第6章 樹型結構
目錄- 一、樹的基本概念
- 二、樹類的定義
- 三、樹的存盤結構 （大概率不考）
- 3.1 雙親表示法
- 3.1.1 樹的存盤結構（雙親表示法）
- 3.2 孩子表示法
- 3.3 孩子兄弟表示法
- 3.1 雙親表示法
- 四、樹的遍歷
- 五、樹的線性表示（大綱未規定）
- 5.1 樹的括號表示
- 5.2 樹的層號表示
- 六、演算法設計題
- 七、錯題集
一、樹的基本概念
- 樹：由 \(n(n>=0)\) 個結點構成的有限集合
- 根：有且僅有一個特定的結點
- 結點的度：結點擁有的子女數
- 樹的度：所有結點度的最大值
- 度為 \(0\) 的結點：終端結點（葉子結點）
- 度不為 \(0\) 的結點：非終端結點（分支結點）
- 樹枝：連接兩個結點的線段
- 結點的層次：根結點為第 \(1\) 層，根的子女結點為第 \(2\) 層
- 樹的高度：樹中結點最大層次樹
- 有序樹：任意結點的子樹看成是從左到右有次序，不能隨意交換，否則為無序樹
- 森林：\(m(m>=0)\) 棵互不相交的樹構成的集合（在森林的每棵樹之上加一個共同的根，森林則成了一棵樹）
二、樹類的定義
- 略
三、樹的存盤結構 （大概率不考）
- 樹的三種常用存盤結構：雙親表示法、孩子表示法、孩子兄弟表示法
3.1 雙親表示法
- 樹的結點包含兩個資訊：結點的值 \(data\) 和體現結點之間相互關系的屬性——該結點的雙親 \(parent\)
3.1.1 樹的存盤結構（雙親表示法）
#define MAXSIZE 100 // 樹中結點個數的最大值
typedef char datatype; // 結點值的型別
// 結點的型別
typedef struct node {
datatype data;
int parent; // 結點雙親的下標
} node;
// 樹的型別
typedef struct tree {
node treelist[MAXSIZE]; // 存放結點的陣列
int length, root; // 樹中實際所含結點的個數及根節點的位置
} tree;
3.2 孩子表示法
- 略
3.3 孩子兄弟表示法
- 略
四、樹的遍歷
-
前序遍歷：首先訪問根結點，再從左到右依次按前序遍歷的方式訪問根結點的每一棵子樹
-
后序遍歷：首先按后序遍歷的方式訪問根結點的每一棵子樹，然后再訪問根結點
-
層序遍歷：首先訪問第一層上的根結點，然后從左到右依次訪問第二層上的所有結點，……，最后訪問樹中最低一層的所有結點，
-
圖樹的遍歷：
-
樹的遍歷常用操作：
- 樹的前續遍歷的遞回演算法
- 樹的后序遍歷的遞回演算法
- 按前序遍歷順序建立一顆 \(3\) 度樹
- 樹的層次遍歷演算法
五、樹的線性表示（大綱未規定）
- 注：僅憑借樹的某種遍歷序列有時無法唯一地確定一棵樹，但只要在遍歷序列的基礎上加上一些附加資訊，即可唯一地確定一棵樹
5.1 樹的括號表示
-
常用操作：
- 樹的括號表示到樹的孩子表示的轉換演算法
-
圖樹的括號表示：
5.2 樹的層號表示
-
常用操作：
- 樹的層號表示到樹的擴充孩子表示的轉換演算法
-
圖樹的層號表示：
六、演算法設計題
- 略
七、錯題集
-
樹最適合用來表示具有有序性和層次性的資料
-
在選擇存盤結構時，既要考慮資料值本身的存盤，還需要考慮資料間關系的存盤
-
（真題）對于一顆具有 \(n\) 個結點的樹，該樹中所有結點的度數之和為 \(n-1\)
-
已知一棵度為 \(m\) 的樹中有 \(n_1\) 個度為 \(1\) 的結點， \(n_2\) 個度為 \(2\) 的結點，……，\(n_m\) 個度為
\(m\) 的結點，問該樹中有多少個葉子結點？
-
樹中結點總數 \(n=n_0+n_1+n_2+…+n_m\)
-
樹中結點的度數之和為 \(n-1\)，且有：\(n-1=n_1+2*n_2+3*n_3+\cdots+m*n_m\) （用上題 \(3\) 的定理）
-
所以葉子結點個數為：\(n_0=1+n_2+2*n_3+\cdots+(m-1)*n_m\)
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/155586.html
標籤：其他
上一篇：第5章 遞回
下一篇：第7章 二叉樹