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