---

1.樹

學(xué)習(xí)二叉樹，首先得了解樹，從樹的基本概念出發(fā)。

1.1定義

樹是n個(gè)節(jié)點(diǎn)的的有限集合，是一種非線性結(jié)構(gòu)。當(dāng)n=0時(shí)稱為空樹，對(duì)于非空樹T：（1）只有一個(gè)根結(jié)點(diǎn)（root）；（2）除根節(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集T1，T2，……，Tm，其中每個(gè)集合本身又是一棵樹，稱為根的子樹。

1.2基本術(shù)語(yǔ)

• 結(jié)點(diǎn)：樹的一個(gè)獨(dú)立單元，包含一個(gè)數(shù)據(jù)元素或者指向其子樹的分支。如圖中的A，B，C等。
• 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度（也可以理解為這個(gè)結(jié)點(diǎn)有多少個(gè)孩子）。如A的度是2，B的度是3，D的度是0。
• 樹的度：樹的各個(gè)結(jié)點(diǎn)的度的最大值。如圖中的樹的度為3。
• 葉子結(jié)點(diǎn)（或者終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)。如圖中的D，E，F，G。
• 非終端結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。除根結(jié)點(diǎn)外，非終端結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。如圖中B，C。
• 孩子結(jié)點(diǎn)（或者子節(jié)點(diǎn)）：一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。如圖中B和C是A的子結(jié)點(diǎn)。
• 雙親結(jié)點(diǎn)（或者父結(jié)點(diǎn)）：一個(gè)結(jié)點(diǎn)有一個(gè)子結(jié)點(diǎn)，該結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)。如圖中，A是B和C的雙親結(jié)點(diǎn)。
• 兄弟結(jié)點(diǎn)：同一雙親的孩子之間互稱兄弟。如圖中B和C是兄弟結(jié)點(diǎn)。
• 祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。如D的祖先是A和B。
• 子孫：以某結(jié)點(diǎn)為根的子樹的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。如D，E，F是B的子孫。
• 層次：從根結(jié)點(diǎn)開始，根結(jié)點(diǎn)為第一層，根的孩子為第二層，以此類推直到最后一層。如A是第一層，B是第二層，D是第三層。
• 深度：樹中結(jié)點(diǎn)的最大層次。如A這棵樹的深度是3。
• 森林：由m棵互不相交的樹構(gòu)成的集合。如去掉A結(jié)點(diǎn)，B和C這兩棵子樹就是森林。

這么多概念，但常用的只有結(jié)點(diǎn)的度、雙親結(jié)點(diǎn)、葉子結(jié)點(diǎn)、樹的層次、樹的高度、結(jié)點(diǎn)的祖先和子孫。

1.3樹形結(jié)構(gòu)和線性結(jié)構(gòu)

樹形結(jié)構(gòu)	線性結(jié)構(gòu)
樹的根結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)	線性表的第一個(gè)元素沒(méi)有前驅(qū)
樹的葉子結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)	線性表的最后一個(gè)元素沒(méi)有后繼
樹的內(nèi)部結(jié)點(diǎn)有一個(gè)前驅(qū)和多個(gè)后繼	線性表的其余元素只有一個(gè)前驅(qū)和一個(gè)后繼

1.4樹的存儲(chǔ)結(jié)構(gòu)

樹有多種存儲(chǔ)結(jié)構(gòu)：雙親表示法、孩子鏈表表示法、孩子兄弟表示法等。由于今天的豬腳是二叉樹，所以在這里簡(jiǎn)單介紹下雙親表示法和孩子兄弟表示法。

1.4.1雙親表示法

//結(jié)點(diǎn)
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{ElemType x;//結(jié)點(diǎn)的數(shù)據(jù)int parent;//結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)
}PTNode;
typedef struct
{PTNode a[MAXSIZE];//結(jié)點(diǎn)數(shù)組int size;//結(jié)點(diǎn)個(gè)數(shù)
}PTree;

1.4.2孩子兄弟表示法

//結(jié)點(diǎn)
typedef int ElemType;
typedef struct CBTreeNode
{ElemType x;//數(shù)據(jù)struct CBTreeNode* firstchild;//指向結(jié)點(diǎn)的左孩子，也就是第一個(gè)孩子struct CBTreeNode* Nextbrother;//指向同一父結(jié)點(diǎn)的兄弟
}CBTNode;

