🐇

🔥博客主頁： 云曦
📋系列專欄：數據結構

💨吾生也有涯，而知也無涯 💛 感謝大家👍點贊 😋關注📝評論

---

前言

在上期，講解完棧和隊列的實現后，本期迎來了新的知識，名為"二叉樹"，希望大家能堅持的學習下去。

一、樹的概念及結構

🌳1.1 樹的概念

樹跟之前所學的順序表、鏈表等不相同，樹是一種非線性 的數據結構，它由n(n>=0)個有序節點組成一個具有層次關系的集合。把它叫作樹是因為它看起來像一顆倒掛的樹，也就是根朝上，而葉子朝下。

• 有一個特殊的節點，稱作根節點，根節點沒有前驅節點。
• 除根節點外，其余結點被分成M(M>0)個互不相交的集T1T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼
• 因此樹是由遞歸定義的
  

• 樹的相關概念：
  

1. 節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6
2. 葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點
3. 非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點
4. 雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
5. 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
6. 兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
7. 樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6
8. 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
9. 樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4
10. 堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
11. 節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
12. 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫
13. 森林：由m（m>0）棵互不相交的樹的集合稱為森林；

🌳1.4 樹和非樹

注意：樹形結構中，子樹之間是沒有交集的，否則就不是樹形結構了。

🌳1.3 樹的表示

孩子兄弟表示法：

typedef int DataType;typedef struct TreeNode
{struct TreeNode* firstchild;//第一個孩子節點struct TreeNode* nextbrother;//指向下一個兄弟節點DataType data;//節點的數據域
}TNode;

🌳1.4 樹在實際中的運用

用于表示文件系統的目錄數結構

二、二叉樹的概念及結構

🌳2.1 二叉樹的概念

每一顆二叉樹是節點的一個有序的集合，該集合的特點是：

1. 由一個根和左子樹、右子樹的組成的二叉樹。
2. 該樹也有可能為空。

從上圖可以看出：

1. 二叉樹不存在大于2的節點。
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

• 注意：對于任何一顆二叉樹都有可能由以下幾種復合而成的：
  

🌳2.2 現實中的二叉樹

🌳2.3 特殊的二叉樹

1. 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是 ，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
   

🌳2.4 二叉樹的性質

1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 個結點.
2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 .
3. 對任何一棵二叉樹, 如果度為0其葉結點個數為 , 度為2的分支結點個數為 ,則有 ＝ ＋1
4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h= . (ps： 是log以2為底，n+1為對數)
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編號，則對于序號為i的結點有：

• 若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
• 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
• 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

🌳2.5 二叉樹的存儲結構

??2.5.1 順序存儲

順序結果存儲就是用數組來存儲的，一般使用數組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而在使用時只有堆才會用數組來存儲，所以本期暫時不講解順序存儲。

??2.5.2 鏈式存儲

二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。 通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址 。鏈式結構又分為二叉鏈和三叉鏈，當前我們使用的都是二叉鏈，三叉鏈會在講解紅黑樹時使用。

typedef char BTDataType;
//二叉鏈
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//指向當前節點左孩子struct BinaryTreeNode* right;//指向當前節點右孩子BTDataType data;//當前節點值域
}BTNode;//三叉鏈
typedef struct BinaryTreeNode
{struct BinaryTreeNode* parents;//指向當前節點的雙親struct BinaryTreeNode* left;//指向當前節點左孩子struct BinaryTreeNode* right;//指向當前節點右孩子BTDataType data;//當前節點值域
}BTNode;

三、二叉樹鏈式結構及實現

結構的創建

typedef char BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//左子樹struct BinaryTreeNode* right;//右子樹BTDataType data;//節點的數據域
}BTNode;

🌳3.1 二叉樹的遍歷

學習二叉樹結構，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次。

??3.1.1 二叉樹前序、中序、后序遍歷的規則

• 前序遍歷：先訪問根節點，其次是左子樹，最后是右子樹(根 -> 左子樹 -> 右子樹)
• 中序遍歷：先訪問左子樹，其次是根，最后是右子樹(左子樹 -> 根 -> 右子樹)
• 后序遍歷：先訪問左子樹，其次是右子樹，最后是根(左子樹 -> 右子樹 -> 根)
• 舉例：
  

由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為
根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

