資訊專(zhuān)欄INFORMATION COLUMN
摘要：當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。也就是說(shuō)，如果一個(gè)二叉樹(shù)的層數(shù)為，且結(jié)點(diǎn)總數(shù)是，則它就是滿二叉樹(shù)。完全二叉樹(shù)完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。
在數(shù)據(jù)結(jié)構(gòu)中什么是樹(shù)呢？我們有如下定義和性質(zhì)：
定義： 樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。
性質(zhì)：
1、 有一個(gè)特殊的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。
2、 除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集合Ti(1<= i<= m)又是一棵結(jié)構(gòu)與樹(shù)類(lèi)似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼結(jié)點(diǎn)。
3、 因此，樹(shù)是遞歸定義的。
注意： 樹(shù)形結(jié)構(gòu)中，子樹(shù)之間不能有交集，否則就不是樹(shù)形結(jié)構(gòu)
樹(shù)結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了，要存儲(chǔ)表示起來(lái)就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，實(shí)際中樹(shù)有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。
我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法：
typedef int DataType;struct Node{struct Node* leftChild1; // 第一個(gè)孩子結(jié)點(diǎn)struct Node* rightBrother; // 指向其下一個(gè)兄弟結(jié)點(diǎn)DataType data; // 結(jié)點(diǎn)中的數(shù)據(jù)域};二叉樹(shù)是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根（root）的元素及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，是有序樹(shù)。
當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱(chēng)作一個(gè)結(jié)點(diǎn)。
根據(jù)上圖可以分析出：
二叉樹(shù)一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。
在學(xué)習(xí)二叉樹(shù)的基本操作前，需先要?jiǎng)?chuàng)建一棵二叉樹(shù)，然后才能學(xué)習(xí)其相關(guān)的基本操作；但是用C語(yǔ)言實(shí)現(xiàn)是非常麻煩和不容易理解的，所以下面我們都是手動(dòng)來(lái)創(chuàng)建一顆簡(jiǎn)單樹(shù)，來(lái)學(xué)習(xí)二叉樹(shù)的精華。
和其它數(shù)據(jù)結(jié)構(gòu)一樣，創(chuàng)建二叉樹(shù)得先創(chuàng)建一個(gè)二叉樹(shù)類(lèi)型的數(shù)據(jù)，代碼如下：
typedef char BTDataType; //對(duì)char類(lèi)型重新起個(gè)名字叫BTDataType//創(chuàng)建一個(gè)二叉樹(shù)類(lèi)型typedef struct BinaryTreeNode{ BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;}BTNode;
創(chuàng)建代碼如下：
typedef char BTDataType; //對(duì)char類(lèi)型重新起個(gè)名字叫BTDataType//創(chuàng)建一個(gè)二叉樹(shù)類(lèi)型typedef struct BinaryTreeNode{ BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;}BTNode;//開(kāi)辟一個(gè)結(jié)點(diǎn)函數(shù)BTNode* BuyNode(BTDataType x){ BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("erron "); exit(-1); } tmp->data = x; tmp->left = NULL; tmp->right = NULL; return tmp;}//創(chuàng)建一個(gè)樹(shù)的函數(shù)BTNode* CreatBinaryTree(){ //先依次開(kāi)辟多個(gè)結(jié)點(diǎn) BTNode* a = BuyNode("A"); BTNode* b = BuyNode("B"); BTNode* c = BuyNode("C"); BTNode* d = BuyNode("D"); BTNode* e = BuyNode("E"); BTNode* f = BuyNode("F"); BTNode* g = BuyNode("G"); //然后把結(jié)點(diǎn)連接成一棵樹(shù) a->left = b; a->right = c; b->left = d; c->left = e; c->right = f; return a;}int main(){ //創(chuàng)建一棵樹(shù)，用變量root來(lái)接收樹(shù)的根 BTNode* root = CreatBinaryTree();}問(wèn)題來(lái)了，我們創(chuàng)建一棵二叉樹(shù)有什么價(jià)值呢？要研究二叉樹(shù)的什么呢？下面我們慢慢分析關(guān)于二叉樹(shù)的經(jīng)典問(wèn)題。
我們先來(lái)分析二叉樹(shù)的前中后遍歷，關(guān)于前中后遍歷的定義如下：
二叉樹(shù)的前中后遍歷的結(jié)果如下圖分析：
我們了解這棵樹(shù)的前序遍歷，那怎么用代碼實(shí)現(xiàn)出來(lái)呢？
代碼如下：
//前序遍歷void PrevOrder(BTNode* root){ if (root == NULL){ printf("NULL "); return; } //先訪問(wèn)根節(jié)點(diǎn) printf("%c ", root->data); //再訪問(wèn)左右子樹(shù) PrevOrder(root->left); PrevOrder(root->right);}int main(){ //手動(dòng)連接結(jié)點(diǎn)創(chuàng)建一棵樹(shù) BTNode* root = CreatBinaryTree(); //前序遍歷 PrevOrder(root); printf("/n");}可能大家一看，這是個(gè)遞歸呀！它是這么做到前序遍歷的呢？怎么看都看不出來(lái)呀。其實(shí)這和C語(yǔ)言的函數(shù)棧幀這塊知識(shí)點(diǎn)連續(xù)起來(lái)了，如果還沒(méi)有了解函數(shù)棧幀這塊可以先看看我的這兩篇博客，里面介紹了遞歸和函數(shù)棧幀，點(diǎn)擊即可跳轉(zhuǎn)==> 【遞歸的快速掌握】 【函數(shù)棧幀的創(chuàng)建與銷(xiāo)毀】
好了，那既然看得有點(diǎn)迷迷糊糊的，拿我們來(lái)畫(huà)一下遞歸的展開(kāi)圖，圖片如下：
這個(gè)二叉樹(shù)的中序遍歷是先訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后再訪問(wèn)右子樹(shù)
代碼實(shí)現(xiàn)如下：
//中序遍歷void InOrder(BTNode* root){ if (root == NULL) { printf("NULL "); return; } //先訪問(wèn)左子樹(shù) InOrder(root->left); //再訪問(wèn)根 printf("%c ", root->data); //再訪問(wèn)右子樹(shù) InOrder(root->right);}int main(){ //手動(dòng)連接結(jié)點(diǎn)創(chuàng)建一棵樹(shù) BTNode* root = CreatBinaryTree(); //中序遍歷 InOrder(root); printf("/n");}這個(gè)和前序遍歷都是用遞歸實(shí)現(xiàn)的，我們腦海里可能構(gòu)想不出來(lái)遞歸的全部路徑，我們還是畫(huà)出遞歸展開(kāi)圖來(lái)分析，圖片如下：
二叉樹(shù)的后序遍歷是先訪問(wèn)左子樹(shù)，再訪右子樹(shù)，最后訪問(wèn)根。
代碼實(shí)現(xiàn)如下：
//后序遍歷void PostOrder(BTNode* root){ if (root == NULL) { printf("NULL "); return; } //先訪問(wèn)左子樹(shù) PostOrder(root->left); //再訪問(wèn)右子樹(shù) PostOrder(root->right); //再訪問(wèn)根 printf("%c ", root->data);}int main(){ //手動(dòng)連接結(jié)點(diǎn)創(chuàng)建一棵樹(shù) BTNode* root = CreatBinaryTree(); //后序遍歷 PostOrder(root); printf("/n");}這個(gè)二叉樹(shù)銷(xiāo)毀我們要注意不能先銷(xiāo)毀根，再銷(xiāo)毀左右子樹(shù)，因?yàn)橄柔尫鸥驼也坏阶笥易訕?shù)的地址了。所以我們先銷(xiāo)毀左右子樹(shù)最后再銷(xiāo)毀根，和后序遍歷相似。
代碼如下:
//二叉樹(shù)的銷(xiāo)毀void DestroyTree(BTNode* root){ if (root == NULL) { return; } //先釋放左右子樹(shù)再釋放根 DestroyTree(root->left); DestroyTree(root->right); free(root);}int main(){ //手動(dòng)連接結(jié)點(diǎn)創(chuàng)建一棵樹(shù) BTNode* root = CreatBinaryTree(); //前序遍歷 PrevOrder(root); printf("/n"); //中序遍歷 InOrder(root); printf("/n"); //后序遍歷 PostOrder(root); printf("/n"); //銷(xiāo)毀二叉樹(shù) DestroyTree(root);}二叉樹(shù)的銷(xiāo)毀和后序遍歷是差不多的，都是先處理左右子樹(shù)再處理根，感覺(jué)不夠理解的小伙伴可以按我前面前序和中序遍歷一樣把遞歸展開(kāi)圖一個(gè)一個(gè)地畫(huà)出來(lái)，能大大增加我們對(duì)遞歸的理解。
要想求二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù)我們還是轉(zhuǎn)化成子問(wèn)題去解決。求二叉樹(shù)總的結(jié)點(diǎn)個(gè)數(shù)，那我可以先求左右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)再加上1自己就是總的個(gè)數(shù)了；而左右子樹(shù)又可以細(xì)分左右子樹(shù)一層層的遞歸下去再返回來(lái)就可以了。
代碼如下：
int BinaryTreeSize(BTNode* root){ if (root == NULL) { return 0 ; } //先求左右子樹(shù)的個(gè)樹(shù)再加上根結(jié)點(diǎn)就是總的結(jié)點(diǎn)個(gè)數(shù) return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;}int main(){ //手動(dòng)連接節(jié)點(diǎn)創(chuàng)建一棵樹(shù) BTNode* root = CreatBinaryTree(); //統(tǒng)計(jì)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù) int ret=BinaryTreeSize(root); printf("二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù)為%d/n", ret);}我們?nèi)绻雌饋?lái)感覺(jué)還是心里不踏實(shí)，總感覺(jué)不對(duì)勁，我們可以用老方法畫(huà)遞歸展開(kāi)圖來(lái)分析分析，遞歸展開(kāi)圖如下：
這個(gè)求的是葉子節(jié)點(diǎn)個(gè)數(shù)，而葉子節(jié)點(diǎn)的定義是左右子樹(shù)都為空才是葉子節(jié)點(diǎn)，所以我們還是用遞歸分而治之的思想，統(tǒng)計(jì)左子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)加上右子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)即可，這樣左右子樹(shù)分別遞歸下去，最后返回的就是總的葉子結(jié)點(diǎn)個(gè)數(shù)。
代碼如下：
//統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)int BinaryTreeLeafSize(BTNode* root){ if (root == NULL) { return 0; } //當(dāng)左右子樹(shù)都為空才是葉子，就返回1 if (root->left == NULL && root->right == NULL) { return 1; } //分別統(tǒng)計(jì)左右子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)，加起來(lái)就是總數(shù) return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);}遞歸展開(kāi)圖如下：
這個(gè)也是要用遞歸的分而治之思想，統(tǒng)計(jì)第K層結(jié)點(diǎn)個(gè)數(shù)，我們先統(tǒng)計(jì)K - 1層的結(jié)點(diǎn)個(gè)數(shù)，一直遞歸分下去到k等于1的時(shí)候，結(jié)點(diǎn)如果不為空就是1個(gè)結(jié)點(diǎn)。
比如求第4層結(jié)點(diǎn)的個(gè)數(shù)，我們可以轉(zhuǎn)化為求第3層左子樹(shù)結(jié)點(diǎn)的個(gè)數(shù) + 右子樹(shù)結(jié)點(diǎn)的個(gè)數(shù)；而第3層又可以轉(zhuǎn)化為第二層左右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，一直遞歸下去。
代碼實(shí)現(xiàn)如下：
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)int BinaryTreeLevelKSize(BTNode* root, int k){ if (root == NULL) { return 0; } //當(dāng)結(jié)點(diǎn)不為空，且k==1結(jié)點(diǎn)個(gè)數(shù)就為1 if (k == 1) { return 1; } //轉(zhuǎn)化為求第k-1層的左右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)，一直分治下去，直到遇到NULL或者k==1 return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);}遞歸展開(kāi)圖如下：
這個(gè)還是采用遞歸的分而治之思想，我們先求出左子樹(shù)的高度，再求出右子樹(shù)的高度，然后二者相比較，大的加1就是二叉樹(shù)的高度；而左右子樹(shù)再遞歸下去求高度，最后就可以得到二叉樹(shù)的高度。代碼實(shí)現(xiàn)如下：
//求二叉樹(shù)的高度int BinaryTreeDepth(BTNode* root){ if (root == NULL) { return 0; } //先求出左右子樹(shù)的高度 int leftDepth = BinaryTreeDepth(root->left); int rightDepth = BinaryTreeDepth(root->right); //比較左右子樹(shù)的高度，大的加1就是樹(shù)的高度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;}題目意思是在二叉樹(shù)中找和一個(gè)X值相等的結(jié)點(diǎn)，如果找到了就返回該結(jié)點(diǎn)的地址，如果沒(méi)有找到就返回空指針NULL；
我們還是用分而治之來(lái)解決，先在左子樹(shù)中找，如果找到了就返回該結(jié)點(diǎn)地址，如果左子樹(shù)沒(méi)有找到那就去右子樹(shù)里面找，找到了就返回地址。如果左右子樹(shù)都沒(méi)有找到就返回空指針NULL。
代碼實(shí)現(xiàn)如下：
//在二叉樹(shù)中找值為X的結(jié)點(diǎn)BTNode* BinaryTreeFind(BTNode* root, BTDataType x){ if (root == NULL) { return NULL; } //找到了就直接返回該結(jié)點(diǎn)地址 if (root->data == x) { return root; } //先在左子樹(shù)中找 BTNode* left = BinaryTreeFind(root->left,x); if (left != NULL) { return left; } //左子樹(shù)中沒(méi)有找到就往右子樹(shù)中找 BTNode* right = BinaryTreeFind(root->right, x); if (right != NULL) { return right; } //如果左右子樹(shù)都沒(méi)有找到就返回空指針 return NULL;}我們學(xué)了二叉樹(shù)的前、中、后序遍歷，還剩下最后一個(gè)就是層序遍歷；顧名思義就是要一層層地往下面遍歷，我們可以利用前面學(xué)過(guò)的隊(duì)列來(lái)解決。
第一步，先判斷二叉樹(shù)是否為空，為空就直接返回
第二步，把二叉樹(shù)的根入隊(duì)列，然后取隊(duì)頭的元素，再出隊(duì)列
第三步，判斷隊(duì)頭元素的左右子樹(shù)是否為空，不為空就入隊(duì)列，為空就不入隊(duì)列
第四步，判斷隊(duì)列是否為空，不為空就繼續(xù)取隊(duì)頭的元素，再出隊(duì)列，循環(huán)第三、四步即可，這樣就做到了一層層遍歷
圖片分析如下：
因?yàn)镃語(yǔ)言中沒(méi)有隊(duì)列，所以我們需要手動(dòng)實(shí)現(xiàn)一個(gè)隊(duì)列，在前面的博客中詳細(xì)地介紹并實(shí)現(xiàn)了隊(duì)列，點(diǎn)擊即可跳轉(zhuǎn)==>【隊(duì)列的模擬實(shí)現(xiàn)】，所以下面代碼中直接引用即可，
代碼實(shí)現(xiàn)如下：
void BinaryTreeOrder(BTNode* root){ if (root == NULL) { return; } Queue q; QueueInit(&q); //把根入隊(duì)列 QueuePush(&q, root); while (!QueueEmpty(&q)) { //取隊(duì)頭的元素 BTNode* front = QueueFront(&q); printf("%c", front->data); QueuePop(&q); //出隊(duì)列 if (front->left != NULL) { QueuePush(&q, front->left); } if (front->right != NULL) { QueuePush(&q, front->right); } } //銷(xiāo)毀隊(duì)列 QueueDestroy(&q);}我們知道完全二叉樹(shù)最后一層的葉子結(jié)點(diǎn)一定都是連續(xù)的，如果葉子結(jié)點(diǎn)沒(méi)有連續(xù)中間有空指針的話就不是完全二叉樹(shù)了；所以我們利用這個(gè)特點(diǎn)和利用隊(duì)列解決，
首先我們把不為空的根先入隊(duì)列，然后取隊(duì)頭的元素，接著出隊(duì)列
然后不管隊(duì)頭的元素左右子樹(shù)是否為空我們都入隊(duì)列；
接著就不斷取隊(duì)頭的元素，取到空指針就不再入隊(duì)列，判斷隊(duì)列剩下的元素是否都為空指針，如果都為空指針代表葉子結(jié)點(diǎn)都是連續(xù)的，是完全二叉樹(shù)；如果不都為空指針，代表葉子結(jié)點(diǎn)是不連續(xù)的不是完全二叉樹(shù)。
代碼實(shí)現(xiàn)如下：
//判斷二叉樹(shù)是否為完全二叉樹(shù)bool BinaryTreeComplete(BTNode* root){ if (root == NULL) { return false; } Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //如果隊(duì)頭元素不為空就入隊(duì)頭元素的左右子樹(shù) //如果隊(duì)頭元素為空就退出 if (front != NULL) { QueuePush(&q, front->left); QueuePush(&q, front->right); } else { break; } } //判斷隊(duì)列剩下的元素是否都為空指針 //都為空指針就是完全二叉樹(shù) while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); if (front != NULL) { QueueDestroy(&q); return false; } QueuePop(&q); } return true;
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/124780.html
閱讀 2000·2021-11-24 09:39
閱讀 2796·2021-10-14 09:43
閱讀 3412·2021-10-08 10:10
閱讀 2423·2021-09-22 15:54
閱讀 2413·2019-08-29 17:20
閱讀 1632·2019-08-28 18:14
閱讀 2432·2019-08-26 13:28
閱讀 1182·2019-08-26 12:16
