🔥博客主頁： 小羊失眠啦.
🎥系列專欄：《C語言》 《數(shù)據(jù)結(jié)構(gòu)》 《Linux》《Cpolar》
??感謝大家點(diǎn)贊👍收藏?評(píng)論??

---

一、前置說明

在學(xué)習(xí)二叉樹各種各樣的操作前，我們先來回顧一下二叉樹的概念：

二叉樹是度不超過2的樹，由根結(jié)點(diǎn)和左右2個(gè)子樹組成，每個(gè)子樹也可以看作一顆二叉樹，又可以拆分為根結(jié)點(diǎn)和左右兩顆子樹…

是不是很熟悉，一個(gè)大問題可以拆分為兩個(gè)子問題，每個(gè)子問題又可以拆分為更小的子問題，這樣層層拆分到不可拆分（遇到空樹）的過程，不就是遞歸嗎！因此，我們可以得出：

樹是遞歸定義的，后續(xù)樹的各種操作正是圍繞著這一點(diǎn)進(jìn)行的。

二、二叉樹的遍歷

我們先從最簡(jiǎn)單的操作----遍歷學(xué)起。所謂二叉樹遍歷(Traversal)就是按照某種特定的規(guī)則，依次對(duì)二叉樹中的結(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)有且只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。二叉樹的遍歷分為四種：前序遍歷、中序遍歷、后序遍歷和層序遍歷。

2.1 前序遍歷

前序遍歷（Preorder Traversal）又稱先根遍歷，即先遍歷根結(jié)點(diǎn)，再遍歷左子樹，最后遍歷右子樹。而對(duì)于子樹的遍歷，也服從上述規(guī)則。利用遞歸，我們可以很快地寫出代碼：

//前序遍歷
void PrevOrder(BTNode* root) {//遇到空樹，遞歸終點(diǎn)if (root == NULL) {printf("NULL ");return;}//對(duì)根節(jié)點(diǎn)進(jìn)行操作（此處為打印）printf("%d ", root->val);//遞歸遍歷左子樹PrevOrder(root->left);//遞歸遍歷右子樹PrevOrder(root->right);
}

為了更好地理解這個(gè)過程，我們可以畫出遞歸展開圖如下：

2.2 中序遍歷

中序遍歷（Inorder Traversal）又稱中根遍歷，即先遍歷左子樹，再遍歷根結(jié)點(diǎn)，最后遍歷右子樹。同樣，子樹的遍歷規(guī)則也是如此。遞歸代碼如下：

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

2.3 后序遍歷

后序遍歷（Inorder Traversal）又稱后根遍歷，即先遍歷左子樹，再遍歷右子樹，最后遍歷根結(jié)點(diǎn)。照葫蘆畫瓢，遞歸代碼如下：

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

2.4 層序遍歷

除了上面的前中后序遍歷，還可以對(duì)二叉樹進(jìn)行層序遍歷。所謂層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā)，首先訪問第1層的根節(jié)點(diǎn)，然后從左到右訪問第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推。這樣自上而下，自左向右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。

與前面三種遍歷不同，層序遍歷屬于廣度優(yōu)先遍歷，因此我們可以利用隊(duì)列先進(jìn)先出的特性，將每個(gè)結(jié)點(diǎn)一層一層依次入隊(duì)，然后依次出隊(duì)進(jìn)行操作即可。具體演示及代碼如下：

void LevelOrder(BTNode* root)
{Que q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->val);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);QueuePop(&q);}printf("\n");QueueDestroy(&q);
}

三、二叉樹的結(jié)點(diǎn)個(gè)數(shù)

3.1 二叉樹的總結(jié)點(diǎn)數(shù)

一顆二叉樹的結(jié)點(diǎn)數(shù)我們可以看作是根結(jié)點(diǎn)+左子樹結(jié)點(diǎn)數(shù)+右子樹結(jié)點(diǎn)數(shù)，那左右子樹的結(jié)點(diǎn)數(shù)又是多少呢？按照相同的方法繼續(xù)拆分，層層遞歸直到左右子樹為空樹，返回空樹的結(jié)點(diǎn)數(shù)0即可。遞歸代碼如下：

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

3.2 二叉樹的葉子結(jié)點(diǎn)數(shù)

左右子樹都為空的結(jié)點(diǎn)即是葉子結(jié)點(diǎn)。這里分為兩種情況：左右子樹都為空和左右子樹不都為空。

1. 當(dāng)左右子樹都為空時(shí)，則這顆樹的葉子結(jié)點(diǎn)數(shù)為1(根節(jié)點(diǎn))。

2. 當(dāng)左右子樹不都為空，即根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)時(shí)，這棵樹的葉子結(jié)點(diǎn)數(shù)就為左子樹葉子結(jié)點(diǎn)數(shù)+右子樹葉子結(jié)點(diǎn)數(shù)（空樹沒有葉子結(jié)點(diǎn)）。

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

3.3 二叉樹第k層結(jié)點(diǎn)數(shù)

類似的，一顆樹第k層的結(jié)點(diǎn)數(shù)我們可以拆分為其左子樹第k-1層結(jié)點(diǎn)+右子樹第k-1層結(jié)點(diǎn)。這樣層層遞歸下去，直到k==1求樹的第1層結(jié)點(diǎn)數(shù)時(shí)返回1(樹的第1層只有根結(jié)點(diǎn))，而如果在遞歸過程中遇到空樹就返回0(空樹沒有結(jié)點(diǎn))。例如下面一顆樹：

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

四、二叉樹的高度/深度

樹中結(jié)點(diǎn)的最大層次稱為二叉樹的高度。因此，一顆二叉樹的高度我們可以看作是

1(根結(jié)點(diǎn))+左右子樹高度的較大值。層層遞歸下去直到遇到空樹返回0即可，遞歸代碼如下：

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

五、二叉樹的查找

二叉樹的查找本質(zhì)上就是一種遍歷，只不過是將之前的打印操作換為查找操作而已。我們可以使用前序遍歷來進(jìn)行查找，先比較根結(jié)點(diǎn)是否為我們要查找的結(jié)點(diǎn)，如果是，之間返回；如果不是，遍歷左子樹和右子樹，返回其查找的結(jié)果；如果都找不到，返回空指針。代碼如下：

// 二叉樹查找值為x的結(jié)點(diǎn)
BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* ret = NULL;ret = TreeFind(root->left, x);if (ret)return ret;ret = TreeFind(root->right, x);if (ret)return ret;return NULL;
}

六、二叉樹的創(chuàng)建和銷毀

最后，我們?cè)賮砜纯慈绾蝸韯?chuàng)建和銷毀一顆二叉樹。我們前面說過：二叉樹是遞歸定義的。有了前面的基礎(chǔ)，二叉樹的創(chuàng)建和銷毀也就不是什么難事了。

BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->val = x;node->left = NULL;node->right = NULL;return node;
}// 二叉樹銷毀
void TreeDestroy(BTNode* root)
{if (root == NULL){return;}TreeDestroy(root->left);TreeDestroy(root->right);free(root);//root = NULL;
}

本次的內(nèi)容到這里就結(jié)束啦。希望大家閱讀完可以有所收獲，同時(shí)也感謝各位鐵汁們的支持。文章有任何問題可以在評(píng)論區(qū)留言，小羊一定認(rèn)真修改，寫出更好的文章~~