1.概念

度：

結點擁有的子樹數(shù)目稱為結點的度。

結點的層次：

從根開始定義起，根為第1層，根的子結點為第2層，以此類推。

高度或深度：

• 樹中結點的最大層次。
• 深度從上往下。
• 高度從下往上。
  以下不是標準定義，但對于我來說很容易記憶。

滿二叉樹：

雙親結點都有2個兒子。

完全二叉樹：

• 從根結點出發(fā)，最深一層以上是滿二叉樹。
• 最后一層葉子結點是從左到右是連續(xù)的，不存在中間有空結點的情況。

2.實現(xiàn)

2.1 順序存儲

2.1.1 結構定義

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存儲空間初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉樹的最大結點數(shù) */

typedef int Status;        /* Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK等 */
typedef int CElemType;      /* 樹結點的數(shù)據(jù)類型，目前暫定為整型 */
typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0號單元存儲根結點  */
CElemType Nil = 0;   /*設整型以0為空 或者以 INT_MAX(65535)*/

// 左兒子索引(雙親結點出發(fā))
#define LeftChild(x) (x)*2+1
// 雙親索引(左兒子反過來算)
// 右兒子多的1，除以2后為0，沒有影響
// 如果要記，就記左兒子算法，雙親直接反推
#define Parent(x) ((x)-1)/2

// 查找用
typedef struct {
    int level; //結點層
    int order; //本層的序號(按照滿二叉樹給定序號規(guī)則)
} Position;

2.1.2 基礎操作

// 1.訪問
Status visit(CElemType c){
    printf("%d ", c);
    return OK;
}

// 2.構造空二叉樹
Status InitBiTree(SqBiTree T) {
    memset(T, Nil, MAX_TREE_SIZE-1);
//    for (int i = 0; i < MAX_TREE_SIZE; i++) {
//        //將二叉樹初始化值置空
//        T[i] = Nil;
//    }
    return OK;
}

// 3.按層序次序輸入二叉樹中的結點值(字符型或整型)，構造順序存儲的二叉樹T
Status CreateBiTree(SqBiTree T) {
    /*
            1       -->1
       2        3   -->2
     4    5   6   7 -->3
    8 9 10          -->4
    1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
    */
    int i = 0;
    while (i < 10) {
        T[i] = i+1;
        printf("%d ",T[i]);
        //結點不為空，且無雙親結點
        if (i != 0 // 不是根結點需要判斷雙親
            && T[i] != Nil // 結點不為空，如果雙親結點為空就有問題
            && T[Parent(i)] == Nil) { // 雙親結點為空
            printf("出現(xiàn)無雙親的非根結點%d\n",T[i]);
            T[i] = Nil;
            return ERROR;
            // 或者直接退出
//            exit(ERROR);
        }
        i++;
    }
    printf("\n");
    //將空賦值給T的后面的結點
    while (i < MAX_TREE_SIZE) {
        T[i] = Nil;
        i++;
    }
    return OK;
}

// 4.清空二叉樹
// 兩個函數(shù)完全一樣，沒必要寫2份，但是為了閱讀方便可以重命名
#define ClearBiTree InitBiTree

// 5.判斷二叉樹是否為空
Status BiTreeEmpty(SqBiTree T) {
    //根結點為空，則二叉樹為空
    if (T[0] == Nil)
        return TRUE;
    return FALSE;
}

// 6.獲取二叉樹的深度
int BiTreeDepth(SqBiTree T) {
    int i = MAX_TREE_SIZE - 1, j = 0;
    for (; i>=0 && T[i] == Nil; i--);// 最后一個葉子節(jié)點
    // 左斜樹序號  1 2 4 8 ...
    // 索引需要-1，0 1 3 7 ...，所以是powl(2, j)-1
    // j層的頭序號比最后一個葉子節(jié)點大時停止遍歷
    for (; powl(2, j)-1 <= i; j++);
    return j;
}

// 7.返回處于位置e(層,本層序號)的結點值
CElemType Value(SqBiTree T, Position e){
    /*
     Position.level -> 結點層.表示第幾層;
     Position.order -> 本層的序號(按照滿二叉樹給定序號規(guī)則)
     */
    // 深度為層數(shù)-1
    int depth = e.level - 1;
    // 左斜樹序號  1 2 4 8 ...
    // 索引需要-1，0 1 3 7 ...，所以是powl(2, depth)-1
    int levelStart = (int)pow(2, depth) - 1;
    // order從1開始而不是0，所以-1
    int idx = e.order - 1;
    return T[levelStart + idx];
}

