二叉樹的存儲方式

樹結構

樹是一種非線性數(shù)據(jù)結構，它是由數(shù)據(jù)元素（結點）按分支關系組織起來的結構。

相關術語

  1. 每個元素稱為結點；
  2. 有一個特定的結點，稱為根結點；
  3. 其余結點被分成m（m>=0）個互不相交的有限集合，而每個子集又都是一棵樹，稱為子樹；
  4. 結點的分支數(shù)，以組成該樹各結點中最大的度， 稱為為該樹的度,也叫寬度；
  5. 組成該樹各結點的最大層次，稱為樹的深度；
  6. 樹的根節(jié)點為第1層，其他結點的層次等于它的父結點的層次數(shù)加1；
  7. 樹中度為零的結點，稱為葉結點或終端結點；
  8. 樹中度不為零的結點，稱為分枝結點或非終端結點；
  9. 除根結點外的分枝結點統(tǒng)，稱為內(nèi)部結點；
  10. 結點的上一級，稱為父結點；
  11. 同一雙親結點的子結點之間互為兄弟結點；
  12. 樹中任意節(jié)點的子結點之間有順序關系，這種樹稱為有序樹；
  13. 樹中任意節(jié)點的子結點之間沒有順序關系，這種樹稱為無序樹,也稱為自由樹，

二叉樹

二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”和“右子樹”。

相關術語

  1. 一棵深度為 k，且有2^k-1 個結點的二叉樹，稱為滿二叉樹；
  2. 在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且或者最后一層是滿的，或者是在右邊缺少連續(xù)若干結點，則此二叉樹為完全二叉樹；
  3. 所有節(jié)點都只有左子樹，稱為左斜樹；
  4. 所有節(jié)點都只有右子樹，稱為右斜樹；

性質(zhì)

  1. 在二叉樹的第 i 層上最多有2^{i-1} 個結點
  2. 深度為 K 的二叉樹最多有2^k -1 個結點(K>=1)
  3. 對于任何一顆二叉樹 T，如果其終端結點數(shù)為 n_0,度為 2 的結點數(shù)為n_2，則n_0 = n_2 + 1;
  4. 具有 n 個結點的完全二叉樹的深度為log{2n} + 1

順序結構

初始化
BOOL InitBiTree(SqBiTree T){
    for (int i = 0; i < MAXSIZE;i++)
    { 
    T[i] = Nil;
    }
    return true;
}
創(chuàng)建二叉樹
BOOL createBiTree(SqBiTree T) {
     int i = 0;
     while (i < 10) {
             T[i] = i+1;
             printf("%d ",T[i]);
             //結點不為空,且無雙親結點
             if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
                 printf("出現(xiàn)無雙親的非根結點%d\n",T[i]);
                 exit(0);
             }
             
             i++;
             
     }
     //將空賦值給T的后面的結點
     while (i < MAXSIZE) {
         T[i] = Nil;
         i++;
     }
     return true;
}
是否空樹
//是否空樹
BOOL isEmpty(SqBiTree T){
 return T[0] == Nil;
}
獲取深度
int BiTreeDepth(SqBiTree T) {

    int j = -1;
    int i;
    for (i = MAXSIZE - 1; i >= 0; i--) {
        if (T[i] != Nil) {

            break;
        }
    }

    do {
        j++;
    } while (pow(2, j) <= i);

    return j;
}
獲取E點的值
//獲取E點的結點值
CElemType getValue(SqBiTree T,Position e){
     return T[pow(2,e.level - 1) + e.order - 2];
}

//插入值至位置e
BOOL Assign(SqBiTree T,Position e  ,CElemType value){
    int i = pow(2,e.level - 1) + e.order - 2;
    if (T[(i + 1) / 2 - 1] == Nil ){
        return false;
    }
    T[i] = value;
    return true;
}
插入結點
//插入值至位置e
BOOL Assign(SqBiTree T,Position e  ,CElemType value){
 int i = pow(2,e.level - 1) + e.order - 2;
 if (T[(i + 1) / 2 - 1] == Nil ){
       return false;
 }
 T[i] = value;
 return true;
}
左子結點
int leftChild(SqBiTree T,Position e){
return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 1 ];
}
右子結點
int rightChild(SqBiTree T,Position e){
 return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 2 ];
}
雙親結點
int fatherNode(SqBiTree T, Position e) {

    if (e.level != 1) {
        return T[(int)(pow(2, e.level - 1) + e.order - 2) / 2 - 1];
    }
    return -1;
    }
