??博客主頁(yè)： 小羊失眠啦.
??系列專(zhuān)欄：《C語(yǔ)言》 《數(shù)據(jù)結(jié)構(gòu)》 《Linux》《Cpolar》
??感謝大家點(diǎn)贊??收藏?評(píng)論??
一、前置說(shuō)明
在學(xué)習(xí)二叉樹(shù)各種各樣的操作前，我們先來(lái)回顧一下二叉樹(shù)的概念：
二叉樹(shù)是度不超過(guò)2的樹(shù)，由根結(jié)點(diǎn)和左右2個(gè)子樹(shù)組成，每個(gè)子樹(shù)也可以看作一顆二叉樹(shù)，又可以拆分為根結(jié)點(diǎn)和左右兩顆子樹(shù)…
是不是很熟悉，一個(gè)大問(wèn)題可以拆分為兩個(gè)子問(wèn)題，每個(gè)子問(wèn)題又可以拆分為更小的子問(wèn)題，這樣層層拆分到不可拆分（遇到空樹(shù)）的過(guò)程，不就是遞歸嗎！因此，我們可以得出：
樹(shù)是遞歸定義的，后續(xù)樹(shù)的各種操作正是圍繞著這一點(diǎn)進(jìn)行的。
二、二叉樹(shù)的遍歷
我們先從最簡(jiǎn)單的操作----遍歷學(xué)起。所謂二叉樹(shù)遍歷(Traversal)就是按照某種特定的規(guī)則，依次對(duì)二叉樹(shù)中的結(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)有且只操作一次。訪問(wèn)結(jié)點(diǎn)所做的操作依賴(lài)于具體的應(yīng)用問(wèn)題。 遍歷是二叉樹(shù)上最重要的運(yùn)算之一，也是二叉樹(shù)上進(jìn)行其它運(yùn)算的基礎(chǔ)。二叉樹(shù)的遍歷分為四種：前序遍歷、中序遍歷、后序遍歷和層序遍歷。
2.1 前序遍歷
前序遍歷（Preorder Traversal）又稱(chēng)先根遍歷，即先遍歷根結(jié)點(diǎn)，再遍歷左子樹(shù)，最后遍歷右子樹(shù)。而對(duì)于子樹(shù)的遍歷，也服從上述規(guī)則。利用遞歸，我們可以很快地寫(xiě)出代碼：
//前序遍歷
void PrevOrder(BTNode* root) {
//遇到空樹(shù)，遞歸終點(diǎn)
if (root == NULL) {
printf("NULL ");
return;
}
//對(duì)根節(jié)點(diǎn)進(jìn)行操作（此處為打?。?/span>
printf("%d ", root->val);
//遞歸遍歷左子樹(shù)
PrevOrder(root->left);
//遞歸遍歷右子樹(shù)
PrevOrder(root->right);
}
為了更好地理解這個(gè)過(guò)程，我們可以畫(huà)出遞歸展開(kāi)圖如下：
2.2 中序遍歷
中序遍歷（Inorder Traversal）又稱(chēng)中根遍歷，即先遍歷左子樹(shù)，再遍歷根結(jié)點(diǎn)，最后遍歷右子樹(shù)。同樣，子樹(shù)的遍歷規(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）又稱(chēng)后根遍歷，即先遍歷左子樹(shù)，再遍歷右子樹(shù)，最后遍歷根結(jié)點(diǎn)。照葫蘆畫(huà)瓢，遞歸代碼如下：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
2.4 層序遍歷
除了上面的前中后序遍歷，還可以對(duì)二叉樹(shù)進(jìn)行層序遍歷。所謂層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，首先訪問(wèn)第1層的根節(jié)點(diǎn)，然后從左到右訪問(wèn)第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類(lèi)推。這樣自上而下，自左向右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的過(guò)程就是層序遍歷。
與前面三種遍歷不同，層序遍歷屬于廣度優(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);
}
三、二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)
3.1 二叉樹(shù)的總結(jié)點(diǎn)數(shù)
一顆二叉樹(shù)的結(jié)點(diǎn)數(shù)我們可以看作是根結(jié)點(diǎn)+左子樹(shù)結(jié)點(diǎn)數(shù)+右子樹(shù)結(jié)點(diǎn)數(shù)，那左右子樹(shù)的結(jié)點(diǎn)數(shù)又是多少呢？按照相同的方法繼續(xù)拆分，層層遞歸直到左右子樹(shù)為空樹(shù)，返回空樹(shù)的結(jié)點(diǎn)數(shù)0即可。遞歸代碼如下：
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
3.2 二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)
左右子樹(shù)都為空的結(jié)點(diǎn)即是葉子結(jié)點(diǎn)。這里分為兩種情況：左右子樹(shù)都為空和左右子樹(shù)不都為空。
-
當(dāng)左右子樹(shù)都為空時(shí)，則這顆樹(shù)的葉子結(jié)點(diǎn)數(shù)為1(根節(jié)點(diǎn))。
-
當(dāng)左右子樹(shù)不都為空，即根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)時(shí)，這棵樹(shù)的葉子結(jié)點(diǎn)數(shù)就為
左子樹(shù)葉子結(jié)點(diǎn)數(shù)+右子樹(shù)葉子結(jié)點(diǎn)數(shù)（空樹(shù)沒(méi)有葉子結(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 二叉樹(shù)第k層結(jié)點(diǎn)數(shù)
類(lèi)似的，一顆樹(shù)第k層的結(jié)點(diǎn)數(shù)我們可以拆分為其左子樹(shù)第k-1層結(jié)點(diǎn)+右子樹(shù)第k-1層結(jié)點(diǎn)。這樣層層遞歸下去，直到k==1求樹(shù)的第1層結(jié)點(diǎn)數(shù)時(shí)返回1(樹(shù)的第1層只有根結(jié)點(diǎn))，而如果在遞歸過(guò)程中遇到空樹(shù)就返回0(空樹(shù)沒(méi)有結(jié)點(diǎn))。例如下面一顆樹(shù)：
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);
}
四、二叉樹(shù)的高度/深度
樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為二叉樹(shù)的高度。因此，一顆二叉樹(shù)的高度我們可以看作是
1(根結(jié)點(diǎn))+左右子樹(shù)高度的較大值。層層遞歸下去直到遇到空樹(shù)返回0即可，遞歸代碼如下：
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}
五、二叉樹(shù)的查找
二叉樹(shù)的查找本質(zhì)上就是一種遍歷，只不過(guò)是將之前的打印操作換為查找操作而已。我們可以使用前序遍歷來(lái)進(jìn)行查找，先比較根結(jié)點(diǎn)是否為我們要查找的結(jié)點(diǎn)，如果是，之間返回；如果不是，遍歷左子樹(shù)和右子樹(shù)，返回其查找的結(jié)果；如果都找不到，返回空指針。代碼如下：
// 二叉樹(shù)查找值為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;
}
六、二叉樹(shù)的創(chuàng)建和銷(xiāo)毀
最后，我們?cè)賮?lái)看看如何來(lái)創(chuàng)建和銷(xiāo)毀一顆二叉樹(shù)。我們前面說(shuō)過(guò)：二叉樹(shù)是遞歸定義的。有了前面的基礎(chǔ)，二叉樹(shù)的創(chuàng)建和銷(xiāo)毀也就不是什么難事了。
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;
}
// 二叉樹(shù)銷(xiāo)毀
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
//root = NULL;
}
本次的內(nèi)容到這里就結(jié)束啦。希望大家閱讀完可以有所收獲，同時(shí)也感謝各位鐵汁們的支持。文章有任何問(wèn)題可以在評(píng)論區(qū)留言，小羊一定認(rèn)真修改，寫(xiě)出更好的文章~~文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-763183.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-763183.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹(shù)之鏈?zhǔn)浇Y(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
