個(gè)人主頁(yè)：點(diǎn)我進(jìn)入主頁(yè)
專欄分類：C語言初階? ? ??C語言程序設(shè)計(jì)————KTV? ? ? ?C語言小游戲? ? ?C語言進(jìn)階
C語言刷題? ? ? ?數(shù)據(jù)結(jié)構(gòu)初階? ??Linux
歡迎大家點(diǎn)贊，評(píng)論，收藏。
一起努力,共赴大廠。
目錄
1.前言?
2.二叉樹各個(gè)功能代碼實(shí)現(xiàn)
2.1二叉樹結(jié)構(gòu)體
2.2二叉樹的前序遍歷?
2.3中序遍歷?
2.4后序遍歷
2.5計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)
2.6計(jì)算二叉樹葉子節(jié)點(diǎn)的個(gè)數(shù)?
2.7計(jì)算二叉樹的深度
2.8計(jì)算第k層的節(jié)點(diǎn)個(gè)數(shù)
2.9層序遍歷
2.10層序遍歷變式
2.11判斷是否為完全二叉樹
2.12二叉樹內(nèi)存釋放
2.13樹的創(chuàng)建
3.二叉樹的性質(zhì)
4.總結(jié)
1.前言?
? ? ? ? 我在前面寫過關(guān)于順序表，棧，隊(duì)列，堆的存儲(chǔ)結(jié)構(gòu)，現(xiàn)在我們還有一種一對(duì)多的存儲(chǔ)結(jié)構(gòu)樹，在堆的博客中我寫過一些樹的概念，樹的增刪查改在我們的應(yīng)用中并不實(shí)用，其中有用的是查找樹，但是查找樹的實(shí)現(xiàn)我們還沒有能力去實(shí)現(xiàn)，樹的實(shí)現(xiàn)可以用順序表實(shí)現(xiàn)也可以用鏈表去實(shí)現(xiàn)，這次我們用鏈?zhǔn)蕉鏄淙?shí)現(xiàn)，利用順序表實(shí)現(xiàn)可以看堆的內(nèi)容。在這篇文章中我主要給大家?guī)黻P(guān)于二叉樹的創(chuàng)建，樹的一些性質(zhì)，樹的前序中序后序?qū)有虮闅v，求樹的節(jié)點(diǎn)個(gè)數(shù)，葉子節(jié)點(diǎn)個(gè)數(shù)，樹的深度，第k層節(jié)點(diǎn)的個(gè)數(shù)，判斷是不是完全二叉樹，在這些中大部分需要用遞歸，我會(huì)給搭建展示部分功能的遞歸展開圖來幫助大家理解，在學(xué)習(xí)這寫內(nèi)容中我建議大家可以會(huì)回憶一下遞歸的內(nèi)容，是不是看到遞歸就覺得畏懼嗎？其實(shí)我們只需要多去感受一下其中的思路與思想，不用過多的去畏懼遞歸，接下來就讓我們看看其中是如何用遞歸去實(shí)現(xiàn)吧。
2.二叉樹各個(gè)功能代碼實(shí)現(xiàn)
2.1二叉樹結(jié)構(gòu)體
typedef struct BiTreeNode {
int val;
struct BiTreeNode* left, * right;
}BTNode;結(jié)構(gòu)體的內(nèi)容包括結(jié)構(gòu)體的內(nèi)容，指向二叉樹的左孩子的指針，指向二叉樹的右孩子的指針。我給大家來看一下二叉樹的大概的模型
2.2二叉樹的前序遍歷?
void PrevorderBTNode(BTNode* root)
{
if (root == NULL)
return;
printf("%d ", root->val);
PrevorderBTNode(root->left);
PrevorderBTNode(root->right);
}例如我們利用上面的二叉樹進(jìn)行模擬
我們可以根據(jù)代碼展開圖進(jìn)行一步步實(shí)現(xiàn)代碼實(shí)現(xiàn)的過程，最好我們自己去畫一畫代碼展開圖這樣對(duì)于我們?nèi)チ私膺f歸會(huì)有非常好的作用。
2.3中序遍歷?
void InorderBTNode(BTNode* root)
{
if (root == NULL)
return;
InorderBTNode(root->left);
printf("%d ", root->val);
InorderBTNode(root->right);
}我們的代碼展開圖如下
?我們可以看到我們的中序遍歷代碼和前序遍歷代碼大致相同，相差的只是代碼的順序，我們可以將大部分二叉樹的遞歸可以表示為根節(jié)點(diǎn)，左孩子右孩子，左子樹右子樹和根節(jié)點(diǎn)，左孩子右孩子這兩種，這非常有用是一種分治的思想。
2.4后序遍歷
void PostorderBTNode(BTNode* root)
{
if (root == NULL)
return;
PostorderBTNode(root->left);
PostorderBTNode(root->right);
printf("%d ", root->val);
}在這里我們不給代碼展開圖了，大家可以自己去畫一畫代碼展開圖。
2.5計(jì)算二叉樹節(jié)點(diǎn)個(gè)數(shù)
int BTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}我們想到二叉樹的遞歸內(nèi)容可以表示為根節(jié)點(diǎn)，左孩子右孩子，左子樹右子樹或根節(jié)點(diǎn)，左孩子右孩子，我們可以看成根節(jié)點(diǎn)，左子樹右子樹，當(dāng)根節(jié)點(diǎn)為空時(shí)我們返回0，我們分為左子樹和右子樹所以我們返回BTreeSize(root->left) + BTreeSize(root->right) + 1進(jìn)行遞歸，我們的遞歸展開圖可以畫為
2.6計(jì)算二叉樹葉子節(jié)點(diǎn)的個(gè)數(shù)?
????????我們可以根據(jù)根據(jù)根節(jié)點(diǎn)，左子樹右子樹進(jìn)行分治，當(dāng)我們的根節(jié)點(diǎn)為空時(shí)返回0，當(dāng)左孩子和右孩子為空是葉子節(jié)點(diǎn)返回1，對(duì)于左子樹和右子樹我們進(jìn)行遞歸。
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);
}遞歸展開圖和上面的相似，大家可以自己去畫一畫。
2.7計(jì)算二叉樹的深度
?我們可以根據(jù)根據(jù)根節(jié)點(diǎn)，左子樹右子樹進(jìn)行分治，當(dāng)根節(jié)點(diǎn)為空時(shí)返回0，然后進(jìn)行遞歸。
int BTreeDeap(BTNode* root)
{
if (root == NULL)
return 0;
return (int)fmax(BTreeDeap(root->left), BTreeDeap(root->right)) + 1;
}2.8計(jì)算第k層的節(jié)點(diǎn)個(gè)數(shù)
int BTreeLeafkSize(BTNode* root,int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BTreeLeafkSize(root->left, k-1) + BTreeLeafkSize(root->right, k-1);
}當(dāng)我們的根節(jié)點(diǎn)是空時(shí)我們返回0，當(dāng)我們的k變成1時(shí)我們返回1，根據(jù)左子樹右子樹進(jìn)行分治每次都讓k-1。
2.9層序遍歷
void Levelorder(BTNode* root)
{
Queue queue;
QueueInit(&queue);
if (root)
{
QueuePush(&queue, root);
}
while (!QueueEmpty(&queue))
{
BTNode* prev = top(&queue) ;
QueuePop(&queue);
if (prev->left)
QueuePush(&queue, prev->left);
if (prev->right)
QueuePush(&queue, prev->right);
printf("%d ", prev->val);
}
}在層序遍歷中我們利用隊(duì)列進(jìn)行存儲(chǔ)，先將非空的根節(jié)點(diǎn)進(jìn)行插入，進(jìn)行循環(huán)隊(duì)列不為空進(jìn)行循環(huán)，利用一個(gè)二叉樹的指針指向隊(duì)頭的元素（隊(duì)列里的元素存的是二叉樹的節(jié)點(diǎn)時(shí)結(jié)構(gòu)體的指針?biāo)晕覀兛梢杂枚鏄涞闹羔樳M(jìn)行指向），然后出隊(duì)，入指針的非空左孩子右孩子，每次打印指針對(duì)應(yīng)的值。
2.10層序遍歷變式
? ? ? ? 如果我們想每層打印時(shí)打印完每次會(huì)輸出一個(gè)換行，這時(shí)候我們應(yīng)該如何作呢？我們首先想到的是再搞一個(gè)隊(duì)列，存放第一個(gè)隊(duì)列元素是第幾層，但是我們c語言去實(shí)現(xiàn)隊(duì)列是非常麻煩的，連結(jié)構(gòu)體都需要我們?nèi)ブ匦略O(shè)定，那我們應(yīng)該如何去做呢？在我們的層序遍歷中你有沒有注意到我們的隊(duì)列中總是存在全部的一層元素或者一層與下一層的元素這兩種情況，什么時(shí)候會(huì)出現(xiàn)只有一層的元素呢？那就是上一層全部出隊(duì)了，這便是我們的突破點(diǎn)，當(dāng)我們將非空根節(jié)點(diǎn)入隊(duì)后我們引入一個(gè)變量存放隊(duì)中的元素的個(gè)數(shù)然后進(jìn)入循環(huán)，此時(shí)這個(gè)變量就是一層元素的個(gè)數(shù)，我們每次出一個(gè)元素就讓這個(gè)變量減1，這也就是我們的循環(huán)條件，循環(huán)結(jié)束后我們重新計(jì)算這個(gè)變量的值，這時(shí)候隊(duì)中還是只有一層全部的節(jié)點(diǎn)，此時(shí)變量的值就是隊(duì)中元素的個(gè)數(shù)。
2.11判斷是否為完全二叉樹
bool BinaryTreeComplete(BTNode* root)
{
Queue queue;
QueueInit(&queue);
if (root)
QueuePush(&queue, root);
while (top(&queue))
{
BiTreeNode* front = top(&queue);
QueuePop(&queue);
QueuePush(&queue, front->left);
QueuePush(&queue, front->right);
}
return QueueEmpty(&queue);
}首先我們需要了解完全二叉樹的性質(zhì)，他和滿二叉樹類似，但是序號(hào)必須和滿二叉樹相同，這時(shí)候我們采用層序遍歷的方式進(jìn)行判斷，我們將非空根節(jié)點(diǎn)入隊(duì)，判斷條件是隊(duì)頭元素不是空，每個(gè)節(jié)點(diǎn)入隊(duì)當(dāng)我們遇到空節(jié)點(diǎn)時(shí)我們判斷隊(duì)是不是都是空節(jié)點(diǎn)，如果是就是完全二叉樹，為什么這樣可以呢？當(dāng)我們?nèi)腙?duì)后一旦想出某一層時(shí)這一層的全部節(jié)點(diǎn)就會(huì)入隊(duì)，然后進(jìn)行判斷就可以了。
2.12二叉樹內(nèi)存釋放
二叉樹內(nèi)存前序中序后序都可以實(shí)現(xiàn)，但是我們?nèi)绾巫霾拍茏屵@個(gè)操作根號(hào)的實(shí)現(xiàn)呢？我們想類似于前中后序遍歷的樣子進(jìn)行，這時(shí)候你會(huì)發(fā)現(xiàn)，利用前序和中序遍歷會(huì)提前將節(jié)點(diǎn)釋放，以至于我們不能找到其他的節(jié)點(diǎn)，但是我們采用后序遍歷就完美的避免了這個(gè)問題，所以我們?cè)卺尫哦鏄鋾r(shí)我們經(jīng)常采用后序遍歷的方式。
void BTNodeDestory(BTNode* root)
{
if (root == NULL)
return;
BTNodeDestory(root->left);
BTNodeDestory(root->right);
free(root);
}2.13樹的創(chuàng)建
BiTree* BiTreeCreate(BiTree* bt)
{
bt = (BiTree*)malloc(sizeof(BiTree));
char ch;
scanf("%c", &ch);
if (ch != '#')
{
bt->data = ch;
bt->lchild = BiTreeCreate(bt);
bt->rchild = BiTreeCreate(bt);
}
else
bt = NULL;
return bt;
}3.二叉樹的性質(zhì)
1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 個(gè)結(jié)點(diǎn).
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是 .
3. 對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 , 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 ,則有 ＝ ＋1
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h= . (ps： 是log以2
為底，n+1為對(duì)數(shù))
5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對(duì)
于序號(hào)為i的結(jié)點(diǎn)有：
1. 若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無雙親節(jié)點(diǎn)
2. 若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無左孩子
3. 若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無右孩子文章來源：http://www.zghlxwxcb.cn/news/detail-753823.html
4.總結(jié)
????????事實(shí)上我們二叉樹的內(nèi)容并不是很難，更多的需要我們?nèi)ダ斫?，這就需要我們多去感受一線二叉樹的實(shí)現(xiàn)，最后希望大家可以來三連。到這里我們樹的內(nèi)容就解決了三分之二，其余的三分之一我會(huì)將以C++的形式來為大家講解，不過可能會(huì)等上一段時(shí)間了。在下一篇文章中我會(huì)給大家?guī)硪恍┒鏄涞念}目，歡迎大家持續(xù)關(guān)注。文章來源地址http://www.zghlxwxcb.cn/news/detail-753823.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)初階之二叉樹的詳細(xì)解析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