前序遍歷（中左右）
/*
前序遍歷二叉樹 中左右
*/
void PreTraverse(SqBiTree T, int e) {

    //打印結點數(shù)據(jù)

    printf("%d ", T[e]);

    //先序遍歷左子樹
    if (T[2 * e + 1] != Nil) {
        PreTraverse(T, 2 * e + 1);
    }
    //最后先序遍歷右子樹
    if (T[2 * e + 2] != Nil) {
        PreTraverse(T, 2 * e + 2);
    }
}

BOOL PreOrderTraverse(SqBiTree T) {

    //樹不為空
    if (!isEmpty(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return true;
}
中序遍歷（左中右）
void InTraverse(SqBiTree T, int e){
    /* 左子樹不空 */
    if (T[2*e+1] != Nil)
        InTraverse(T, 2*e+1);

     printf("%d ",T[e]);

    /* 右子樹不空 */
    if (T[2*e+2] != Nil)
        InTraverse(T, 2*e+2);
}

BOOL InOrderTraverse(SqBiTree T){

    /* 樹不空 */
    if (!isEmpty(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return true;
}
后序遍歷
void PostTraverse(SqBiTree T,int e){   
    /* 左子樹不空 */
        if(T[2*e+1]!=Nil)
            PostTraverse(T,2*e+1);
        /* 右子樹不空 */
        if(T[2*e+2]!=Nil)
            PostTraverse(T,2*e+2);
        printf("%d ",T[e]);

}
BOOL PostOrderTraverse(SqBiTree T){
        if(!isEmpty(T)) /* 樹不空 */
            PostTraverse(T,0);
        printf("\n");
        return true;
}

鏈式存儲

結構
typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符為空 */
typedef struct BiTNode  /* 結點結構 */
{
   CElemType data;        /* 結點數(shù)據(jù) */
   struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode,*BiTree;
初始化
BOOL InitBiTree(BiTree *T)
{
   *T=NULL;
   return true;
}
銷毀二叉樹
void DestroyBiTree(BiTree *T)
{
   if(*T)
   {
       /* 有左孩子 */
       if((*T)->lchild)
           DestroyBiTree(&(*T)->lchild); /* 銷毀左孩子子樹 */

       /* 有右孩子 */
       if((*T)->rchild)
           DestroyBiTree(&(*T)->rchild); /* 銷毀右孩子子樹 */

       free(*T); /* 釋放根結點 */

       *T=NULL; /* 空指針賦0 */
   }
}
創(chuàng)建二叉樹
void CreateBiTree(BiTree *T){
    
    CElemType ch;
    
    //獲取字符
    ch = str[indexs++];
    
    //判斷當前字符是否為'#'
    if (ch == '#') {
        *T = NULL;
    }else
    {
        //創(chuàng)建新的結點
        *T = (BiTree)malloc(sizeof(BiTNode));
        //是否創(chuàng)建成功
        if (!*T) {
            exit(OVERFLOW);
        }
        
        /* 生成根結點 */
        (*T)->data = ch;
        /* 構造左子樹 */
        CreateBiTree(&(*T)->lchild);
        /* 構造右子樹 */
        CreateBiTree(&(*T)->rchild);
    }
    
}
判斷二叉樹是否為空
BOOL BiTreeEmpty(BiTree T)
{
   if(T)
       return false;
   else
       return true;
}
二叉樹的深度
int BiTreeDepth(BiTree T){

   int i,j;
   if(!T)
       return 0;

   //計算左孩子的深度
   if(T->lchild)
       i=BiTreeDepth(T->lchild);
   else
       i=0;

   //計算右孩子的深度
   if(T->rchild)
       j=BiTreeDepth(T->rchild);
   else
       j=0;

   //比較i和j
   return i>j?i+1:j+1;
}
根結點
CElemType getRoot(BiTree T){
   if (BiTreeEmpty(T))
       return Nil;

   return T->data;
}
獲取結點的值
CElemType getValue(BiTree p){
   return p->data;
}
給結點賦值
void Assign(BiTree p,CElemType value)
{
   p->data=value;
}
前序遍歷
void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);/* 顯示結點數(shù)據(jù)，可以更改為其它對結點操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍歷左子樹 */
    PreOrderTraverse(T->rchild); /* 最后先序遍歷右子樹 */
}
中序遍歷
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild); /* 中序遍歷左子樹 */
    printf("%c",T->data);/* 顯示結點數(shù)據(jù)，可以更改為其它對結點操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍歷右子樹 */
}
后序遍歷
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍歷左子樹  */
    PostOrderTraverse(T->rchild); /* 再后序遍歷右子樹  */
    printf("%c",T->data);/* 顯示結點數(shù)據(jù)，可以更改為其它對結點操作 */
}
最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容