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