之前的順序表和鏈表都是一種線性的結構，樹是非線性的結構，
文章目錄
- 一、樹的概念
- 1.1.樹用代碼表示
- 二、二叉樹
- 2.1特殊的二叉樹
- 2.2.二叉樹的性質
- 2.3.二叉樹的存盤形式
- 2.3.1.順序存盤
- 2.3.2.鏈式存盤
- 2.4.二叉樹的遍歷
- 2.4.1.前序遍歷
- 2.4.2.中序遍歷
- 2.4.3.后序遍歷
- 2.5.二叉樹的一些題目
- 三、二叉樹的代碼實作
- 3.1.測驗代碼
一、樹的概念
樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成，當 n=0 時，稱為空樹，
- 樹的起始節點是一個特殊的結點，稱為根結點，它沒有前驅結點，
- 除根節點外，其余結點也是一個類似于樹結構的子樹，也就是說這個節點也有子節點，所以樹是一種遞回結構，
- 節點的度：一個節點含有的子樹的個數稱為該節點的度，比如A的度是3，B的度是2
- 葉節點或終端節點：度為0的節點稱為葉節點，
- 非終端節點或分支節點：度不為0的節點，
- 雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點，
- 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點，
- 兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點，但F、G不是兄弟節點，因為它們的父節點不相同，
- 樹的度：一棵樹中，最大的節點的度稱為樹的度，上圖中樹的度是3.
- 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，
- 樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4，
- 節點的祖先：從根到該節點所經分支上的所有節點；如上圖：J節點的祖先是EBA
- 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫，
- 森林：由m（m>0）棵互不相交的多顆樹的集合稱為森林，
注意，子樹和子樹之間是不能相交的，除了根節點外的其他節點只能有一個父節點
比如這種結構就不能稱為樹：
1.1.樹用代碼表示
樹要用C語言代碼表示起來還是比較麻煩的，因為一個節點的度是不確定性的，因此父節點該存幾個指標指向子節點是不清楚的，常見的表示法有雙親表示法，孩子表示法、孩子兄弟表示法等等
最常用的是孩子兄弟表示法：讓兄弟節點指向兄弟節點，父節點指向第一個孩子節點，因此只需要存兩個指標就可以了：
typedef int DataType;
struct Node
{
struct Node* firstChildl; // 第一個孩子結點
struct Node* ![pNextBrother] // 指向其下一個兄弟結點
DataType data; // 結點中的資料域
};
比如上面的樹用這種方法表示：
二、二叉樹
顧名思義，二叉樹就是節點的度不超過2的樹，也就是最多有兩個子樹，二叉樹的子樹有左右之分，其子樹的次序不能顛倒，一般稱為左子樹和右子樹，
2.1特殊的二叉樹
- 滿二叉樹
一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是(2K) -1（因為第一層節點是20，第二次是21，一直到最后一層K是2K，用等比數列求和可以得出總結點個數） ，則它就是滿二叉樹，
- 完全二叉樹
如果二叉樹的層數是K，前K-1層都是滿的，只有最后一層不滿，但是最后一層從左往右都是連續的，這種數就是完全二叉樹
注意完全二叉樹最后一層從左往右必須是連續的，下面的情況就不是完全二叉樹，因為D少一個左子樹，最后一層不連續：
2.2.二叉樹的性質
二叉樹的這些性質可以幫助我們做題：
- 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2(i-1)個結點，最少有1個節點.
- 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2h- 1，最小節點數是2h-1+1（最后一層最少有一個節點）.
- 對任何一棵二叉樹, 度為0的節點個數比度為2的節點個數多1
- 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h=Log2(n+1)（由2h- 1=n得出），
2.3.二叉樹的存盤形式
二叉樹一般可以使用兩種結構存盤，一種順序結構，一種鏈式結構，也就是類似于順序表和鏈表的形式，
2.3.1.順序存盤
順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹
會有空間的浪費，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，
2.3.2.鏈式存盤
用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系， 通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址，這種形式被稱作二叉鏈，如果再加入一個指向父節點的指標，那么這種形式的鏈表被稱作三叉鏈 ，這里主要用到的形式是二叉鏈，
2.4.二叉樹的遍歷
遍歷是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問，
二叉樹的遍歷分為三種：前序遍歷、中序遍歷和后續遍歷，
任何一顆二叉樹分為三個部分：1.根節點，2.左子樹，3.右子樹，這三種遍歷方式的區別在于訪問根節點的時機不同，
二叉樹的遍歷采用的是分治演算法：分而治之，大問題分成類似的子問題，子問題再分成子問題，直到子問題不可再分割，因此用代碼實作采用的是遞回方式，
2.4.1.前序遍歷
前序遍歷也就是先訪問根，它的遍歷順序是：根 左子樹 右子樹
每到一個節點，都會優先訪問以該節點為子樹的根節點，然后訪問左子樹，再訪問右子樹，
根節點A永遠被第一個遍歷：
2.4.2.中序遍歷
中序遍歷的順序是：左子樹 根 右子樹
每到一個節點，都會優先訪問以該節點為子樹的左子樹，然后根節點，再訪問右子樹，
根節點A的左邊是左子樹，右邊是右子樹
2.4.3.后序遍歷
后序遍歷的順序是：左子樹 右子樹 根
每到一個節點，都會優先訪問以該節點為子樹的左子樹，然后訪問右子樹，最后訪問根，
根節點A最后一個被遍歷：
2.5.二叉樹的一些題目
某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ ）
A 不存在這樣的二叉樹
B 200
C 198
D 199
由性質可知：對任何一棵二叉樹, 度為0的節點個數比度為2的節點個數多1，因此葉子節點的個數是200
在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
A n
B n+1
C n-1
D n/2
假設度為0的節點有X0個，度為1的節點有X1個，度為2的節點有X2個，由題意可知X0+X1+X2=2n
因為度為0的節點比度為2的節點多1，所以X2=X0-1，因此2X0+X1-1=2n，
完全二叉樹中度為1的節點最多有一個，所以X1=1，因此X0=n
（如果X1=0，則算不出整數，所以X1=1）
一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（ ）
A 11
B 10
C 8
D 12
假設這棵樹的高度是h，由于是完全二叉樹，所以假設最后一層缺了X個節點
由題意得出公式2^h-1-X=531;
最后一層最少有一個，最多一個都不缺，因此X的范圍是0~~2^(h-1)-1
帶入ABCD的范圍可以得出結果h=10
某完全二叉樹按層次輸出（同一層從左到右）的序列為 ABCDEFGH ，該完全二叉樹的前序序列為（）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
二叉樹的前序遍歷和中序遍歷如下：前序遍歷：EFHIGJK;中序遍歷：HFIEJKG.則二叉樹根結點為
（）
A E
B F
C G
D H
前序和后序確定根，中序確定左右子樹的區間，因此只需要前序+中序或者后序+中序即可還原二叉樹：通過前序遍歷確定根節點為E,左子樹的根為F，再通過中序確定F的左右子樹為HI，再通過前序確定右子樹的根是G，通過中序確定G沒有右子樹，再通過前序確定G的左子樹節點是J，最后通過中序確定J的右子樹是K，這里如果K是J的左子樹，那么中序遍歷應該是KJ，而不是JK
設一課二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為____，
A adbce
B decab
C debac
D abcde
前序遍歷是abcde
三、二叉樹的代碼實作
- 宣告二叉樹的結構體
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;
- 前序遍歷
//前序
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
為了更好的說明前序遍歷的邏輯，這里以下面的代碼舉例：
int main()
{
BTNode*A = (BTNode*)malloc(sizeof(BTNode));
A->data = 'A';
A->left = NULL;
A->right = NULL;
BTNode* B = (BTNode*)malloc(sizeof(BTNode));
B->data = 'B';
B->left = NULL;
B->right = NULL;
BTNode* C = (BTNode*)malloc(sizeof(BTNode));
C->data = 'C';
C->left = NULL;
C->right = NULL;
BTNode* D = (BTNode*)malloc(sizeof(BTNode));
D->data = 'D';
D->left = NULL;
D->right = NULL;
BTNode* E = (BTNode*)malloc(sizeof(BTNode));
E->data = 'E';
E->left = NULL;
E->right = NULL;
A->left = B;
A->right = C;
B->left = D;
B->right = E;
PrevOrder(A);
}
這個二叉樹的結構如下：
程式的流程圖：
- 中序
//中序
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;
}
如果數的節點不等于空指標，則回傳這個左子樹的函式和右子樹的函式再加上這個節點的個數1：
- 求葉子節點的個數
//求葉子個數
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)//葉子節點的左右子樹都是空
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
- 求樹的深度
//求樹的深度
int maxDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
如果是空，則高度為0.
如果是非空，則對于一個節點，先求該節點左右子樹的深度，該節點的深度等于左右子樹深度中大的那個深度+1
- 判斷是否為平衡二叉樹（每個節點的左右子樹的高度差的絕對值不超過1）
//判斷是否為平衡二叉樹
bool isBalanced(BTNode* root) {
if (root == NULL)
{
return true;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left)
&& isBalanced(root->right);//abs是求絕對值
}
- 銷毀二叉樹
//銷毀二叉樹
void DestoryTree(BTNode** root)//要將root置為空指標，這里傳指標的地址
{
if ((*root) = NULL)
{
return;
}
DestoryTree((*root)->left);
DestoryTree((*root)->right);
free(*root);
(*root) = NULL;
}
3.1.測驗代碼
#include<stdio.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;
//求節點的個數
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//求葉子個數
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
//求樹的深度
int maxDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//判斷是否為平衡二叉樹
bool isBalanced(BTNode* root) {
if (root == NULL)
{
return true;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left)
&& isBalanced(root->right);
}
//銷毀二叉樹
void DestoryTree(BTNode** root)
{
if ((*root) = NULL)
{
return;
}
DestoryTree((*root)->left);
DestoryTree((*root)->right);
free(*root);
(*root) = NULL;
}
//前序
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 main()
{
BTNode*A = (BTNode*)malloc(sizeof(BTNode));
A->data = 'A';
A->left = NULL;
A->right = NULL;
BTNode* B = (BTNode*)malloc(sizeof(BTNode));
B->data = 'B';
B->left = NULL;
B->right = NULL;
BTNode* C = (BTNode*)malloc(sizeof(BTNode));
C->data = 'C';
C->left = NULL;
C->right = NULL;
BTNode* D = (BTNode*)malloc(sizeof(BTNode));
D->data = 'D';
D->left = NULL;
D->right = NULL;
BTNode* E = (BTNode*)malloc(sizeof(BTNode));
E->data = 'E';
E->left = NULL;
E->right = NULL;
A->left = B;
A->right = C;
B->left = D;
B->right = E;
PrevOrder(A);
printf("\n");
InOrder(A);
printf("\n");
PostOrder(A);
printf("\n");
printf("%d\n", TreeSize(A));
printf("%d\n", TreeSize(B));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/292349.html
標籤：其他
上一篇：MYSQL性能調優01_索引的概述、B+樹、InnoDB索引實作(聚集)、聯合索引的設定
下一篇：什么是4G工業智能網關？·