· CSDN的uu們，大家好。這里是C語言數(shù)據(jù)結(jié)構(gòu)的第十講。
· 目標(biāo)：前路坎坷，披荊斬棘，扶搖直上。
· 博客主頁：?@姬如祎
· 收錄專欄：?數(shù)據(jù)結(jié)構(gòu)與算法
?
?
目錄
1.?函數(shù)接口一覽
2.?函數(shù)接口的實現(xiàn)
2.1 BTNode* BuyNode(BTDataType x)?的實現(xiàn)
2.2?BTNode* CreateTree()?的實現(xiàn)
?2.3?void TreeDestroy(BTNode* root)?的實現(xiàn)
2.4?void PrevOrder(BTNode* root)?的實現(xiàn)
2.5?void InOrder(BTNode* root)?的實現(xiàn)
2.6?void PostOrder(BTNode* root)?的實現(xiàn)
2.7?void LevelOrder(BTNode* root)?的實現(xiàn)
2.7?int TreeSize(BTNode* root)?的實現(xiàn)
2.8?int TreeHeight(BTNode* root)?的實現(xiàn)
2.9?int TreeLevel(BTNode* root, int k)?的實現(xiàn)
?2.10?BTNode* TreeFind(BTNode* root, BTDataType x)?的實現(xiàn)
說明：因為是數(shù)據(jù)結(jié)構(gòu)初階，所以二叉樹的創(chuàng)建方式我們選擇直接開辟節(jié)點，然后手動鏈接。二叉樹真正的創(chuàng)建方式在高階的數(shù)據(jù)結(jié)構(gòu)再來實現(xiàn)。因為我們實現(xiàn)的二叉樹只是普通的二叉樹，增刪改查沒有什么意義。像哪些特殊的二叉樹，紅黑樹等的增刪改查才有意義。這里這是通過常見接口的講解來理解二叉樹遞歸的性質(zhì)。
1.?函數(shù)接口一覽
typedef int BTDataType;
typedef struct BinaryTree
{
BTDataType data;
struct BinaryTree* left;
struct BinaryTree* right;
} BTNode;
//開辟一個節(jié)點
BTNode* BuyNode(BTDataType x);
//二叉樹的手動創(chuàng)建
BTNode* CreateTree();
//二叉樹的銷毀
void TreeDestroy(BTNode* root);
//二叉樹的前序遍歷
void PrevOrder(BTNode* root);
//二叉樹的中序遍歷
void InOrder(BTNode* root);
//二叉樹的后序遍歷
void PostOrder(BTNode* root);
//二叉樹的層序遍歷
void LevelOrder(BTNode* root);
//二叉樹的節(jié)點個數(shù)
int TreeSize(BTNode* root);
//二叉樹的深度
int TreeHeight(BTNode* root);
//二叉樹第K層的節(jié)點個數(shù)
int TreeLevel(BTNode* root, int k);
//二叉樹查找節(jié)點值為X的節(jié)點
BTNode* TreeFind(BTNode* root, BTDataType x);2.?函數(shù)接口的實現(xiàn)
2.1 BTNode* BuyNode(BTDataType x)?的實現(xiàn)
這個函數(shù)和鏈表中申請節(jié)點的作用相同，均是為了方便構(gòu)建數(shù)據(jù)結(jié)構(gòu)。在向堆區(qū)申請空間后需要將該節(jié)點的左右孩子的指針初始化為NULL。
//開辟一個節(jié)點
BTNode* BuyNode(BTDataType x)
{
//堆區(qū)開辟節(jié)點
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
if (newNode == NULL)
{
perror("BuyNode::malloc");
exit(-1);
}
else
{
//節(jié)點初始化
newNode->data = x;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
}2.2?BTNode* CreateTree()?的實現(xiàn)
文章開頭我們就說明了，我們學(xué)的是最普通的二叉樹，因此為了?方便起見，我們選擇手動進(jìn)行二叉樹的構(gòu)建。方法很簡單，你只需要開辟你所需要構(gòu)建的樹的節(jié)點個數(shù)，然后將指針鏈接起來即可。這里我們構(gòu)建一顆如下圖所示的完全二叉樹。
//二叉樹的手動創(chuàng)建
BTNode* CreateTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
BTNode* node7 = BuyNode(7);
BTNode* node8 = BuyNode(8);
BTNode* node9 = BuyNode(9);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;
node4->left = node8;
node4->right = node9;
return node1;
}?2.3?void TreeDestroy(BTNode* root)?的實現(xiàn)
二叉樹的初階內(nèi)容不涉及數(shù)據(jù)的增刪改查，我們學(xué)習(xí)的主要內(nèi)容就是理解二叉樹的遞歸特性。為將來學(xué)習(xí)特殊的二叉樹打好基礎(chǔ)。因此下面開始的函數(shù)均選擇使用遞歸來實現(xiàn)。
這個函數(shù)的實現(xiàn)比較簡單，但是釋放節(jié)點的順序還是有講究的，如下圖，我們要對這三個節(jié)點進(jìn)行釋放，我們有三個選擇：先釋放4；先釋放8；先釋放9。顯然我們不會選擇先釋放4，因為如果你想要先釋放4，那么你還需要用變量先保存4的左右孩子，這樣就顯得比較麻煩啦。至于是先釋放8.還是先釋放9，就沒有優(yōu)劣之差啦。
?在釋放樹的節(jié)點時，顯然只能從葉子節(jié)點開始釋放，這恰恰符合了遞歸遞去歸來的特性，因此我們選擇使用遞歸來實現(xiàn)。通過遞歸，先到達(dá)葉子節(jié)點，我們不妨先釋放左孩子，再釋放右孩子，如果左右孩子不為空，我們就釋放他們，然后再釋放左右孩子的雙親節(jié)點，釋放完成后逐步向上返回，直到將根結(jié)點釋放。下圖展示了8這個節(jié)點的銷毀過程，請結(jié)合代碼進(jìn)行理解。
//二叉樹的銷毀
void TreeDestroy(BTNode* root)
{
if (root == NULL)
return;
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
root = NULL;
}2.4?void PrevOrder(BTNode* root)?的實現(xiàn)
?前序遍歷，就是在遍歷二叉樹時先訪問根結(jié)點，在訪問左子樹，最后訪問右子樹。二叉樹的遞歸邏輯都是相似的，可以結(jié)合下面的這張圖來理解前序遍歷。
?在進(jìn)行前序遍歷的時候，他的本質(zhì)是會去訪問葉子節(jié)點左右孩子的那兩個NULL指針的，因此在訪問到NULL時，我們可以將NULL打印出來，這樣能更加深刻的理解前序遍歷的本質(zhì)。
//二叉樹的前序遍歷
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
2.5?void InOrder(BTNode* root)?的實現(xiàn)
中序遍歷就是在遍歷二叉樹的時候先訪問左子樹，再訪問根結(jié)點，最后訪問右子樹。思路就是二叉樹的遞歸思路，代碼只需要將前序遍歷代碼的順序交換一下即可。
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}2.6?void PostOrder(BTNode* root)?的實現(xiàn)
后續(xù)遍歷就是指在遍歷二叉樹時先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點。
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}2.7?void LevelOrder(BTNode* root)?的實現(xiàn)
層序遍歷就是將一棵樹按照每一層每一層的方式進(jìn)行遍歷，下圖中的二叉樹的層序遍歷結(jié)果就是：1 2 3 4 5 6 7 8 9
這該怎么做呢？其實很簡單，我們只需要維護一個隊列，?一開始呢，先將根結(jié)點入隊列。然后進(jìn)入一個循環(huán)，循環(huán)繼續(xù)的條件就是隊列不為空，然后逐步取出隊頭的元素，如果隊頭元素的左右孩子有不為空的，就將其入隊列，依次類推，節(jié)點從隊列中出來的順序就是層序遍歷的結(jié)果。
至于隊列的選擇，我們選擇使用數(shù)組模擬實現(xiàn)隊列，因為C語言嘛，不像其他語言那么方便。
關(guān)于數(shù)組模擬實現(xiàn)隊列，請參考：數(shù)據(jù)模擬實現(xiàn)隊列
2.7?int TreeSize(BTNode* root)?的實現(xiàn)
你可能會想，我們維護一個變量Size，然后將二叉樹遍歷一遍，每遍歷到一個節(jié)點就將Size++，這樣就能求出二叉樹的節(jié)點個數(shù)了。這沒問題，很好，只不過這種方法有一點值得注意，如果你不使用全局或者靜態(tài)變量，而是將Size作為參數(shù)傳遞給TreeSize函數(shù)，那么，一定記得傳指針哦！具體原因想必大家都懂啦！俺們都是C語言學(xué)完的人了！但是這里不推薦使用全局和靜態(tài)的變量。如果你要對多棵樹調(diào)用該方法，那么你還得重新初始化這個全局變量，比較麻煩。
這里我們就不對上面的這種方法做實現(xiàn)啦！這里還有一種方法：整個二叉樹節(jié)點的個數(shù)就等于左子樹節(jié)點的個數(shù) +?右子樹節(jié)點的個數(shù) + 1 (這個1就是根節(jié)點啦)。這便是分治思想。將大的問題拆解成小的問題(說實話還有一點動態(tài)規(guī)劃的味道)。
int TreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
2.8?int TreeHeight(BTNode* root)?的實現(xiàn)
我們理解了求解TreeSize的思路，TreeHeight就是信手拈來的事情。同樣地，我們利用分治的思想：樹的深度 =?左右子樹中深度較大的那一個 + 1，是不是很簡單嘞。
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int left = TreeHeight(root->left);
int right = TreeHeight(root->right);
return left > right ? left + 1 : right + 1;
}2.9?int TreeLevel(BTNode* root, int k)?的實現(xiàn)
求解二叉樹第K層的節(jié)點個數(shù)，怎么用分治的思想解決呢？上圖解
?這下是不是有思路了呢？當(dāng)我們遞歸到所求節(jié)點總數(shù)的那一層時，對于K = 1，而這個時候呢，我們就不要向下遞歸啦！這層有節(jié)點的話，遞歸到此層的每一個節(jié)點返回1就行啦！
int TreeLevel(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}?2.10?BTNode* TreeFind(BTNode* root, BTDataType x)?的實現(xiàn)
咦，不是說普通的二叉樹不學(xué)增刪改查嗎！哈哈，勉強看一個吧，這里有一個地方值得注意，TreeFind函數(shù)的返回值不是bool值而是查找到的節(jié)點，如果有修改的需要，我們就能夠在查找的同時對節(jié)點的值進(jìn)行修改啦！是不是很方便。
怎么實現(xiàn)這個函數(shù)呢？其實很簡單，我們先對每一層遞歸的根結(jié)點進(jìn)行判斷，如果這個時候根結(jié)點的data就等于x那么直接返回結(jié)果就行。如果根結(jié)點的data值不等于x呢？
我們就在根結(jié)點的左子樹中去找，也就是往左子樹遞歸、如果在左子樹找的結(jié)果不為空，說明在左子樹中找到了data值為x的節(jié)點，返回該節(jié)點即可！
如果左子樹沒找到，就在右子樹中去找，也就是往右子樹去遞歸。如果在右子樹找的結(jié)果不為空，說明在右子樹中找到了data值為x的節(jié)點，返回該節(jié)點即可！如果在右子樹中沒有找到嘞，說明左右子樹都沒找到，返回NULL即可。文章來源：http://www.zghlxwxcb.cn/news/detail-402740.html
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
return root;
BTNode* left = TreeFind(root->left, x);
if (left)
return left;
BTNode* right = TreeFind(root->right, x);
if (right)
return right;
return NULL;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-402740.html
到了這里，關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)初階(10)----二叉樹的實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
