?? 歡迎大家來到貝蒂大講堂??
🎈🎈養成好習慣，先贊后看哦~🎈🎈
所屬專欄：數據結構與算法
貝蒂的主頁：Betty’s blog
1. 樹
1.1. 樹的定義
樹是一種非線性的數據結構，它是由n（n >= 0）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
在樹中有一個特殊的結點，稱為根結點，根節點沒有前驅結點
除根節點外，其余結點被分成M(M > 0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1 <= i<= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼因此，樹是遞歸定義的。
注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構
1.2. 樹的基本概念
| 術語 | 定義 |
|---|---|
| 節點的度 | 一個節點含有的子樹的個數稱為該節點的度，比如說節點1的度為2 |
| 葉節點 | 度為0的節點，比如說4，5，6節點 |
| 分支節點 | 度不為0的節點，比如說2，3節點 |
| 雙親節點 | 若一個節點含有子節點，則這個節點稱為其子節點的父節點。比如說2是4，5的雙親節點 |
| 子節點 | 一個節點含有的子樹的根節點稱為該節點的子節點，比如說4，5是2的子節點 |
| 兄弟節點 | 具有相同父節點的節點互稱為兄弟節點，比如說4，5就是兄弟節點 |
| 樹的度 | 一棵樹中，最大的節點的度稱為樹的度，比如說上面這棵樹的度為2 |
| 節點的層次 | 從根開始定義起，根為第1層，根的子節點為第2層，以此類推 |
| 樹的高度或深度 | 樹中節點的最大層次，比如說上面這棵樹的高度為3 |
| 堂兄弟節點 | 雙親在同一層的節點互為堂兄弟，比如說5，6節點 |
| 節點的祖先 | 從根到該節點所經分支上的所有節點，比如說1就是所有節點的祖先 |
| 子孫 | 以某節點為根的子樹中任一節點都稱為該節點的子孫，比如說所有節點都是1的子孫 |
| 森林 | 由m（m>0）棵互不相交的樹的集合稱為森林 |
1.3. 樹的表示方法
下面我們將采用三種方式表示下面這課樹：
1.3.1. 雙親表示法
雙親表示法采用順序表的方式存儲，即用順序表存儲各個節點的數據，并且同時存儲其雙親節點的下標。注意：根節點沒有雙親節點，所以特別記為-1。
#define MAX_SIZE 10
typedef int DataType;
typedef struct Node
{DataType data;//數據域int parent; //雙親結點在數組中的位置下標
}Node;
typedef struct PTree
{//存放樹中所有結點Node tnode[MAX_SIZE];//當前結點個數int n;
}PTree;
1.3.2. 樹的孩子表示法
樹的孩子表示法就是采用順序表與鏈表結合的形式，用順序表存儲樹的值與鏈表的頭節點，而鏈表的頭節點存儲其孩子節點在順序表中的下標，若沒有則記為空(N)。
#define MAX_SIZE 10
#define DataType int
typedef struct ListNode
{int child;struct ListNode* next;
}ListNode;
typedef struct TNode
{DataType data;//孩子鏈表的頭指針ListNode* firstchild;
}TNode;
typedef struct PTree{//存儲結點的數組TNode nodes[MAX_SIZE];int n; //結點數量
}PTree;
1.3.3. 左孩子右兄弟表示法
最常用表示樹的的方法就是左孩子右兄弟表示法，即定義兩個指針，讓左指針指向子節點，右指針指向兄弟節點。
如果沒有節點，則都指向空。
typedef int DataType;
struct Node
{struct Node* leftChild1; // 孩子結點struct Node* rightBrother; // 指向其下一個兄弟結點DataType _data; // 結點中的數據域
};
1.4. 樹的實際應用
在linux環境下目錄結構就是有一顆樹構成，而在Windows環境下，目錄許多內容并不交叉，所以是由森林構成。
2. 二叉樹
2.1. 二叉樹的定義
一棵二叉樹是結點的一個有限集合，該集合可能為空，也可以由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成。
注意：
- 二叉樹不存在度大于2的結點
- 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
2.2. 特殊的二叉樹
2.2.1. 滿二叉樹
滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是N=2k -1,則它就是滿二叉樹。
2.2.2. 完全二叉樹
**完全二叉樹：**完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
2.3. 二叉樹的特點
- 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2i -1個結點。
- 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數N=1+2+4+…+2i -1=2h -1。
- 對任何一棵二叉樹, 如果度為0其葉結點個數為N0, 度為2的分支結點個數為N2, 則有 N0＝N2＋1
證明如下：
假設節點總數為N，如果度為0其葉結點個數為N0, 度為1的分支結點個數為N1，度為2的分支結點個數為N2
節點總數：N=N0 + N1+ N2 又因為二叉樹的邊比節點樹少1，所以N= N1 +2N2+1=>N0 + N1+ N2= N1 +2N2+1=>N0＝N2＋1
-
若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h =log2 (n+1) 。
-
對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編號，則對
? 于序號為i的結點有：
? 1. 若i > 0，i位置節點的雙親序號：(i - 1) / 2；i = 0，i為根節點編號，無雙親節點。
? 2. 若2i + 1 < n，左孩子序號：2i + 1，2i + 1 >= n否則無左孩子。
? 3. 若2i + 2 < n，右孩子序號：2i + 2，2i + 2 >= n否則無右孩子。
2.4. 二叉樹的存儲
2.4.1. 數組存儲
我們可以通過雙親節點與子節點下標之間的映射關系將二叉樹存儲在數組中，如果節點為空，我們以INT_MAX來標記。
2.4.2. 鏈式存儲
除了數組存儲，我們也可以鏈式存儲二叉樹。
typedef struct BinaryTreeNode
{struct BinTreeNode* left; // 左孩子struct BinTreeNode* right; // 右孩子DataType data; // 當前節點值域
}BTree;
2.5. 二叉樹的遍歷
二叉樹的遍歷一般有四種方法：前序遍歷，中序遍歷，后序遍歷，層序遍歷。
2.5.1. 前序遍歷
前序遍歷：先遍歷根節點，再依次遍歷左子樹，右子樹。而遍歷左子樹，又要先遍歷根節點，再依次遍歷左子樹，右子樹…直至遍歷到空樹。
- 遞歸實現
void PreOrder(BTree*root)
{if (root == NULL){return;}printf("%d ", root->data);//根節點PreOrder(root->left);//左子樹PreOrder(root->right);//右子樹
}
- 非遞歸實現
非遞歸實現樹的前序遍歷我們需要借助棧這個數據結構，來達到與遞歸一樣的深度優先遍歷的目的。并且棧中存儲元素為BTree*。
typedef BTree* STDataType;void PreOrder(BTree* root){Stack s; InitStack(&s); BTree*p = root;// p為遍歷指針while (p || !IsEmpty(&s)) // 棧不為空或p不為空時循環{if(p!=NULL)//入棧{printf("%d ", p->data);//根節點StackPush(&s, p);p = p->left;}else//出棧，訪問右子樹{p = StackTop(&s);//訪問原本雙親節點StackPop(&s); // 棧頂元素出棧p = p->right; //訪問} }}
2.5.2. 中序遍歷
中序遍歷：先遍歷左子樹，再依次遍歷根節點，右子樹。而遍歷左子樹，又要先遍歷左子樹，再依次遍歷根節點，右子樹…直至遍歷到空樹。
- 遞歸實現
void Inorder(BTree*root)
{if (root == NULL){return;}PreOrder(root->left);//左子樹printf("%d ", root->data);//根節點PreOrder(root->right);//右子樹
}
- 非遞歸實現
非遞歸實現樹的中序遍歷我們需要借助棧這個數據結構，來達到與遞歸一樣的深度優先遍歷的目的。并且棧中存儲元素為BTree*。
typedef BTree* STDataType;void Inorder(BTree* root){Stack s;InitStack(&s);BTree* p = root;// p為遍歷指針while (p || !IsEmpty(&s)) // 棧不為空或p不為空時循環{if (p != NULL)//入棧{StackPush(&s, p);p = p->left;}else//出棧，訪問右子樹{p = StackTop(&s);//訪問原本雙親節點StackPop(&s); // 棧頂元素出棧printf("%d ", p->data);p = p->right; //訪問}}}
2.5.3. 后序遍歷
后序遍歷：先遍歷左子樹，再依次遍歷右子樹，根節點。而遍歷左子樹，又要先遍歷左子樹，再依次遍歷右子樹，根節點…直至遍歷到空樹。
- 遞歸實現
void Postorder(BTree*root)
{if (root == NULL){return;}PreOrder(root->left);//左子樹PreOrder(root->right);//右子樹printf("%d ", root->data);//根節點
}
- 非遞歸實現
非遞歸實現樹的后序遍歷我們需要借助棧這個數據結構，來達到與遞歸一樣的深度優先遍歷的目的。并且棧中存儲元素為BTree*。
void Postorder(BTree* root)
{Stack s;InitStack(&s);BTree* p = root;// p為遍歷指針BTree* v = root;// v標記已訪問節點while (p || !IsEmpty(&s)) // 棧不為空或p不為空時循環{while(p != NULL)//入棧{StackPush(&s, p);p = p->left;}p = StackTop(&s);//訪問雙親節點if (p->right && p->right != v)//存在右子樹，且沒有被訪問{p = p->right;//訪問}else//沒有右子樹或者右子樹已被訪問{printf("%d ", p->data);v = p;//記錄當前訪問的節點p = NULL;//防止重復訪問左子樹StackPop(&s);// 棧頂元素出棧}}
}
2.5.4. 層序遍歷
層序遍歷顧名思義就是一層一層地遍歷，這時就需要借助一個數據結構：隊列來輔助實現。
void leverOrder(BTree* root, Queue* pq)
{if (root == NULL)//為空直接返回{return;}QueuePush(pq, root);//插入第一個節點while (!QueueEmpty(pq))//隊列不為空{BTree* p = QueueFront(pq);printf("%d ", p->val);QueuePop(pq);if (p->left != NULL)//帶入左孩子{QueuePush(pq, p->left);}if (p->right != NULL)//帶入右孩子{QueuePush(pq, p->right);}}
}
)