// 二叉樹前序遍歷
void PreOrder(BTNode* root);
// 二叉樹中序遍歷
void InOrder(BTNode* root);
// 二叉樹后序遍歷
void PostOrder(BTNode* root);

??3.1.2 前序遍歷

//二叉樹前序遍歷
void PrevOrder(BTNode* root)
{//根為空就返回if (root == NULL){printf("NULL ");return;}//根 -> 左子樹 -> 右子樹printf("%c ", root->data);//打印根PrevOrder(root->left);//遞歸左子樹PrevOrder(root->right);//遞歸右子樹
}

??3.1.3 中序遍歷

//二叉樹中序遍歷
void InOrder(BTNode* root)
{//根為空就返回if (root == NULL){printf("NULL ");return;}//左子樹 -> 根 -> 右子樹InOrder(root->left);//遞歸左子樹printf("%c ", root->data);//打印根InOrder(root->right);//遞歸右子樹
}

??3.1.4 后序遍歷

void PostOrder(BTNode* root)
{//根為空就返回if (root == NULL){printf("NULL ");return;}//左子樹 -> 右子樹 -> 根PostOrder(root->left);//遞歸左子樹PostOrder(root->right);//遞歸右子樹printf("%c ", root->data);//打印根
}

??3.1.5 層序遍歷

• 前序中序后序其實也叫：深度優先遍歷
• 而層序遍歷也叫作：廣度優先遍歷
• 層序的核心思路就是：上層取出的時候，帶下一層進
• 層序遍歷需要用到隊列來實現，而在C語言中沒有隊列的庫，那么還要實現一個隊列。但其實不需要實現，因為上一起已經實現過了，我們直接將源文件和頭文件復制粘貼到實現二叉樹的目錄下即可。(實現棧和隊列的鏈接)
• 實現思路：
  注意：引用隊列的源文件和頭文件后，要在隊列的頭文件里聲明樹的結構體，然后將隊列結構data的類型改為樹的結構體指針類型
  
  且在二叉樹的頭文件里聲明隊列的頭文件時，要在樹的結構體后面聲明，因為在編譯是頭文件是張開向上找結構體的。
  

void LevelOrder(BTNode* root)
{//創建及初始化隊列Que q;QueueInit(&q);//空樹就不需要入隊列了//不是空樹就把根節點入隊列if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){//根節點出隊列BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->data);//左子樹入隊列if (front->left){QueuePush(&q, front->left);}//右子樹入隊列if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);
}

🌳3.2 二叉樹節點個數的統計

??3.2.1 節點的個數

int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

看遞歸很繞的時候教大家一個方法，畫遞歸展開圖

??3.2.2 葉子節點的個數

int LeafSize(BTNode* root)
{//根為空就返回0if (root == NULL){return 0;}//左右子樹為空，則返回1if (root->left == NULL && root->right == NULL){return 1;}//遞歸左子樹的葉子個數加遞歸右子樹的葉子個數return LeafSize(root->left) + LeafSize(root->right);
}

相當于節點個數功能的思路延伸，根為空返回0，左子樹與右子樹都為空返回1，最后遞歸左右子樹相加就得到了葉子節點的個數。

🌳3.3 二叉樹的創建和銷毀

??3.3.2二叉樹的創建

• 二叉樹的創建思路是：通過前序遍歷的數組"ABD##E##C##"構建二叉樹
• 只有前序是不可能構建出二叉樹的，但是在數組里用’#'表示NULL，這樣構建二叉樹就很容易了。
  

BTNode* BinaryTreeCreate(BTDataType* s, int* pi)
{//遇到'#',加加pi，然后返回NULLif (s[*pi] == '#'){(*pi)++;return NULL;}//malloc出來新的根節點BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = s[*pi];(*pi)++;//遞歸構建左子樹root->left = BinaryTreeCreate(s, pi);//遞歸構建右子樹root->right = BinaryTreeCreate(s, pi);return root;
}

??3.3.2 二叉樹的銷毀

銷毀的含義依然是：把空間還給操作系統。
銷毀二叉樹很簡單，用后序遍歷的思路，把打印數據改成free(釋放)節點即可。

//思路就是：使用后序遍歷思路銷毀
void TreeDestroy(BTNode* root)
{//根為空時，直接返回if (root == NULL){return;}TreeDestroy(root->left);//遞歸左子樹TreeDestroy(root->right);//遞歸右子樹free(root);//釋放根節點root = NULL;
}

