樹結(jié)構(gòu)

樹是一種非線性數(shù)據(jù)結(jié)構(gòu)应狱，它是由數(shù)據(jù)元素（結(jié)點(diǎn)）按分支關(guān)系組織起來的結(jié)構(gòu)坝初。

相關(guān)術(shù)語

1. 每個元素稱為結(jié)點(diǎn)凡伊；
2. 有一個特定的結(jié)點(diǎn)唧席，稱為根結(jié)點(diǎn)擦盾；
3. 其余結(jié)點(diǎn)被分成m（m>=0）個互不相交的有限集合，而每個子集又都是一棵樹淌哟，稱為子樹迹卢；
4. 結(jié)點(diǎn)的分支數(shù)，以組成該樹各結(jié)點(diǎn)中最大的度徒仓， 稱為為該樹的度,也叫寬度腐碱；
5. 組成該樹各結(jié)點(diǎn)的最大層次，稱為樹的深度掉弛；
6. 樹的根節(jié)點(diǎn)為第1層症见，其他結(jié)點(diǎn)的層次等于它的父結(jié)點(diǎn)的層次數(shù)加1；
7. 樹中度為零的結(jié)點(diǎn)殃饿，稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)谋作；
8. 樹中度不為零的結(jié)點(diǎn)，稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)壁晒；
9. 除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)瓷们，稱為內(nèi)部結(jié)點(diǎn)；
10. 結(jié)點(diǎn)的上一級秒咐，稱為父結(jié)點(diǎn)谬晕；
11. 同一雙親結(jié)點(diǎn)的子結(jié)點(diǎn)之間互為兄弟結(jié)點(diǎn)；
12. 樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系携取，這種樹稱為有序樹攒钳；
13. 樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹,也稱為自由樹雷滋，

二叉樹

二叉樹是每個結(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)不撑。通常子樹被稱作“左子樹”和“右子樹”。

相關(guān)術(shù)語

1. 一棵深度為 k晤斩，且有 個結(jié)點(diǎn)的二叉樹焕檬，稱為滿二叉樹；
2. 在一棵二叉樹中澳泵，除最后一層外实愚，若其余層都是滿的，并且或者最后一層是滿的，或者是在右邊缺少連續(xù)若干結(jié)點(diǎn)腊敲，則此二叉樹為完全二叉樹击喂；
3. 所有節(jié)點(diǎn)都只有左子樹，稱為左斜樹碰辅；
4. 所有節(jié)點(diǎn)都只有右子樹懂昂，稱為右斜樹；

性質(zhì)

1. 在二叉樹的第 i 層上最多有 個結(jié)點(diǎn)
2. 深度為 K 的二叉樹最多有 個結(jié)點(diǎn)
3. 對于任何一顆二叉樹 T没宾，如果其終端結(jié)點(diǎn)數(shù)為 ,度為 2 的結(jié)點(diǎn)數(shù)為凌彬，則 = + 1;
4. 具有 n 個結(jié)點(diǎn)的完全二叉樹的深度為

順序結(jié)構(gòu)

初始化

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]);
             //結(jié)點(diǎn)不為空,且無雙親結(jié)點(diǎn)
             if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
                 printf("出現(xiàn)無雙親的非根結(jié)點(diǎn)%d\n",T[i]);
                 exit(0);
             }
             
             i++;
             
     }
     //將空賦值給T的后面的結(jié)點(diǎn)
     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點(diǎn)的值

//獲取E點(diǎn)的結(jié)點(diǎn)值
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;
}

插入結(jié)點(diǎn)

//插入值至位置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;
}

左子結(jié)點(diǎn)

int leftChild(SqBiTree T,Position e){
return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 1 ];
}

右子結(jié)點(diǎn)

int rightChild(SqBiTree T,Position e){
 return T[(int)(pow(2, e.level-1)+e.order-2) * 2 + 2 ];
}

雙親結(jié)點(diǎn)

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) {

    //打印結(jié)點(diǎn)數(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;
}

鏈?zhǔn)酱鎯?/h4>

結(jié)構(gòu)

typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符為空 */
typedef struct BiTNode  /* 結(jié)點(diǎn)結(jié)構(gòu) */
{
   CElemType data;        /* 結(jié)點(diǎn)數(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); /* 釋放根結(jié)點(diǎn) */

       *T=NULL; /* 空指針賦0 */
   }
}

創(chuàng)建二叉樹

void CreateBiTree(BiTree *T){
    
    CElemType ch;
    
    //獲取字符
    ch = str[indexs++];
    
    //判斷當(dāng)前字符是否為'#'
    if (ch == '#') {
        *T = NULL;
    }else
    {
        //創(chuàng)建新的結(jié)點(diǎn)
        *T = (BiTree)malloc(sizeof(BiTNode));
        //是否創(chuàng)建成功
        if (!*T) {
            exit(OVERFLOW);
        }
        
        /* 生成根結(jié)點(diǎn) */
        (*T)->data = ch;
        /* 構(gòu)造左子樹 */
        CreateBiTree(&(*T)->lchild);
        /* 構(gòu)造右子樹 */
        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;

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

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

   //比較i和j
   return i>j?i+1:j+1;
}

根結(jié)點(diǎn)

CElemType getRoot(BiTree T){
   if (BiTreeEmpty(T))
       return Nil;

   return T->data;
}

獲取結(jié)點(diǎn)的值

CElemType getValue(BiTree p){
   return p->data;
}

給結(jié)點(diǎn)賦值

void Assign(BiTree p,CElemType value)
{
   p->data=value;
}

前序遍歷

void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);/* 顯示結(jié)點(diǎn)數(shù)據(jù)，可以更改為其它對結(jié)點(diǎn)操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍歷左子樹 */
    PreOrderTraverse(T->rchild); /* 最后先序遍歷右子樹 */
}

中序遍歷

void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild); /* 中序遍歷左子樹 */
    printf("%c",T->data);/* 顯示結(jié)點(diǎn)數(shù)據(jù)榕吼，可以更改為其它對結(jié)點(diǎn)操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍歷右子樹 */
}

后序遍歷

void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍歷左子樹  */
    PostOrderTraverse(T->rchild); /* 再后序遍歷右子樹  */
    printf("%c",T->data);/* 顯示結(jié)點(diǎn)數(shù)據(jù)饿序，可以更改為其它對結(jié)點(diǎn)操作 */
}