// 8.獲取二叉樹跟結點的值
Status Root(SqBiTree T,CElemType *e){
    if (T[0] == Nil) return ERROR;
    *e = T[0];
    return OK;
}

// 9.給處于位置e的結點賦值
Status Assign(SqBiTree T, Position e, CElemType value) {
    // 深度為層數(shù)-1
    int depth = e.level - 1;
    // 左斜樹序號  1 2 4 8 ...
    // 索引需要-1，0 1 3 7 ...，所以是powl(2, depth)-1
    int levelStart = (int)pow(2, depth) - 1;
    // order從1開始而不是0，所以-1
    int idx = e.order - 1;
    
    // 目標位置
    int i = levelStart + idx;
    // 重點1：葉子結點的雙親為空
    if (value != Nil && T[Parent(i)] == Nil) return ERROR;
    // 重點2：給雙親賦空值但是有葉子結點
    if (value == Nil && (T[LeftChild(i)] != Nil || T[LeftChild(i)+1] != Nil)) return ERROR;
    // 成功賦值
    T[i] = value;
    return OK;
}

// 10.獲取e的雙親
CElemType ParentValue(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空樹
    for (int i = 1 ; i < MAX_TREE_SIZE; i++) {
        if (T[i] == e) {
            return T[Parent(i)]; //找到e
        }
    }
    return Nil; //沒有找到
}

// 11.獲取某個結點的左孩子
CElemType LeftChildValue(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空樹
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        if (T[i] == e) { //找到e
            return T[LeftChild(i)];
        }
    }
    return Nil; //沒有找到
}

// 12.獲取某個結點的右孩子
CElemType RightChild(SqBiTree T,CElemType e){
    if (T[0] == Nil) return Nil; //空樹
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        if (T[i] == e) { //找到e
            return T[LeftChild(i)+1];
        }
    }
    return Nil; //沒有找到
}

// 13.獲取結點的左兄弟，e值必須是右孩子才有左兄弟
CElemType LeftSibling(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空樹
    for (int i=1; i <= MAX_TREE_SIZE-1; i++) // 頭結點沒有左兄弟，從1開始
        if (T[i]==e && i%2==0) return T[i-1]; // 找到e且其序號為偶數(shù)(是右孩子)
    return Nil; //沒有找到
}

// 14.獲取結點的右兄弟，e值必須是左孩子才有右兄弟
CElemType RightSibling(SqBiTree T, CElemType e) {
    if (T[0] == Nil) return Nil; //空樹
    for (int i=1; i <= MAX_TREE_SIZE-1; i++) // 頭結點沒有左兄弟，從1開始
        if (T[i]==e && i%2==1) return T[i+1]; // 找到e且其序號為奇數(shù)(是左孩子)
    return Nil; //沒有找到
}

2.1.3 遍歷

// 1.層序遍歷(存儲就是層序的)
void LevelOrderTraverse(SqBiTree T){
    int i = MAX_TREE_SIZE - 1;
    for (; i>=0 && T[i] == Nil; i--);// 最后一個葉子結點
    for (int j = 0; j <= i; j++) //從根結點起，按層序遍歷二叉樹
        if (T[j] != Nil) //只遍歷非空結點
            visit(T[j]);
    printf("\n");
}

// 2.前序遍歷二叉樹
void PreTraverse(SqBiTree T, int i){
    //打印結點數(shù)據(jù)
    visit(T[i]);
    //遍歷左子樹
    if (T[LeftChild(i)] != Nil) PreTraverse(T, LeftChild(i));
    //遍歷右子樹
    if (T[LeftChild(i)+1] != Nil) PreTraverse(T, LeftChild(i)+1);
}

Status PreOrderTraverse(SqBiTree T) {
    if (T[0] != Nil) //樹不為空
        PreTraverse(T, 0); // 遞歸遍歷
    printf("\n");
    return  OK;
}

// 3.中序遍歷二叉樹
void InTraverse(SqBiTree T, int i) {
    //遍歷左子樹
    if (T[LeftChild(i)] != Nil) InTraverse(T, LeftChild(i));
    //打印結點數(shù)據(jù)
    visit(T[i]);
    //遍歷右子樹
    if (T[LeftChild(i)+1] != Nil) InTraverse(T, LeftChild(i)+1);
}

