比如我們要?jiǎng)?chuàng)建如下一個(gè)二叉樹：

//創(chuàng)建節(jié)點(diǎn)
BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}
//創(chuàng)建鏈?zhǔn)蕉鏄?/span>
BTNode* CreateBTree()
{BTNode* node1 = BuyBTNode(1);BTNode* node2 = BuyBTNode(2);BTNode* node3 = BuyBTNode(3);BTNode* node4 = BuyBTNode(4);BTNode* node5 = BuyBTNode(5);BTNode* node6 = BuyBTNode(6);BTNode* node7 = BuyBTNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->left = node7;return node1;
}

1.2 根、左子樹、右子樹

由于這里是鏈?zhǔn)蕉鏄?#xff0c;所以后面我們看到一個(gè)二叉樹，就要把樹分成三個(gè)部分：根、左子樹、右子樹?；仡櫠鏄涞母拍?#xff1a;二叉樹分為空樹和非空二叉樹，非空二叉樹由根結(jié)點(diǎn)、根結(jié)點(diǎn)的左子樹、根結(jié)點(diǎn)的右子樹組成的。
根結(jié)點(diǎn)的左子樹和右子樹分別又是由子樹的根結(jié)點(diǎn)、子樹結(jié)點(diǎn)的左子樹、子樹結(jié)點(diǎn)的右子樹組成的。因此二叉樹的定義是遞歸式的, 后序鏈?zhǔn)蕉鏄涞牟僮髦谢径际前凑赵摳拍顚?shí)現(xiàn)的。

1.3 二叉樹的前中后序遍歷

二叉樹的操作離不開樹的遍歷，那二叉樹的遍歷有哪些方式呢？比如我們要遍歷下面這個(gè)二叉樹：
二叉樹的遍歷分為三種：前/中/后序遍歷。下面我們分別講解三種遍歷。

1.3.1前(先)序遍歷

▲ 前序遍歷(Preorder Traversal(DLR)亦稱先序遍歷): 訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前

訪問順序?yàn)? 根結(jié)點(diǎn)、左子樹、右子樹

void PreOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}printf("%c ",root->val);PreOrder(root->left);PreOrder(root->right);
}

先看運(yùn)行結(jié)果：

打印的結(jié)果為什么是上面的樣子呢？這里涉及到函數(shù)的遞歸，所以要先理解前序遍歷的順序是根、左子樹、右子樹。也就是從根節(jié)點(diǎn)開始遍歷，根遍歷完了就到左子樹，那左子樹又可以分為根、左子樹、右子樹，又會(huì)按照根左右的順序遍歷；要等到左子樹完完全全遍歷完了，才會(huì)遍歷到右子樹。這里的難點(diǎn)就是: 理解遞歸遞推的終止條件和每一層函數(shù)調(diào)用完畢后會(huì)返回上一層調(diào)用它的函數(shù)處繼續(xù)往后執(zhí)行(回歸)。

前序遍歷的遞歸過程如下：

1.3.2中序遍歷

◆中序遍歷(lnorder Traversal(LDR)): 訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中(間)

訪問順序?yàn)? 左子樹、根結(jié)點(diǎn)、右子樹

void InOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}

打印結(jié)果如下：

中序遍歷就是從左子樹開始遍歷，左子樹遍歷完了就遍歷根，最后再遍歷右子樹。而其中的子樹又可以分為左子樹、根、右子樹，又會(huì)按照左根右的順序遍歷。

1.3.3后序遍歷

▼后序遍歷(Postorder Traversal(LRD)): 訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后

訪問順序?yàn)? 左子樹、右子樹、根結(jié)點(diǎn)

void PostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->val);
}

打印結(jié)果如下：

后序遍歷就是根要在左右子樹之后訪問。前\中\(zhòng)后續(xù)遍在歷代碼中的遞歸調(diào)用雖然只是換了個(gè)位置，但是遞歸調(diào)用的過程是不相同的，如不理解函數(shù)的逐層調(diào)用過程，就需要畫圖層層遞進(jìn)地來深刻剖析遞歸。

1.4 二叉樹的節(jié)點(diǎn)個(gè)數(shù)

通過遞歸計(jì)算二叉樹的節(jié)點(diǎn)個(gè)數(shù)：

int BTreeSize(BTNode* root)
{if (root == NULL)return 0;return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

這里要理解遞歸的過程是什么樣, 以下圖的舉例來理解這里的遞歸：
這里遞推的結(jié)束條件是：子樹為空才會(huì)回歸上一層; 而空樹就沒有節(jié)點(diǎn)嘛！所以return 0。在返回上一層的時(shí)候可以看到是左右子樹都遞歸完畢而且還要加一個(gè)1之后才返回上一層，加的1其實(shí)就是加上根節(jié)點(diǎn)的數(shù)量。

1.5 二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)