---

2.二叉樹

2.1定義

二叉樹是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)為空樹，當(dāng)n不為0時(shí)，二叉樹有以下特點(diǎn)：1.每個(gè)結(jié)點(diǎn)的度不超過(guò)2（可以理解為二孩政策下的結(jié)點(diǎn)最多只能有兩個(gè)孩子）；
2.每個(gè)結(jié)點(diǎn)的左子樹和右子樹順序不能顛倒，所以二叉樹是有序樹。

2.2特殊二叉樹

1. 滿二叉樹：每一層結(jié)點(diǎn)數(shù)都達(dá)到最大，那么它就是滿二叉樹。如第1層最多有2 ^0個(gè)結(jié)點(diǎn)，第2層最多有 2 ^1個(gè)結(jié)點(diǎn)，則第k層最多有2 ^(k-1)個(gè)結(jié)點(diǎn)，假設(shè)這棵滿二叉樹有k層，那么它總共有2 ^0+2 ^1+……+2 ^(k-1) = 2 ^k-1個(gè)結(jié)點(diǎn)。
2. 完全二叉樹：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。（簡(jiǎn)介版：完全二叉樹的前k-1層是滿二叉樹，最后一層從左到右依次連續(xù)）

2.3性質(zhì)

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個(gè)結(jié)點(diǎn)。
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h-1。
3. 對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。
   證明
   
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h= log (n+1)(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)，無(wú)雙親節(jié)點(diǎn)
   （2）. 若2i+1<n，左孩子序號(hào)：2i+1，2i+1>=n否則無(wú)左孩子
   （3）.若2i+2<n，右孩子序號(hào)：2i+2，2i+2>=n否則無(wú)右孩子
   

2.4存儲(chǔ)結(jié)構(gòu)

2.4.1順序存儲(chǔ)

二叉樹的順序存儲(chǔ)是用數(shù)組存儲(chǔ)的，其中結(jié)點(diǎn)之間的關(guān)系用下標(biāo)來(lái)表示。即二叉樹的邏輯結(jié)構(gòu)是樹，但是其物理結(jié)構(gòu)是數(shù)組。

但這種存儲(chǔ)結(jié)構(gòu)會(huì)造成空間浪費(fèi)，適用于完全二叉樹和滿二叉樹。

但這個(gè)結(jié)構(gòu)卻可以來(lái)實(shí)現(xiàn)一個(gè)很牛逼的排序：堆排序。

2.4.2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以解決順序存儲(chǔ)結(jié)構(gòu)浪費(fèi)空間的問(wèn)題，二叉樹的鏈?zhǔn)酱鎯?chǔ)表示有二叉鏈表、三叉鏈表、雙親鏈表、線索鏈表等。這里重點(diǎn)講二叉鏈表。

//二叉樹的節(jié)點(diǎn)
typedef int DataType;
typedef struct BinaryTreeNode
{DataType val;struct BinaryTreeNode* left;//指向左孩子的指針struct BinaryTreeNode* right;//指向右孩子的指針
}BTNode;

下面講二叉樹的基本操作。

3.二叉樹的基本操作

遍歷是指每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。二叉樹有一個(gè)前驅(qū)和兩個(gè)后繼，這注定其遍歷不同于線性結(jié)構(gòu)的遍歷。二叉樹的遍歷有前序遍歷、中序遍歷，后序遍歷，層序遍歷。

3.1前序遍歷（先序遍歷）

1. 概念
   前序遍歷：先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹和右子樹。
   

由圖可知，樹的前序遍歷是遞歸的，所以可以用遞歸來(lái)實(shí)現(xiàn)。

2. 代碼實(shí)現(xiàn)

//先手動(dòng)創(chuàng)建一個(gè)二叉樹
BTNode* BuyNode(DataType x)//申請(qǐng)一個(gè)結(jié)點(diǎn)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc failed");return NULL;}newnode->left = newnode->right = NULL;newnode->val = x;return newnode;
}
BTNode* CreateBT()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;//返回根結(jié)點(diǎn)
}
//前序遍歷
void PreOrder(BTNode* root)
{//思路：先訪問(wèn)根結(jié)點(diǎn)，再訪問(wèn)左子樹和右子樹if (root==NULL){printf("NULL ");return;}//先訪問(wèn)根結(jié)點(diǎn)printf("%d ", root->val);//再訪問(wèn)左右子樹PreOrder(root->left);PreOrder(root->right);
}
int main()
{BTNode* root = CreateBT();PreOrder(root);return 0;
}

