文章目錄
- 樹和森林
- 雙親表示法
- C語言的類型描述
- 樹結構
- 結點結構
- 孩子連結清單法
- C語言的類型描述
- 樹結構
- 帶雙親的孩子連結清單
- 孩子兄弟表示法（二叉樹表示法、二叉連結清單表示法）
- 樹與二叉樹的轉換
- 将樹轉換成二叉樹
- 将二叉樹轉換成樹
- 森林與二叉樹的轉換
- 森林轉換成二叉樹（二叉樹與多棵樹之間的關系）
- 二叉樹轉換成森林
- 樹和森林的周遊
- 樹的周遊（三種方式）
- 森林的周遊
- 先序周遊
- 中序周遊
- 例
樹和森林
森林：是m（m≥0）棵互不相交的樹的集合。
樹（Tree）是n（n≥0）個結點的有限集。若n = 0，則稱為空樹。
若n > 0，（1）有且僅有一個特點的根（Root）的結點；
（2）其餘結點可分為m（m≥0）個互不相交的有限集T1, T2, T3, …, Tm。
雙親表示法
實作：定義數組結構存放樹的結點，每個結點含兩個域：
資料域：存放結點本身資訊。
雙親域：訓示本結點的雙親結點在數組中的位置。
特點：找雙親容易，找孩子難。
C語言的類型描述
typedef struce PTNode {
TElemType data;
int parent; // 雙親位置域
} PTNode; 樹結構
#define MAX_TREE_SIZE 100
typedef struce {
PTNode nodes[MAX_TREE_SIZE];
int r, n; // 根結點的位置和結點個數
} PTree; 結點結構
孩子連結清單法
把每個結點的孩子結點排列起來，看成是一個線性表，用單連結清單存儲，則n個結點有n個孩子連結清單（葉子的孩子連結清單為空表）。而n個頭指針又組成一個線性表，用順序表（含n個元素的結構數組）存儲。
特點：找孩子容易，找雙親難。
C語言的類型描述
孩子結點結構：
typedef struct CTNode {
int child;
struct CTNode *next;
} *ChildPtr; 雙親結點結構：
typedef struct {
TElemType data;
ChildPtr firstchild; // 孩子連結清單頭指針
} CTBox; 樹結構
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n, r; // 結點數和根節點位置
} CTree; 帶雙親的孩子連結清單
犧牲空間來換取時間，找雙親和孩子都友善。
孩子兄弟表示法（二叉樹表示法、二叉連結清單表示法）
實作：用二叉連結清單作樹的存儲結構，連結清單中每個結點的兩個指針域分别指向其第一個孩子結點和下一個兄弟結點。
typedef struct CSNode {
ElemType data;
struct CSNode *firstchild,
} 樹與二叉樹的轉換
将樹轉化為二叉樹進行處理，利用二叉樹的算法來實作對樹的操作。
由于樹和二叉樹都可以用二叉連結清單作存儲結構，則以二叉連結清單作媒介可以導出樹與二叉樹之間的一個對應關系。
将樹轉換成二叉樹
① 加線：在兄弟之間加一條線。
② 抹線：對每個結點，除了其左孩子外，去除其餘其餘孩子之間的關系。
③ 旋轉：以樹的根節點為軸心，将整樹順時針旋轉45°。
樹變二叉樹：兄弟相連留長子。
将二叉樹轉換成樹
① 加線：若p結點是雙親結點的左孩子，則将p的右孩子，右孩子的右孩子…沿分支找到的所有右孩子，都與p的雙親用線連起來。
② 抹線：抹掉原二叉樹中雙親與右孩子之間的連線。
③ 調整：将結點按層次排列，形成樹結構。
二叉樹變樹：左孩右右連雙親，去掉原來右孩線。
森林與二叉樹的轉換
森林轉換成二叉樹（二叉樹與多棵樹之間的關系）
① 将各棵樹分别轉換成二叉樹。
② 将每棵樹的根節點用線相連。
③ 以第一棵樹根節點為二叉樹的根，再以根節點為軸心，順時針旋轉，構成二叉樹型結構。
森林變二叉樹：樹變二叉根相連。
二叉樹轉換成森林
① 抹線：将二叉樹中根節點與其右孩子連線，及沿右分支搜尋到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹。
② 還原：将孤立的二叉樹還原成樹。
二叉樹變森林：去掉全部右孩線，孤立二叉再還原。
樹和森林的周遊
樹的周遊（三種方式）
① 先根（次序）周遊：
若樹不空，則先通路根結點，然後依次先根周遊各棵子樹。
② 後根（次序）周遊：
若樹不空，則先依次後根周遊各棵子樹，然後通路根節點。
③ 按層次周遊：
若樹不空，則自上而下自左至右通路樹中每個結點。
周遊結果：
先根周遊：ABCDE
後根周遊：BDCEA
按層次周遊：ABCED
森林的周遊
将森林看做由三部分組成：
1.森林中第一棵樹的根節點；
2.森林中第一棵樹的子樹森林；
3.森林中其他樹構成的森林。
先序周遊
若森林不空，則
1.通路森林中第一棵樹的根結點；
2.先序周遊森林中第一棵樹的子樹森林；
3.先序周遊森林中（除第一棵樹之外）其餘樹構成的森林。
即：依次從左至右對森林中的每一棵樹進行先根周遊。
中序周遊
若森林不空，則
1.中序周遊森林中第一棵樹的子樹森林；
2.通路森林中第一棵樹的根結點；
3.中序周遊森林中（除第一棵樹之外）其餘樹構成的森林。
即：依次從左至右對森林中的每一棵樹進行後根周遊。