通過遞歸計(jì)算二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)：

int BTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

沒有孩子節(jié)點(diǎn)的節(jié)點(diǎn)就是葉子節(jié)點(diǎn)，所以遞推結(jié)束的條件就是：該節(jié)點(diǎn)的左右子樹為空就返回1，即把該葉子節(jié)點(diǎn)的數(shù)量計(jì)上。而一開始的判空其實(shí)針對(duì)對(duì)根節(jié)點(diǎn)而言的。如果樹都為空，那就沒有葉子節(jié)點(diǎn)啦。舉例遞歸過程：

1.6 第K層節(jié)點(diǎn)個(gè)數(shù)

二叉樹的第K層節(jié)點(diǎn)個(gè)數(shù)：

int BTreeLevelKSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return BTreeLevelKSize(root->left, k - 1)+ BTreeLevelKSize(root->right, k - 1);
}

計(jì)算二叉樹第K層的節(jié)點(diǎn)，這里需要加入一個(gè)參數(shù)k才能實(shí)現(xiàn)，因?yàn)槲覀儾恢肋f歸什么時(shí)候會(huì)到達(dá)第k層，所以傳一個(gè)參數(shù)k，讓它每遞推一次就遞減1，若根節(jié)點(diǎn)為第一層，則k遞減到1就到達(dá)第k層了(遞推終止條件)。當(dāng)然還有一個(gè)遞推終止條件就是還沒到達(dá)第k層就已經(jīng)出現(xiàn)了空節(jié)點(diǎn)，所以還沒到達(dá)第k層時(shí)就遇到了空就返回。

1.7 二叉樹的高度

通過遞歸計(jì)算二叉樹的高度/深度：

int BTreeDepth(BTNode* root)
{if (root == NULL)return 0;int leftDepth = BTreeDepth(root->left);int rightDepth = BTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

計(jì)算二叉樹的高度也就是計(jì)算該二叉樹有多少層？那就是我們要找到一個(gè)沿著其祖先路徑最長(zhǎng)的那個(gè)節(jié)點(diǎn)。所以左右子樹之間需要通過比較返回較長(zhǎng)的那個(gè)節(jié)點(diǎn)才行。每返回一層要加個(gè)1因?yàn)槊總€(gè)節(jié)點(diǎn)相較于其孩子節(jié)點(diǎn)都是一個(gè)根，只要不為空就要算一節(jié)長(zhǎng)度。
注意：如果上面的代碼簡(jiǎn)化寫成下面的樣子：

return BTreeDepth(root->left) > BTreeDepth(root->right)? BTreeDepth(root->left)+1 : BTreeDepth(root->right)+1;

這樣寫時(shí)間效率上會(huì)非常差。試想：如果二叉樹的節(jié)點(diǎn)數(shù)量龐大，即層數(shù)很多時(shí)；左右子樹相比較就要進(jìn)行兩個(gè)函數(shù)的遞歸調(diào)用，遞歸調(diào)用又是三目表達(dá)式，那時(shí)間消耗就會(huì)很大；而等比較出了大小以后，才決定三目表達(dá)式的返回值；而返回值又是一個(gè)函數(shù)的遞歸調(diào)用，遞推進(jìn)入下一層以后還是面臨同樣的三目表達(dá)式，同樣的事情一遍又一遍地重復(fù)，就會(huì)消耗非常非常多的時(shí)間。所以這里不建議這么寫，最好的方式就是將函數(shù)的返回值記錄下來，這樣回歸的時(shí)候?qū)⒂涗浵聛淼闹捣祷厝?#xff0c;就不會(huì)造成上面的情況。

1.8 查找指定的值(val)

在二叉樹中查找指定的值x, 如果找到則返回該節(jié)點(diǎn)的地址, 否則返回NULL。

BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* ret1 = BTreeFind(root->left, x);if (ret1 != NULL)return ret1;return BTreeFind(root->right, x);
}

舉如下一個(gè)例子：比如我們要找x == 3的節(jié)點(diǎn)，則函數(shù)的遞歸過程如下：
遞歸的難點(diǎn)就是返回值不是一下子返回到最上面(最外面)的函數(shù)，而是返回上一層調(diào)用它的函數(shù)處。

1.9 二叉樹的銷毀

銷毀二叉樹的銷毀就比較簡(jiǎn)單了, 遞歸的過程采用后續(xù)遍歷釋放節(jié)點(diǎn)：

void BTreeDestroy(BTNode* root)
{if (root == NULL)return;BTreeDestroy(root->left);BTreeDestroy(root->right);free(root);
}

鏈?zhǔn)蕉鏄溥m合于數(shù)據(jù)的存儲(chǔ)，但并不適用于數(shù)據(jù)的增刪查改。所以這里只是了解鏈?zhǔn)蕉鏄涞男再|(zhì)，以及怎樣通過遞歸去求二叉樹的節(jié)點(diǎn)、葉子結(jié)點(diǎn)、高度等。