答案

3.2中序遍歷

1. 概念
   中序遍歷：先訪問(wèn)左子樹，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹。
   
   同樣可以用遞歸實(shí)現(xiàn)
2. 代碼實(shí)現(xiàn)

// 二叉樹中序遍歷
void InOrder(BTNode* root)
{//思路：先訪問(wèn)左子樹，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹if (root == NULL){printf("NULL ");return;}//先訪問(wèn)左子樹InOrder(root->left);//再訪問(wèn)根節(jié)點(diǎn)printf("%d ", root->val);//最后訪問(wèn)右子樹InOrder(root->right);
}

答案

3.3后序遍歷

1. 概念
   后序遍歷：先訪問(wèn)左子樹，再訪問(wèn)右子樹，最后訪問(wèn)根節(jié)點(diǎn)。
   
2. 代碼實(shí)現(xiàn)

//后序遍歷
void PostOrder(BTNode* root)
{//思路：先訪問(wèn)左子樹，再訪問(wèn)右子樹，最后訪問(wèn)根結(jié)點(diǎn)if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}

答案

3.4層序遍歷

1. 概念
   層序遍歷：從上到下，從左到右，依次訪問(wèn)。
   
2. 代碼實(shí)現(xiàn)

// 層序遍歷
void LevelOrder(BTNode* root)
{//思路：用隊(duì)列實(shí)現(xiàn)，出隊(duì)一層，入隊(duì)下一層Queue q;QInit(&q);//如果非空就直接入隊(duì)if (root){QPush(&q, root);}//隊(duì)列中只入隊(duì)非空元素while (!QEmpty(&q)){//先出隊(duì)BTNode* tmp = QPop(&q);printf("%d ", tmp->val );//再判斷左右子樹是否為空if (tmp->left){QPush(&q, tmp->left);}if (tmp->right){QPush(&q, tmp->right);}}QDestroy(&q);
}

答案

4.二叉樹練習(xí)

樣例

1. 求二叉樹的節(jié)點(diǎn)個(gè)數(shù)

// 二叉樹節(jié)點(diǎn)個(gè)數(shù)//法一：
int size = 0;//也可以使用靜態(tài)變量
void TreeSize(BTNode* root)
{//思路：只要節(jié)點(diǎn)不為空，就記錄一次if (root == NULL){return 0;}++size;TreeSize(root->left);TreeSize(root->right);
}//法二：
int BinaryTreeSize(BTNode* root)
{//思路：二叉樹的節(jié)點(diǎn)個(gè)數(shù) = 左子樹的節(jié)點(diǎn)個(gè)數(shù) + 右子樹的節(jié)點(diǎn)個(gè)數(shù)if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1 ;
}

注意
但是法一有個(gè)弊端：size是全局（或靜態(tài)）變量，每次調(diào)用都得初始化一次。
答案

2. 求二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)