Status InOrderTraverse(SqBiTree T) {
    if (T[0] != Nil) //樹不為空
        InTraverse(T, 0); // 遞歸遍歷
    printf("\n");
    return OK;
}

// 4.后序遍歷
void PostTraverse(SqBiTree T,int i) {
    //遍歷左子樹
    if (T[LeftChild(i)] != Nil) PostTraverse(T, LeftChild(i));
    //遍歷右子樹
    if (T[LeftChild(i)+1] != Nil) PostTraverse(T, LeftChild(i)+1);
    //打印結點數(shù)據(jù)
    visit(T[i]);
}

Status PostOrderTraverse(SqBiTree T) {
    if (T[0] != Nil) //樹不為空
        PostTraverse(T,0);
    printf("\n");
    return OK;
}

2.1.4 檢驗

int main(int argc, const char * argv[]) {
    printf("二叉樹順序存儲結構實現(xiàn)!\n");
    
    Status iStatus;
    Position p;
    CElemType e;
    SqBiTree T;
    /*
            1       -->1
       2        3   -->2
     4    5   6   7 -->3
    8 9 10          -->4
    1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
    */
    InitBiTree(T);
    CreateBiTree(T);
    printf("建立二叉樹后，樹空否？%d (1:是 0:否) \n",BiTreeEmpty(T));
    printf("樹的深度 = %d\n",BiTreeDepth(T));
    
    p.level = 3;
    p.order = 2;
    e = Value(T, p);
    printf("第%d層第%d個結點的值: %d\n",p.level,p.order,e);
    
    iStatus = Root(T, &e);
    if (iStatus) {
        printf("二叉樹的根為:%d\n",e);
    } else {
        printf("樹為空,無根!\n");
    }
  
    //向樹中3層第2個結點位置上結點賦值99
    e = 99;
    Assign(T, p, e);
    
    //獲取樹中3層第2個結點位置結點的值是多少:
    e = Value(T,p);
    printf("第%d層第%d個結點的值: %d\n",p.level,p.order,e);
    
    //找到e這個結點的雙親;
    printf("結點%d的雙親為: %d ", e, ParentValue(T, e));
    //找到e這個結點的左右孩子;
    printf("左右孩子分別為: %d, %d\n", LeftChildValue(T, e), RightChild(T, e));
    //找到e這個結點的左右兄弟;
    printf("結點%d的左右兄弟: %d, %d\n", e, LeftSibling(T, e), RightSibling(T, e));
    
    // 還原
    Assign(T, p, 5);
    
    // 開始遍歷
    printf("二叉樹T層序遍歷:");
    LevelOrderTraverse(T);
    printf("二叉樹T先序遍歷:");
    PreOrderTraverse(T);
    printf("二叉樹T中序遍歷:");
    InOrderTraverse(T);
    printf("二叉樹T后序遍歷:");
    PostOrderTraverse(T);
    return 0;
}
// 輸出
二叉樹順序存儲結構實現(xiàn)!
1 2 3 4 5 6 7 8 9 10 
建立二叉樹后，樹空否？0 (1:是 0:否) 
樹的深度 = 4
第3層第2個結點的值: 5
二叉樹的根為:1
第3層第2個結點的值: 99
結點99的雙親為: 2 左右孩子分別為: 10, 0
結點99的左右兄弟: 4, 0
二叉樹T層序遍歷:1 2 3 4 5 6 7 8 9 10 
二叉樹T先序遍歷:1 2 4 8 9 5 10 3 6 7 
二叉樹T中序遍歷:8 4 9 2 10 5 1 6 3 7 
二叉樹T后序遍歷:8 9 4 10 5 2 6 7 3 1 

2.2 鏈式存儲

2.2.1 結構定義

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK等 */
typedef int Status;

// 數(shù)據(jù)結構
typedef char CElemType;
CElemType Nil = '#'; /* 以#為空 */
typedef struct BiTNode { /* 結點結構 */
    CElemType data;        /* 結點數(shù)據(jù) */
    struct BiTNode *lchild, *rchild; /* 左右孩子指針 */
} BiTNode, *BiTree;

為了方便后續(xù)創(chuàng)建二叉樹：

