---

1.樹

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

1.1定義

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

1.2基本術語

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

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

1.3樹形結構和線性結構

樹形結構	線性結構
樹的根結點沒有雙親結點	線性表的第一個元素沒有前驅
樹的葉子結點沒有子結點	線性表的最后一個元素沒有后繼
樹的內部結點有一個前驅和多個后繼	線性表的其余元素只有一個前驅和一個后繼

1.4樹的存儲結構

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

1.4.1雙親表示法

//結點
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{ElemType x;//結點的數(shù)據(jù)int parent;//結點的雙親結點的下標
}PTNode;
typedef struct
{PTNode a[MAXSIZE];//結點數(shù)組int size;//結點個數(shù)
}PTree;

1.4.2孩子兄弟表示法

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

---

2.二叉樹

2.1定義

二叉樹是n（n>=0）個結點的有限集合。當n=0時為空樹，當n不為0時，二叉樹有以下特點：1.每個結點的度不超過2（可以理解為二孩政策下的結點最多只能有兩個孩子）；
2.每個結點的左子樹和右子樹順序不能顛倒，所以二叉樹是有序樹。

2.2特殊二叉樹

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

2.3性質

1. 若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個結點。
2. 若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結點數(shù)是2^h-1。
3. 對任何一棵二叉樹T，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0=n2+1。
   證明
   
4. 若規(guī)定根節(jié)點的層數(shù)為1，具有n個結點的滿二叉樹的深度，h= log (n+1)(ps:log是以2
   為底，n+1為對數(shù))。
   證明
   
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序對所有節(jié)點從0開始編號，則對于序號為i的結點有：
   （1）. 若i>0，i位置節(jié)點的雙親序號：(i-1)/2；i=0，i為根節(jié)點編號，無雙親節(jié)點
   （2）. 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
   （3）.若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子
   

2.4存儲結構

2.4.1順序存儲

二叉樹的順序存儲是用數(shù)組存儲的，其中結點之間的關系用下標來表示。即二叉樹的邏輯結構是樹，但是其物理結構是數(shù)組。

但這種存儲結構會造成空間浪費，適用于完全二叉樹和滿二叉樹。

但這個結構卻可以來實現(xiàn)一個很牛逼的排序：堆排序。

2.4.2鏈式存儲結構

鏈式存儲結構可以解決順序存儲結構浪費空間的問題，二叉樹的鏈式存儲表示有二叉鏈表、三叉鏈表、雙親鏈表、線索鏈表等。這里重點講二叉鏈表。

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

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

3.二叉樹的基本操作

遍歷是指每個結點被訪問一次且僅被訪問一次。二叉樹有一個前驅和兩個后繼，這注定其遍歷不同于線性結構的遍歷。二叉樹的遍歷有前序遍歷、中序遍歷，后序遍歷，層序遍歷。

3.1前序遍歷（先序遍歷）

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

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

2. 代碼實現(xiàn)

//先手動創(chuàng)建一個二叉樹
BTNode* BuyNode(DataType x)//申請一個結點
{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;//返回根結點
}
//前序遍歷
void PreOrder(BTNode* root)
{//思路：先訪問根結點，再訪問左子樹和右子樹if (root==NULL){printf("NULL ");return;}//先訪問根結點printf("%d ", root->val);//再訪問左右子樹PreOrder(root->left);PreOrder(root->right);
}
int main()
{BTNode* root = CreateBT();PreOrder(root);return 0;
}

答案

3.2中序遍歷

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

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

答案

3.3后序遍歷

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

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

答案

3.4層序遍歷

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

// 層序遍歷
void LevelOrder(BTNode* root)
{//思路：用隊列實現(xiàn)，出隊一層，入隊下一層Queue q;QInit(&q);//如果非空就直接入隊if (root){QPush(&q, root);}//隊列中只入隊非空元素while (!QEmpty(&q)){//先出隊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.二叉樹練習

樣例

1. 求二叉樹的節(jié)點個數(shù)

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

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

2. 求二叉樹的葉子節(jié)點個數(shù)

// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root)
{//思路：二叉樹的葉子節(jié)點 = 左子樹的葉子節(jié)點 + 右子樹的葉子節(jié)點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é)點個數(shù)

// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{//思路：//對于第一層，是求第k層節(jié)點個數(shù)（k）//對于第二層，是求第k-1層節(jié)點個數(shù)（k-1）//……//對于第k層，是求這一層節(jié)點個數(shù)（1）//第k層節(jié)點個數(shù) = 左子樹第k層節(jié)點個數(shù) + 右子樹第k層節(jié)點個數(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鏈接
   單值二叉樹：二叉樹的每個節(jié)點都有相同的值

// 判斷是否是單值二叉樹
bool isUnivalTree(BTNode* root)
{//思路：比較根節(jié)點與左右子樹是否相等，不相等就返回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. 查找一個值為x的節(jié)點

// 二叉樹查找值為x的節(jié)點
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)
{//思路：先判斷根結點是否相等，再判斷左子樹是否相等，最后判斷右子樹是否相等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. 判斷是否是對稱二叉樹（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)
{
·	//思路：寫一個輔助函數(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;}//先對根結點進行操作，再對左右子樹進行操作a[(*i)++] = root->val;PreOrder(root->left, a, i);PreOrder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){//我們需要知道這棵樹的大小，再來動態(tài)申請int size = TreeSize(root);*returnSize = size;int* ret = (int*)malloc(sizeof(int) * size);//寫一個函數(shù)來實現(xiàn)遍歷，不要在這個函數(shù)遍歷，因為遍歷需要遞歸，所以TreeSize會重復調用int i = 0;//用來記錄數(shù)組的下標，方便存儲數(shù)據(jù)PreOrder(root, ret, &i);//為什么要傳下標的地址？因為要對下標進行修改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){//我們需要知道這棵樹的大小，再來動態(tài)申請int size = TreeSize(root);*returnSize = size;int* ret = (int*)malloc(sizeof(int) * size);//寫一個函數(shù)來實現(xiàn)遍歷，不要在這個函數(shù)遍歷，因為遍歷需要遞歸，所以TreeSize會重復調用int i = 0;//用來記錄數(shù)組的下標，方便存儲數(shù)據(jù)InOrder(root, ret, &i);//為什么要傳下標的地址？因為要對下標進行修改return ret;
}

結果

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);//用來存放前序序列int i = 0;PostOrder(root, ret, &i);return ret;
}

結果

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

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

結果

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

// 判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root)
{//思路：利用層序遍歷，將完全二叉樹的所有節(jié)點全部入隊，//當出隊時節(jié)點為NULL，如果為完全二叉樹，則隊列中的其余節(jié)點都是NULL，//所以最后判斷隊列中的節(jié)點是否不為NULL，即可判斷Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode*tmp = QueueFront(&q);QueuePop(&q);if (tmp == NULL){break;//當遇到NULL，就跳出循環(huán)}else{QueuePush(&q, tmp->left);//如果為NULL也入隊QueuePush(&q, tmp->right);}}while (!QueueEmpty(&q)){BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp){QueueDestroy(&q);//注意銷毀隊列，防止內存泄漏return false;}}QueueDestroy(&q);//等下學習怎么銷毀，先記住它有銷毀的功能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)建和銷毀

前面的二叉樹是我們手動創(chuàng)建的，現(xiàn)在學習了前序、中序、后序遍歷，就可以利用它們來創(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)++;//遇到#,不要忘記跳過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);
}

結果

5.2二叉樹的銷毀

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