// 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root)
{//思路：二叉樹的葉子節(jié)點(diǎn) = 左子樹的葉子節(jié)點(diǎn) + 右子樹的葉子節(jié)點(diǎn)if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

答案

3. 求二叉樹的高度

// 二叉樹的高度(深度)
int TreeHeight(BTNode* root)
{// 思路：二叉樹的高度 = 左子樹的高度和右子樹的高度的最大值 + 1if (root == NULL){return 0;}int left = TreeHeight(root->left);int right = TreeHeight(root->right);return left > right ? left + 1 : right + 1;
}

答案

4. 求第k層節(jié)點(diǎn)個(gè)數(shù)

// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{//思路：//對(duì)于第一層，是求第k層節(jié)點(diǎn)個(gè)數(shù)（k）//對(duì)于第二層，是求第k-1層節(jié)點(diǎn)個(gè)數(shù)（k-1）//……//對(duì)于第k層，是求這一層節(jié)點(diǎn)個(gè)數(shù)（1）//第k層節(jié)點(diǎn)個(gè)數(shù) = 左子樹第k層節(jié)點(diǎn)個(gè)數(shù) + 右子樹第k層節(jié)點(diǎn)個(gè)數(shù)if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

答案

5. 判斷是否是單值二叉樹（LeetCode965）OJ鏈接
   單值二叉樹：二叉樹的每個(gè)節(jié)點(diǎn)都有相同的值

// 判斷是否是單值二叉樹
bool isUnivalTree(BTNode* root)
{//思路：比較根節(jié)點(diǎn)與左右子樹是否相等，不相等就返回false，相等就判斷左右子樹是否是單值二叉樹if (root == NULL){return true;}if (root->left && root->left->val != root->val){return false;}if (root->right && root->right->val != root->val){return false;}return isUnivalTree(root->left) && isUnivalTree(root->right);
}

答案

6. 查找一個(gè)值為x的節(jié)點(diǎn)

// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{//思路：先判斷根的值是否與x相等，相等就返回根，//不等就判斷是否與左子樹相等，相等就返回//不等就判斷是否與右子樹相等，相等就返回，不等就返回NULLif (root == NULL){return NULL;}if (root->val == x){return root;}BTNode*tmp = BinaryTreeFind(root->left, x);if (tmp != NULL){return tmp;}tmp = BinaryTreeFind(root->right, x);if (tmp != NULL){return tmp;}return NULL;
}

7. 判斷兩棵二叉樹是否相等（LeetCode100）OJ鏈接

// 判斷兩棵二叉樹是否相等
bool isSameTree(BTNode* p, BTNode* q)
{//思路：先判斷根結(jié)點(diǎn)是否相等，再判斷左子樹是否相等，最后判斷右子樹是否相等if (p == NULL && q == NULL){return true;}if (p == NULL || q == NULL){return false;}if (p->val != q->val){return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

答案

8. 判斷是否是對(duì)稱二叉樹（LeetCode101）OJ鏈接

bool isLefRig(BTNode* p1, BTNode* p2)//功能類似于判斷兩棵二叉樹是否相等
{if (p1 == NULL && p2 == NULL){return true;}if (p1 == NULL || p2 == NULL){return false;}if (p1->val != p2->val){return false;}return isLefRig(p1->left, p2->right) && isLefRig(p1->right, p2->left);
}
bool isSymmetric(BTNode* root)
{
·	//思路：寫一個(gè)輔助函數(shù)，功能與判斷二叉樹是否相等類似if (root == NULL){return true;}return isLefRig(root->left, root->right);
}

答案

9. 二叉樹的前序遍歷（LeetCode144）OJ鏈接

int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* a, int* i)
{if (root == NULL){return;}//先對(duì)根結(jié)點(diǎn)進(jìn)行操作，再對(duì)左右子樹進(jìn)行操作a[(*i)++] = root->val;PreOrder(root->left, a, i);PreOrder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){//我們需要知道這棵樹的大小，再來(lái)動(dòng)態(tài)申請(qǐng)int size = TreeSize(root);*returnSize = size;int* ret = (int*)malloc(sizeof(int) * size);//寫一個(gè)函數(shù)來(lái)實(shí)現(xiàn)遍歷，不要在這個(gè)函數(shù)遍歷，因?yàn)楸闅v需要遞歸，所以TreeSize會(huì)重復(fù)調(diào)用int i = 0;//用來(lái)記錄數(shù)組的下標(biāo)，方便存儲(chǔ)數(shù)據(jù)PreOrder(root, ret, &i);//為什么要傳下標(biāo)的地址？因?yàn)橐獙?duì)下標(biāo)進(jìn)行修改return ret;
}

答案

10. 二叉樹的中序遍歷（LeetCode94）OJ鏈接