// 全局變量
#define MAXSIZE 100 //存儲空間初始分配量
typedef char String[MAXSIZE]; /*  0號單元存放串的長度 */
String str;
Status StrAssign(String T, char *chars) {
    size_t length = strlen(chars);
    if (length > MAXSIZE) return ERROR;
    T[0] = length;
    for (int i = 1; i <= T[0]; i++)
        T[i] = *(chars+i-1);
    return OK;
}

2.2.2 基礎操作

// 1.打印數(shù)據(jù)
Status visit(CElemType e) {
    printf("%c ",e);
    return OK;
}

// 2.構造空二叉樹T
Status InitBiTree(BiTree *T) {
    *T = NULL;
    return OK;
}

// 3.銷毀二叉樹
void DestroyBiTree(BiTree *T) {
    if (*T) {
        // 有左孩子
        if ((*T)->lchild)
            DestroyBiTree(&(*T)->lchild); // 銷毀左孩子子樹
        // 有右孩子
        if ((*T)->rchild)
            DestroyBiTree(&(*T)->rchild); // 銷毀右孩子子樹
        free(*T); // 釋放結點
        *T = NULL; // 指針賦空
    }
}

// 4.清空樹和銷毀代碼完全一樣
#define ClearBiTree DestroyBiTree

// 5.創(chuàng)建二叉樹
int createIndex = 1;
void CreateBiTree(BiTree *T) {
    CElemType ch = str[createIndex++]; // 獲取字符
    if (ch == Nil) { // 判斷當前字符是否為空
        *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); // 構造右子樹
    }
}

// 6.二叉樹T是否為空
Status BiTreeEmpty(BiTree T) {
    if (T)
        return FALSE;
    else
        return TRUE;
}

// 7.二叉樹T的深度
int BiTreeDepth(BiTree T) {
    if (!T) return 0;
    int i, j;
    i = T->lchild ? BiTreeDepth(T->lchild) : 0; // 計算左孩子的深度
    j = T->rchild ? BiTreeDepth(T->rchild) : 0; // 計算右孩子的深度
    return i > j ? i+1 : j+1; // 比較i和j
}

// 8.二叉樹T的根
CElemType Root(BiTree T) {
    if (BiTreeEmpty(T)) return Nil;
    return T->data;
}

// 9.返回p所指向的結點值
CElemType Value(BiTree p) {
    return p->data;
}

// 10.給p所指結點賦值為value
void Assign(BiTree p, CElemType value) {
    p->data = value;
}

2.2.3 遍歷

// 1.前序遞歸遍歷T
void PreOrderTraverse(BiTree T) {
    if (!T) return;
    printf("%c", T->data); // 顯示結點數(shù)據(jù)
    PreOrderTraverse(T->lchild); // 遍歷左子樹
    PreOrderTraverse(T->rchild); // 遍歷右子樹
}

// 2.中序遞歸遍歷T
void InOrderTraverse(BiTree T) {
    if (!T) return;
    InOrderTraverse(T->lchild); // 遍歷左子樹
    printf("%c", T->data); // 顯示結點數(shù)據(jù)
    InOrderTraverse(T->rchild); // 遍歷右子樹
}

// 3.后序遞歸遍歷T
void PostOrderTraverse(BiTree T) {
    if (!T) return;
    PostOrderTraverse(T->lchild); // 遍歷左子樹
    PostOrderTraverse(T->rchild); // 遍歷右子樹
    printf("%c", T->data); // 顯示結點數(shù)據(jù)
}

2.2.4 檢驗

int main(int argc, const char * argv[]) {
    printf("二叉樹鏈式存儲結構實現(xiàn)!\n");
    
    BiTree T;
    CElemType e1;
    /*
                A
           B        C
         D   E     F   G
        H # # #   I # # J
       # K       # #   # #
        # #
     ABDH#K###E##CFI###G#J##
     */
    InitBiTree(&T);
    StrAssign(str,"ABDH#K###E##CFI###G#J##");
    CreateBiTree(&T);
    printf("二叉樹是否為空: %d (1:是 0:否)\n樹的深度: %d\n", BiTreeEmpty(T), BiTreeDepth(T));
    e1 = Root(T);
    printf("二叉樹的根為: %c\n",e1);
    printf("前序遍歷二叉樹:");
    PreOrderTraverse(T);
    printf("\n中序遍歷二叉樹:");
    InOrderTraverse(T);
    printf("\n后序遍歷二叉樹:");
    PostOrderTraverse(T);
    printf("\n");
    return 0;
}