二、層序遍歷

2.1 二叉樹的層序遍歷

除了先序遍歷、中序遍歷、后序遍歷外，還可以對(duì)二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根結(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹的根結(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根結(jié)點(diǎn)，然后從左到右訪問第2層上的結(jié)點(diǎn)，接著是第三層的結(jié)點(diǎn)，以此類推；自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。

實(shí)現(xiàn)層序遍歷最好的方法是借助數(shù)據(jù)結(jié)構(gòu): 隊(duì)列

可以看到上圖通過隊(duì)列就可以實(shí)現(xiàn)二叉樹的層序遍歷，每出隊(duì)一個(gè)元素就讓該元素的左右孩子入隊(duì)。代碼實(shí)現(xiàn)如下：(隊(duì)列的性質(zhì)是先進(jìn)先出)

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);printf("%c ", top->val);QueuePop(&q);if (top->left != NULL){QueuePush(&q, top->left);}if (top->right != NULL){QueuePush(&q, top->right);}}QueueDestroy(&q);
}

注意：這里隊(duì)列中每個(gè)節(jié)點(diǎn)存放的值(data)是二叉樹節(jié)點(diǎn)的地址。所以隊(duì)列出隊(duì)只是將隊(duì)列的頭結(jié)點(diǎn)釋放掉了，而并沒有把節(jié)點(diǎn)里存放的二叉樹節(jié)點(diǎn)指針刪掉。上面的代碼中可以看到已經(jīng)提前將隊(duì)頭節(jié)點(diǎn)的值(二叉樹節(jié)點(diǎn)的指針)存放在top里面了。

2.2 層序遍歷判斷二叉樹是否是完全二叉樹

有了層序遍歷這種方法，我們其實(shí)就可以用此方法判斷一個(gè)二叉樹是否是完全二叉樹：

bool IsCompleteBTree(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//遇到有空指針的地方就跳出循環(huán)if (front == NULL)break;QueuePush(&q,front->left);QueuePush(&q,front->right);}//只管出隊(duì) //在出隊(duì)的過程中若有不為空的指針說明不是完全二叉樹while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

三、二叉樹的性質(zhì)(補(bǔ)充)

1.若規(guī)定根結(jié)點(diǎn)所在層數(shù)為1, 則一棵非空二叉樹的第i層上最多有2^i-1個(gè)結(jié)點(diǎn).
2.若規(guī)定根結(jié)點(diǎn)所在層數(shù)為1，則深度(層數(shù))為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h-1
3.對(duì)任何一棵二叉樹, 如果度為0的葉結(jié)點(diǎn)個(gè)數(shù)為n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n2, 則有: n0=n2+1

解釋一下第三個(gè)性質(zhì)：

3.1選擇題

(1) 某完全二叉樹按層次輸出(同一層從左到右)的列為ABCDEFGH，該完全二叉樹的前序序列為 (A)
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA

(2) 某二叉樹的先序遍歷和中序遍歷如下: 先序遍歷: EFHIGJK; 中序遍歷: HFIEJKG. 則二叉樹根節(jié)點(diǎn)為 (A)
A E
B F
C G
D H

(3) 一棵二叉樹的中序遍歷序列為: badce，后序遍歷序列為: bdeca，則該二叉樹的前序歷列為 (D)
A adbce
8 decab
C debac
D abcde
記住：前序序列能確定根節(jié)點(diǎn)在最左邊，后續(xù)遍歷能確定根節(jié)點(diǎn)在最右邊，再結(jié)合中序遍歷就能分割出整體的左、根、右。將該二叉樹畫出來。

(4) 某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出(同一層從左到右)為 (A)
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

(5) 某二叉樹共有399個(gè)結(jié)點(diǎn)，其中有199個(gè)度為2的結(jié)點(diǎn)，則該二又樹中的葉子結(jié)點(diǎn)數(shù)為 (B)
A 不存在這樣的二叉柯
B 200
C 198
D 199
通過二叉樹性質(zhì)可知：該二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)為199+1 == 200

(6) 下列數(shù)據(jù)結(jié)構(gòu)中，不適合采用順序存儲(chǔ)結(jié)構(gòu)的是 (AC)
A 非完全二叉樹
B 堆
C 隊(duì)列
D 棧

(7) 在具有2n個(gè)結(jié)點(diǎn)的完全二叉樹中中，葉子結(jié)點(diǎn)個(gè)數(shù)為(A)
A n
B n+1
C n-1
D n/2

(8) 一棵完全二又樹的結(jié)點(diǎn)個(gè)數(shù)為531個(gè)，那么這棵樹的高度為 (B)
A 11
B 10
C 8
D 12