int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void InOrder(struct TreeNode* root, int* a, int* i)
{if (root == NULL){return;}InOrder(root->left, a, i);a[(*i)++] = root->val;InOrder(root->right, a, i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){//我們需要知道這棵樹的大小，再來(lái)動(dòng)態(tài)申請(qǐng)int size = TreeSize(root);*returnSize = size;int* ret = (int*)malloc(sizeof(int) * size);//寫一個(gè)函數(shù)來(lái)實(shí)現(xiàn)遍歷，不要在這個(gè)函數(shù)遍歷，因?yàn)楸闅v需要遞歸，所以TreeSize會(huì)重復(fù)調(diào)用int i = 0;//用來(lái)記錄數(shù)組的下標(biāo)，方便存儲(chǔ)數(shù)據(jù)InOrder(root, ret, &i);//為什么要傳下標(biāo)的地址？因?yàn)橐獙?duì)下標(biāo)進(jìn)行修改return ret;
}

結(jié)果

11. 二叉樹的后序遍歷（LeetCode145）OJ鏈接

int BinaryTreeSize(struct TreeNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
void PostOrder(struct TreeNode* root, int* ret, int* pi)
{if (root == NULL){return 0;}PostOrder(root->left, ret, pi);PostOrder(root->right, ret, pi);ret[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){int size = BinaryTreeSize(root);*returnSize = size;int* ret = (int*)malloc(sizeof(int) * size);//用來(lái)存放前序序列int i = 0;PostOrder(root, ret, &i);return ret;
}

結(jié)果

12. 判斷一棵樹是否是另一棵樹的子樹

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{//思路：用當(dāng)前節(jié)點(diǎn)所在樹與sub進(jìn)行比較，相等返回真，不相等用當(dāng)前根結(jié)點(diǎn)的左子樹比較，再不相等用右子樹比較if (root == NULL){return false;}if (isSameTree(root, subRoot)){return true;}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

結(jié)果

13. 判斷是否是完全二叉樹

// 判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root)
{//思路：利用層序遍歷，將完全二叉樹的所有節(jié)點(diǎn)全部入隊(duì)，//當(dāng)出隊(duì)時(shí)節(jié)點(diǎn)為NULL，如果為完全二叉樹，則隊(duì)列中的其余節(jié)點(diǎn)都是NULL，//所以最后判斷隊(duì)列中的節(jié)點(diǎn)是否不為NULL，即可判斷Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode*tmp = QueueFront(&q);QueuePop(&q);if (tmp == NULL){break;//當(dāng)遇到NULL，就跳出循環(huán)}else{QueuePush(&q, tmp->left);//如果為NULL也入隊(duì)QueuePush(&q, tmp->right);}}while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp){QueueDestroy(&q);//注意銷毀隊(duì)列，防止內(nèi)存泄漏return false;}}QueueDestroy(&q);//等下學(xué)習(xí)怎么銷毀，先記住它有銷毀的功能return true;
}
int main()
{char arr[100] = { 0 };scanf("%s", arr);int i = 0;int size = strlen(arr);BTNode* root = CreateBT(arr, &i,size);InOrder(root);
}

5.二叉樹的創(chuàng)建和銷毀

前面的二叉樹是我們手動(dòng)創(chuàng)建的，現(xiàn)在學(xué)習(xí)了前序、中序、后序遍歷，就可以利用它們來(lái)創(chuàng)建和銷毀二叉樹。

5.1二叉樹的創(chuàng)建

二叉樹遍歷OJ鏈接

BTNode* BuyNode(DataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc failed");return NULL;}newnode->left = NULL;newnode->right = NULL;newnode->val = x;return newnode;
}
BTNode* CreateBT(char* arr, int* pi,int size)
{	//ABC##DE#G##F###if (*pi == size)//遞歸的停止條件{return NULL;}if (arr[*pi] == '#'){(*pi)++;//遇到#,不要忘記跳過(guò)return NULL;}BTNode* root = BuyNode(arr[(*pi)++]);root->left = CreateBT(arr, pi,size);root->right = CreateBT(arr, pi,size);return root;
}
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}
int main()
{char arr[100] = { 0 };scanf("%s", arr);int i = 0;int size = strlen(arr);BTNode* root = CreateBT(arr, &i,size);InOrder(root);
}

結(jié)果

5.2二叉樹的銷毀

// 二叉樹銷毀
void BinaryTreeDestory(BTNode* root)
{//如果用前序或者中序遍歷銷毀二叉樹會(huì)導(dǎo)致內(nèi)存泄漏（找不到左右子樹）//所以用后序遍歷銷毀二叉樹if (root == NULL){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);root == NULL;
}