// 輸出
二叉樹鏈式存儲結構實現(xiàn)!
二叉樹是否為空: 0 (1:是 0:否)
樹的深度: 5
二叉樹的根為: A
前序遍歷二叉樹:ABDHKECFIGJ
中序遍歷二叉樹:HKDBEAIFCGJ
后序遍歷二叉樹:KHDEBIFJGCA

2.2.5 非遞歸遍歷

// 1.前序循環(huán)遍歷T
void LoopPreOrderTraverse(BiTree T) {
    if (!T) return;
    // 這里偷懶知道樹高5
    int top = -1;
    BiTNode **stack = (BiTNode **)malloc(sizeof(BiTNode*) * 5);
    BiTNode *cur = T;
    while (cur || top > -1){
        while (cur) {
            stack[++top] = cur;
            printf("%c", cur->data); // 顯示結點數(shù)據(jù)
            cur = cur->lchild;
        }
        if (top > -1) {
            cur = stack[top];
            --top;
            cur = cur->rchild;
        }
    }
    free(stack);
}

// 2.前序循環(huán)遍歷T
void LoopInOrderTraverse(BiTree T) {
    if (!T) return;
    // 這里偷懶知道樹高5
    int top = -1;
    BiTNode **stack = (BiTNode **)malloc(sizeof(BiTNode*) * 5);
    BiTNode *cur = T;
    while (cur || top > -1){
        while (cur) {
            stack[++top] = cur;
            cur = cur->lchild;
        }
        if (top > -1) {
            cur = stack[top];
            printf("%c", cur->data); // 顯示結點數(shù)據(jù)
            --top;
            cur = cur->rchild;
        }
    }
    free(stack);
}

// 3.前序循環(huán)遍歷T
void LoopPostOrderTraverse(BiTree T) {
    if (!T) return;
    // 這里偷懶知道樹高5
    int top = -1;
    BiTNode **stack = (BiTNode **)malloc(sizeof(BiTNode*) * 5);
    BiTNode *cur = T, *recent = NULL;
    while (cur || top > -1) {
        if (cur) { //走到最左邊
            stack[++top] = cur;
            cur = cur->lchild;
        } else {
            cur = stack[top];
            if (cur->rchild && cur->rchild != recent) //右子樹存在，未被訪問
                cur = cur->rchild;
            else {
                --top;
                printf("%c", cur->data); // 顯示結點數(shù)據(jù)
                recent = cur; //記錄最近訪問過的節(jié)點
                cur = NULL; //節(jié)點訪問完后，重置p指針
            }
        }
    }
    free(stack);
}

// 檢驗
int main(int argc, const char * argv[]) {
    BiTree T;
    CElemType e1;
    /*
                A
           B        C
         D   E     F   G
        H # # #   I # # J
       # K       # #   # #
        # #
     ABDH#K###E##CFI###G#J##
     */
    
    InitBiTree(&T);
    StrAssign(str,"ABDH#K###E##CFI###G#J##");
    CreateBiTree(&T);
    
    printf("遞歸前序遍歷二叉樹:");
    PreOrderTraverse(T);
    printf("\n遞歸中序遍歷二叉樹:");
    InOrderTraverse(T);
    printf("\n遞歸后序遍歷二叉樹:");
    PostOrderTraverse(T);
    
    printf("\n循環(huán)前序遍歷二叉樹:");
    LoopPreOrderTraverse(T);
    printf("\n循環(huán)中序遍歷二叉樹:");
    LoopInOrderTraverse(T);
    printf("\n循環(huán)后序遍歷二叉樹:");
    LoopPostOrderTraverse(T);
  
    printf("\n");
    return 0;
}
// 輸出
遞歸前序遍歷二叉樹:ABDHKECFIGJ
遞歸中序遍歷二叉樹:HKDBEAIFCGJ
遞歸后序遍歷二叉樹:KHDEBIFJGCA
循環(huán)前序遍歷二叉樹:ABDHKECFIGJ
循環(huán)中序遍歷二叉樹:HKDBEAIFCGJ
循環(huán)后序遍歷二叉樹:KHDEBIFJGCA