關(guān)于樹的定義和存儲結(jié)構(gòu)可以查看上一篇文章樹的定義和樹的三種存儲結(jié)構(gòu)

一蹄溉、二叉樹的定義

二叉樹的定義

二叉樹（Binary Tree）是n（n>=0）個結(jié)點的有限集合昼钻，該集合或者為空集（稱為空二叉樹），或者是由一個根結(jié)點和兩顆互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成痘昌。（官方概念，不是很直觀，直接上圖）

二叉樹

二叉樹的特點

• 每個結(jié)點最多有兩顆子樹辆苔，所以二叉樹中不存在度大于2的結(jié)點算灸。（注意不是只有兩顆子樹，是最多有）
• 左子樹和右子樹是有順序的驻啤，次序不能任意顛倒菲驴。
• 即使樹中某個結(jié)點只有一棵樹，也要區(qū)分它是左子樹還是右子樹街佑。

二叉樹的五中基本形態(tài)

• 空二叉樹谢翎。
• 只有一個根節(jié)點。
• 根結(jié)點只有左子樹沐旨。
• 根結(jié)點只有右子樹森逮。
• 根結(jié)點既有左子樹又有右子樹。

特殊二叉樹

斜樹

• 左斜樹：所有的結(jié)點都只有左子樹的二叉樹磁携。
• 右斜樹：所有的結(jié)點都只有右子樹的二叉樹褒侧。

滿二叉樹

所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上的二叉樹谊迄。

滿二叉樹的特點

• 葉子結(jié)點只能出現(xiàn)在最下一層闷供。出現(xiàn)在其他層就不可能達到平衡。
• 非葉子結(jié)點的度一定是2统诺。
• 在同樣深度的二叉樹中歪脏，滿二叉樹的結(jié)點個數(shù)最多，葉子數(shù)最少粮呢。

完全二叉樹

對于一顆具有n個結(jié)點的二叉樹按層序編號婿失，如果編號為i(1<=i&&i<=n)的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中位置完全相同的二叉樹。（概念難理解啄寡，直接上圖）

完全二叉樹

完全二叉樹的特點

• 葉子結(jié)點只能出現(xiàn)在最下兩層豪硅。
• 最下層的葉子一定集中在左部連續(xù)位置。
• 倒數(shù)第二層挺物，若有葉子結(jié)點懒浮，一定都在右部連續(xù)位置。
• 如果結(jié)點度為1识藤，則該節(jié)點只有左孩子砚著，即不存在只有右子樹的情況。
• 同樣結(jié)點的二叉樹痴昧，完全二叉樹的深度最小赖草。

區(qū)分滿二叉樹和完全二叉樹

• 滿二叉樹一定是完全二叉樹。
• 完全二叉樹不一定是滿二叉樹剪个。

二、二叉樹的性質(zhì)

• 性質(zhì)1：在二叉樹的第i層上至多有2^(i-1)個結(jié)點（i>=1）。
• 性質(zhì)2：深度為k的二叉樹至多有2^k - 1個結(jié)點(k>=1)扣囊。（注意是2^k后再減去1）
• 性質(zhì)3：對任何一顆二叉樹T乎折，如果其終端結(jié)點數(shù)為n0,度為2的結(jié)點樹為n2,則n0 = n2+1.
• 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為：向下取整log2n+1;(注意，對x的向下取整就是取不大于x的最大整數(shù))
• 性質(zhì)5：如果對一顆有n個結(jié)點的完全二叉樹的結(jié)點按層序編號（從第1層到第（向下取整log2n+1）侵歇，每層從左到右）層骂澄，對任一結(jié)點i(1<=i&&i<=n)有：
  • 如果i=1，則結(jié)點i是二叉樹的根惕虑，無雙親坟冲；如果i>1，則其雙親是結(jié)點：向下取整i/2;
  • 如果2i>n溃蔫，則結(jié)點i無左孩子（結(jié)點i為葉子結(jié)點）;否則其左孩子是結(jié)點2i;
  • 如果2i+1>n健提，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1伟叛；

三私痹、二叉樹的存儲結(jié)構(gòu)

樹的存儲結(jié)構(gòu)可以查看前一篇文章：
由于二叉樹是特殊的樹樹的定義和樹的三種存儲結(jié)構(gòu)

由于二叉樹是一種特殊的樹，所以一般采用二叉鏈表來存儲二叉樹统刮。將二叉樹的結(jié)點的最多有兩個孩子紊遵，所以為它設(shè)計一個數(shù)據(jù)域和兩個指針域。

代碼實現(xiàn)：

/* 二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義 */
typedef int  ElemeType;
typedef struct  BiTNode{ // 結(jié)點結(jié)構(gòu)
    ElemeType data; // 結(jié)點數(shù)據(jù)
    struct BiTNode * lchild; // 左孩子指針
    struct BiTNode * rchild; // 右孩子指針
}BiTNode, *BiTree;

二叉鏈表

四侥蒙、二叉樹的遍歷

二叉樹的遍歷定義

二叉樹的遍歷是指從根節(jié)點出發(fā)暗膜，按照某種次序訪問二叉樹中所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次鞭衩。

二叉樹的遍歷方式有很多学搜，如果我們限制了從左到右的習(xí)慣方式，那么主要分為四種：

• 前序遍歷
• 中序遍歷
• 后序遍歷
• 層序遍歷

前序遍歷

• 若二叉樹為空醋旦，則空操作返回恒水；
• 若不為空，則先訪問根結(jié)點饲齐，然后前序遍歷左子樹钉凌，在前序遍歷右子樹。

• 下圖的前序遍歷結(jié)果為：ABDGHCEIF

  
  
  前序遍歷

