?個(gè)人主頁：日刷百題
系列專欄：〖C語言小游戲〗〖Linux〗〖數(shù)據(jù)結(jié)構(gòu)〗?〖C語言〗
??歡迎各位→點(diǎn)贊??+收藏??+留言????
一、二叉樹的創(chuàng)建
當(dāng)然為了后續(xù)內(nèi)容能夠銜接，我們先手動(dòng)創(chuàng)建一個(gè)固定的樹，就是上面這棵樹，后續(xù)內(nèi)容全部圍繞這棵樹
typedef int DataType;
typedef struct TreeNode
{
DataType data;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
TreeNode* BuyNode(int x)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
if (node == NULL)
{
perror("malloc fail:");
return NULL;
}
node->data = x;
node->left = node->right = NULL;
}
TreeNode* CreatTree()
{
TreeNode* node1 = BuyNode(1);
TreeNode* node2 = BuyNode(2);
TreeNode* node3 = BuyNode(3);
TreeNode* node4 = BuyNode(4);
TreeNode* node5 = BuyNode(5);
TreeNode* node6= BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}現(xiàn)在開始講如何用前序遍歷方式來進(jìn)行創(chuàng)建二叉樹，這里給倆種創(chuàng)建方法。
1.1? 返回根節(jié)點(diǎn)指針創(chuàng)建
注：我們用前序遍歷方式輸入數(shù)字，-1代表空，上面的二叉樹可寫為：1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1
TreeNode* CreatTree()
{
int i;
scanf("%d", &i);
if (i == -1)
{
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
if (root == NULL)
{
perror("malloc fail:");
exit(-1);
}
root->data = i;
root->left = CreatTree();
root->right = CreatTree();
return root;
}
注：return root 是不能省略的，遞歸返回時(shí)，遇到空返回；或者構(gòu)建完子數(shù)，返回根節(jié)點(diǎn)，作為上一級左子樹，構(gòu)建完子樹，返回根節(jié)點(diǎn)，作為上一級右子樹，依次遞歸回去，直到返回整個(gè)數(shù)的根節(jié)點(diǎn)
1.2 二級指針傳參創(chuàng)建
同樣的，依然構(gòu)建上面的而二叉樹，用前序遍歷方式輸入數(shù)字，-1代表空，上面的二叉樹可寫為：1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1
void CreatTree(TreeNode** root)
{
int i;
scanf("%d", &i);
if (i == -1)
{
*root = NULL;
}
else
{
*root = (TreeNode*)malloc(sizeof(TreeNode));
if (*root == NULL)
{
perror("malloc fail:");
exit(-1);
}
(*root)->data = i;
CreatTree(&((*root)->left));
CreatTree(&((*root)->right));
}
}?注：二級指針傳參可以改變一級指針的指向，同樣的，這里創(chuàng)建好根節(jié)點(diǎn)后，創(chuàng)造左子樹，在創(chuàng)造右子樹，依次遞歸下去。
二、二叉樹的遍歷
我們先從最簡單的操作----遍歷學(xué)起。所謂二叉樹遍歷(Traversal)就是按照某種特定的規(guī)則，依次對二叉樹中的結(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)，再遍歷左子樹，最后遍歷右子樹。而對于子樹的遍歷，也服從上述規(guī)則。利用遞歸，我們可以很快地寫出代碼：
// 二叉樹前序遍歷
void PreOrder(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return ;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}便于我們更好的理解，我們畫出遞歸展開圖
2.2 中序遍歷
中序遍歷（Inorder Traversal）又稱中根遍歷，即先遍歷左子樹，再遍歷根結(jié)點(diǎn)，最后遍歷右子樹。同樣，子樹的遍歷規(guī)則也是如此。遞歸代碼如下：
// 二叉樹中序遍歷
void InOrder(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return ;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}2.3 后序遍歷
后序遍歷（Inorder Traversal）又稱后根遍歷，即先遍歷左子樹，再遍歷右子樹，最后遍歷根結(jié)點(diǎn)。遞歸代碼如下：
// 二叉樹后序遍歷
void PostOrder(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return ;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}2.4??層序遍歷
//層序遍歷
void LevelOrder(TreeNode* root)
{
Queue pq;
QueueInit(&pq);
if (root == NULL)
{
QueueDestroy(&pq);
return;
}
QueuePush(&pq,root);
while (!QueueEmpty(&pq))
{
TreeNode* front= QueueFront(&pq);
printf("%d ", front->data);
QueuePop(&pq);
if (front->left!= NULL)
{
QueuePush(&pq, front->left);
}
if (front->right != NULL)
{
QueuePush(&pq, front->right);
}
}
QueueDestroy(&pq);
}
思考：當(dāng)然層序遍歷這里有一個(gè)變形，我們能不能將二叉樹每一層打印單獨(dú)放一行，該怎么做呢？
思路：
（1）設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1，第一層根節(jié)點(diǎn)進(jìn)隊(duì)列，隊(duì)列元素個(gè)數(shù)為1，size==1
（2）每出隊(duì)列一次，size--,根節(jié)點(diǎn)出完隊(duì)列，倆個(gè)子節(jié)點(diǎn)進(jìn)隊(duì)列,此時(shí)隊(duì)列元素個(gè)數(shù)為第二層節(jié)點(diǎn)個(gè)數(shù)，size==2
（3）當(dāng)我們出隊(duì)列size次，把第二層元素出完，隊(duì)列剩下的元素是第三層節(jié)點(diǎn)，size==QueueSize
以此類推，以size為循環(huán)條件，則可實(shí)現(xiàn)每層單獨(dú)打印一行
void LevelOrder(TreeNode* root)
{
Queue pq;
QueueInit(&pq);
if (root == NULL)
{
QueueDestroy(&pq);
return;
}
QueuePush(&pq,root);
int size = 1;
while (!QueueEmpty(&pq))
{
while (size--)
{
TreeNode* front = QueueFront(&pq);
printf("%d ", front->data);
QueuePop(&pq);
if (front->left != NULL)
{
QueuePush(&pq, front->left);
}
if (front->right != NULL)
{
QueuePush(&pq, front->right);
}
}
size = QueueSize(&pq);
printf("\n");
}
QueueDestroy(&pq);
}
三、二叉樹的結(jié)點(diǎn)
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即可。遞歸代碼如下：
// 二叉樹節(jié)點(diǎn)個(gè)數(shù)
int TreeSize(TreeNode* 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)）。
?
// 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeafSize(TreeNode* 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)。（注：當(dāng)前節(jié)點(diǎn)為第一層）
（1）若為空樹，無論哪層節(jié)點(diǎn)數(shù)都是0
（2）若不是空樹且k==1,則只有一個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)）
// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int TreeLevelKSize(TreeNode* root, int k)
{
assert(k > 0);
if (root!=NULL&&k == 1)
{
return 1;
}
if (root == NULL)
{
return 0;
}
if (k > 1)
{
return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
}
// 判斷二叉樹是否是完全二叉樹
bool TreeComplete(TreeNode* root)
{
Queue pq;
QueueInit(&pq);
if (root == NULL)
{
QueueDestroy(&pq);
return;
}
QueuePush(&pq, root);
while (!QueueEmpty(&pq))
{
TreeNode* front = QueueFront(&pq);
QueuePop(&pq);
if (front == NULL)
{
break;
}
QueuePush(&pq, front->left);
QueuePush(&pq, front->right);
}
while (!QueueEmpty(&pq))
{
TreeNode* front = QueueFront(&pq);
QueuePop(&pq);
if (front != NULL)
{
return false;
}
}
QueueDestroy(&pq);
return true;
}四、二叉樹的查找
二叉樹的查找本質(zhì)上就是一種遍歷，只不過是將之前的打印操作換為查找操作而已。我們可以使用前序遍歷來進(jìn)行查找：
（1）先比較根結(jié)點(diǎn)是否為我們要查找的結(jié)點(diǎn)，如果是，返回根節(jié)點(diǎn)地址
（2）如果不是，遍歷左子樹，如果左子樹是，直接返回節(jié)點(diǎn)地址；不是則遍歷右子樹，如果右子樹是，直接返回節(jié)點(diǎn)地址，不是返回空，說明左右子樹都沒找到。
// 二叉樹查找值為x的節(jié)點(diǎn)
TreeNode* TreeFind(TreeNode* root, DataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
TreeNode* node1 = TreeFind(root->left, x);
if (node1)
{
return node1;
}
TreeNode* node2 = TreeFind(root->right, x);
if (node2)
{
return node2;
}
return NULL;
}五、二叉樹的高度/深度
樹中結(jié)點(diǎn)的最大層次稱為二叉樹的高度。因此，一顆二叉樹的高度我們可以看作是
1(根結(jié)點(diǎn))+左右子樹高度的較大值。層層遞歸下去直到遇到空樹返回0即可，
這里值得注意的是：不要寫成
return TreeHeight(root->left)>TreeHeight(root->right) ?
TreeHeight(root->left)+1:TreeHeight(root->right)+1;
}這里比較好左右子樹較大的一顆后，又會從新遞歸較大那顆子樹高度，會造成重復(fù)計(jì)算，時(shí)間復(fù)雜度增高。
我們要保存好左右子樹層數(shù)，避免重復(fù)計(jì)算，代碼如下：
//二叉樹的高度
int TreeHeight(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHeight(root->left);
int right = TreeHeight(root->right);
return left>right ?
left+1:right+1;
}六、完全二叉樹的判斷
這里的思路利用了層序遍歷，不同的是，將空節(jié)點(diǎn)指針也入隊(duì)列，當(dāng)我們遇到第一個(gè)空節(jié)點(diǎn)指針則退出循環(huán)，然后對隊(duì)列進(jìn)行檢測，若第一個(gè)空節(jié)點(diǎn)指針以后全都是空，則為完全二叉樹，反之，不為完全二叉樹。
注：當(dāng)在隊(duì)列遇到第一個(gè)空節(jié)點(diǎn)指針時(shí)，二叉樹中空節(jié)點(diǎn)指針之后所有非空節(jié)點(diǎn)指針全部進(jìn)隊(duì)列
思路解析圖如下：
代碼如下：
// 判斷二叉樹是否是完全二叉樹
bool TreeComplete(TreeNode* root)
{
Queue pq;
QueueInit(&pq);
if (root == NULL)
{
QueueDestroy(&pq);
return;
}
QueuePush(&pq, root);
while (!QueueEmpty(&pq))
{
TreeNode* front = QueueFront(&pq);
QueuePop(&pq);
if (front == NULL)
{
break;
}
QueuePush(&pq, front->left);
QueuePush(&pq, front->right);
}
while (!QueueEmpty(&pq))
{
TreeNode* front = QueueFront(&pq);
QueuePop(&pq);
if (front != NULL)
{
return false;
}
}
QueueDestroy(&pq);
return true;
}?七、二叉樹的銷毀
7.1 一級指針傳參銷毀
同樣的，和創(chuàng)建節(jié)點(diǎn)一樣，我們給出倆個(gè)銷毀方式：
(1)一種是傳一級指針方式，這種方式不是改變根節(jié)點(diǎn)的指向，需要在銷毀函數(shù)結(jié)束后，將root置為NULL
void TreeDestroy(TreeNode* root)//出來將root=NULL
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}7.2?二級指針傳參銷毀?
(2)另一種是傳二級指針，直接在函數(shù)內(nèi)部將每一個(gè)銷毀的節(jié)點(diǎn)指針置為NULL.
void TreeDestroy(TreeNode** root)
{
if (*root == NULL)
{
return;
}
TreeDestroy(&(*root)->left);
TreeDestroy(&(*root)->right);
free(*root);
*root = NULL;
}?總結(jié)：本篇文章將二叉樹的基礎(chǔ)知識差不多囊括了，后續(xù)的話還需要大量練習(xí)做鞏固加強(qiáng)，遞歸比較抽象難以理解，需要?jiǎng)邮之嬤f歸展開圖進(jìn)行幫助理解。
希望大家閱讀完可以有所收獲，同時(shí)也感謝各位鐵汁們的支持。文章有任何問題可以在評論區(qū)留言，百題一定會認(rèn)真閱讀！文章來源：http://www.zghlxwxcb.cn/news/detail-751728.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-751728.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