🌳3.3 二叉樹接口測試

int main()
{//構建樹char str[] = "ABD##E##C##";int i = 0;BTNode* root = BinaryTreeCreate(str, &i);//測試功能PrevOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");int ATree = TreeSize(root);printf("%d\n", ATree);//5int BTree = TreeSize(root->left);printf("%d\n", BTree);//3int ALeaf = LeafSize(root);printf("%d\n", ALeaf);//3LevelOrder(root);//A B C D ETreeDestroy(root);return 0;
}

四、完整代碼

🌳4.1 BinaryTree.h

#pragma once#include<stdio.h>
#include<stdlib.h>//二叉樹
typedef char BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//左子樹struct BinaryTreeNode* right;//右子樹BTDataType data;//當前節點值域
}BTNode;#include "Queue.h"//二叉樹前序遍歷
void PrevOrder(BTNode* root);
//二叉樹中序遍歷
void InOrder(BTNode* root);
//二叉樹后序遍歷
void PostOrder(BTNode* root);
//二叉樹的層次
//核心思路：上層取出的時候，帶下一層進
void LevelOrder(BTNode* root);
//二叉樹節點的個數
int TreeSize(BTNode* root);
//二叉樹葉子的個數
int LeafSize(BTNode* root);
//二叉樹的銷毀
void TreeDestroy(BTNode* root);
//通過前序遍歷的數組"ABD##E##C##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* s, int* pi);

🌳4.2 BinaryTree.c

#include "BinaryTree.h"void PrevOrder(BTNode* root)
{//根為空就返回if (root == NULL){printf("NULL ");return;}//根 -> 左子樹 -> 右子樹printf("%c ", root->data);//打印根PrevOrder(root->left);//遞歸左子樹PrevOrder(root->right);//遞歸右子樹
}void InOrder(BTNode* root)
{//根為空就返回if (root == NULL){printf("NULL ");return;}//左子樹 -> 根 -> 右子樹InOrder(root->left);//遞歸左子樹printf("%c ", root->data);//打印根InOrder(root->right);//遞歸右子樹
}void PostOrder(BTNode* root)
{//根為空就返回if (root == NULL){printf("NULL ");return;}//左子樹 -> 右子樹 -> 根PostOrder(root->left);//遞歸左子樹PostOrder(root->right);//遞歸右子樹printf("%c ", root->data);//打印根
}int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}int LeafSize(BTNode* root)
{//根為空就返回0if (root == NULL){return 0;}//左右子樹為空，則返回1if (root->left == NULL && root->right == NULL){return 1;}//遞歸左子樹的葉子個數加遞歸右子樹的葉子個數return LeafSize(root->left) + LeafSize(root->right);
}//核心思路：上層取出的時候，帶下一層進
void LevelOrder(BTNode* root)
{//創建及初始化隊列Que q;QueueInit(&q);//空樹就不需要入隊列了//不是空樹就把根節點入隊列if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){//根節點出隊列BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->data);//左子樹入隊列if (front->left){QueuePush(&q, front->left);}//右子樹入隊列if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);
}//思路就是：使用后序遍歷思路銷毀
void TreeDestroy(BTNode* root)
{//根為空時，直接返回if (root == NULL){return;}TreeDestroy(root->left);//遞歸左子樹TreeDestroy(root->right);//遞歸右子樹free(root);//釋放根節點root = NULL;
}BTNode* BinaryTreeCreate(BTDataType* s, int* pi)
{//遇到'#',加加pi，然后返回NULLif (s[*pi] == '#'){(*pi)++;return NULL;}//malloc出來新的根節點BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = s[*pi];(*pi)++;//遞歸構建左子樹root->left = BinaryTreeCreate(s, pi);//遞歸構建右子樹root->right = BinaryTreeCreate(s, pi);return root;
}

🌳4.3 test.c

#include "BinaryTree.h"int main()
{//構建樹char str[] = "ABD##E##C##";int i = 0;BTNode* root = BinaryTreeCreate(str, &i);//測試功能PrevOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");int ATree = TreeSize(root);printf("%d\n", ATree);//5int BTree = TreeSize(root->left);printf("%d\n", BTree);//3int ALeaf = LeafSize(root);printf("%d\n", ALeaf);//3LevelOrder(root);TreeDestroy(root);return 0;
}