中序遍歷

• 若二叉樹為空捂人，則空操作返回御雕；
• 若不為空，則從根節(jié)點開始（注意并不是先訪問根結(jié)點）滥搭，中序遍歷根節(jié)點的左子樹酸纲，然后訪問根節(jié)點，最后中序遍歷右子樹瑟匆。

• 下圖的中序遍歷結(jié)果是：GDHBAEICF

  
  
  中序遍歷

后序遍歷

• 若二叉樹為空闽坡，則空操作返回；
• 若不為空，則從左到右先葉子后結(jié)點的方式遍歷訪問左右子樹疾嗅，最后訪問根節(jié)點外厂。

• 下圖的后序遍歷結(jié)果為：

  
  

層序遍歷

• 若二叉樹為空，則空操作返回代承；
• 若不為空汁蝶，則從樹的第一層(也就是根結(jié)點)開始訪問，從上到下逐層遍歷论悴，在同一層中掖棉，從左到右的順序?qū)Y(jié)點逐個訪問。

• 下圖的層序遍歷結(jié)果為：ABCDEFGHI

  
  
  層序遍歷

代碼實現(xiàn)

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100 

typedef char ElemType;

typedef struct BiTNode{
    
    char data;  // 數(shù)據(jù)域
    struct BiTNode * lchild;  // 指向左孩子的指針
    struct BiTNode * rchild; // 指向右孩子的指針
}BiTNode, *BiTree;

/**
 * 按照前序輸入的方式構(gòu)造二叉樹
 */
void CreatBitree(BiTree *T){
    
    char c = '\0';
    
    scanf("%c", &c);
    
    if (c == '#') {  // 空結(jié)點
        *T = NULL;
        
    }else{
        
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        if (!T)
            exit(0);
        (*T)->data = c;  // 生成根節(jié)點
        CreatBitree(&(*T)->lchild);  // 構(gòu)造左子樹
        CreatBitree(&(*T)->rchild);  // 構(gòu)造右子樹
    }
}


/**
 * 二叉樹的前序遞歸遍歷
 */
void PreOrderTraverse(BiTree T){
    
    if (T == NULL)  // 空樹
        return;
    printf("%c", T->data);  // 顯示結(jié)點數(shù)據(jù)
    
    PreOrderTraverse(T->lchild);  // 先序遍歷左子樹
    PreOrderTraverse(T->rchild);  // 再先序遍歷右子樹
}

/**
 * 二叉樹的中序遞歸遍歷
 */
void InOrderTraverse(BiTree T){
    
    if (T == NULL)  // 空樹
        return;
    InOrderTraverse(T->lchild);  // 中序遍歷左子樹
    
    printf("%c", T->data);  // 顯示結(jié)點數(shù)據(jù)
    
    InOrderTraverse(T->rchild); // 最后中序遍歷右子樹
}

/**
 * 二叉樹的后序遞歸遍歷
 */
void PostOrderTraverse(BiTree T){
    
    if (T == NULL)  // 空樹
        return;
    
    PostOrderTraverse(T->lchild);  // 先后序遍歷左子樹
    PostOrderTraverse(T->rchild);  // 再后序遍歷右子樹
    printf("%c", T->data);  // 顯示結(jié)點數(shù)據(jù)
}

測試代碼

int main(int argc, const char * argv[]) {
    
    printf("請按照先序輸入二叉樹的結(jié)點膀估，空結(jié)點用#表示, 回車結(jié)束\n");

    BiTree T = NULL;
    CreatBitree(&T);
    
    printf("該二叉樹的前序遍歷結(jié)果為：\n");
    PreOrderTraverse(T);
    printf("\n");
    
    printf("該二叉樹的中序遍歷結(jié)果為：\n");
    InOrderTraverse(T);
    printf("\n");
    
    printf("該二叉樹的后序遍歷結(jié)果為：\n");
    PostOrderTraverse(T);
    printf("\n");

    return 0;
}

擴展：遍歷二叉樹的同時輸出該節(jié)點所在的層數(shù)

在二叉樹的幾種遍歷方式的代碼中幔亥，為了輸出該節(jié)點的數(shù)據(jù)，會有一個printf玖像，要輸出該節(jié)點的層數(shù) 紫谷，就可以改變這里的代碼來實現(xiàn)，比如在前序遞歸遍歷的同時輸出節(jié)點所在層數(shù)捐寥，可以將這個打印代碼寫在一個封裝在一個方法里面然后調(diào)用

代碼實現(xiàn)

/**
 * 打印該節(jié)點所在層數(shù)
 */
void visit(char c, int level){
    printf("%c 位于第 %d 層\n", c, level);
}
/**
 * 二叉樹的前序遞歸遍歷
 */
void PreOrderTraverse(BiTree T, int level){
    
    if (T == NULL)  // 空樹
        return;
//    printf("%c", T->data);  // 顯示結(jié)點數(shù)據(jù)
    visit(T->data, level);  // 調(diào)用寫好的打印方法
    
    PreOrderTraverse(T->lchild, level + 1);  // 先序遍歷左子樹
    PreOrderTraverse(T->rchild, level + 1);  // 再先序遍歷右子樹
}
int main(int argc, const char * argv[]) {
    
    printf("請按照先序輸入二叉樹的結(jié)點笤昨，空結(jié)點用#表示, 回車結(jié)束\n");

    int level = 1;
    BiTree T = NULL;
    CreatBitree(&T);
    
    printf("該二叉樹的前序遍歷結(jié)果為：\n");
    PreOrderTraverse(T, level);
    printf("\n");
    return 0;
}

結(jié)果輸出