目錄

樹的存儲方法

雙親表示法

孩子表示法

孩子兄弟表示法

樹、森林與二叉樹的轉換

樹轉換成二叉樹

森林轉換成二叉樹

二叉樹轉換成森林

樹與森林的遍歷

樹的遍歷

森林的遍歷

---

樹的存儲方法

雙親表示法

這種存儲結構采用一組連續空間來存儲每個結點，同時在每個結點中增設一個偽指針，指示其雙親結點在數組中的位置，根結點下標為0，其偽指針域為-1。

孩子表示法

孩子表示法是將每個結點的孩子結點視為一個線性表，且以單鏈表作為存儲結構，則n個結點就有n個孩子鏈表(葉結點的孩子鏈表為空表)。而n個頭指針又組成一個線性表，為便于查找，可采用順序存儲結構。

孩子兄弟表示法

孩子兄弟表示法又稱二叉樹表示法，即以二叉鏈表作為樹的存儲結構。孩子兄弟表示法使每個結點包括三部分內容:結點值、指向結點第一個孩子結點的指針，以及指向結點下一個兄弟結點的指針，其中左指針指向第一個孩子，右指針指向第一個兄弟。

孩子兄弟表示法比較靈活，其最大的優點是可以方便地實現樹轉換為二叉樹的操作，易于查找結點的孩子等,但缺點是從當前結點查找其雙親結點比較麻煩。若為每個結點增設一個parent域指向其父結點，則查找結點的父結點也很方便。

孩子兄弟表示法代碼如下：

typedef struct CSNode{int data;struct CSNode *firstchild, *nextsibling;
}CSNode,*CSTree;

樹、森林與二叉樹的轉換

樹轉換成二叉樹

樹轉換為二叉樹的規則是：每個節點的左指針指向它的第一個孩子，右指針指向它在樹中的相鄰右兄弟。這種規則也被稱為“左孩子右兄弟”表示法。由于根節點在樹中沒有兄弟，因此樹轉換得到的二叉樹的根節點沒有右子樹。

將樹轉換為二叉樹的畫法可以按照以下步驟進行：

1. 在兄弟節點之間加連線：對于樹中的每個節點，將其所有子節點（即兄弟節點）之間用線連接起來。
2. 保留第一個孩子的連線，刪除其他孩子的連線：對于每個節點，只保留它與第一個孩子的連線，而刪除與其他子節點的連線。
3.順時針旋轉 45°：以樹的根節點為軸心，將整個結構順時針旋轉 45°，使得轉換后的二叉樹符合“左孩子右兄弟”的規則。

示例如下：

森林轉換成二叉樹

將森林轉換為二叉樹的規則與樹轉換為二叉樹類似，具體步驟如下：

1. 先將森林中的每棵樹分別轉換為二叉樹，轉換規則遵循“左孩子右兄弟”原則，即每個節點的左指針指向其第一個孩子，右指針指向其相鄰的右兄弟。
2. 連接各二叉樹：由于每棵樹轉換為二叉樹后，其右子樹必定為空，因此可以將森林中第二棵樹的根節點視為第一棵樹根節點的右兄弟，即將第二棵樹對應的二叉樹作為第一棵二叉樹根的右子樹；同理，將第三棵樹對應的二叉樹作為第二棵二叉樹根的右子樹，依次類推，最終將整個森林連接成一棵二叉樹。

二叉樹轉換成森林

二叉樹轉換為森林的規則如下：

1. 確定第一棵樹：如果二叉樹非空，那么二叉樹的根節點及其左子樹對應森林中的第一棵樹。因此，需要將根節點的右鏈斷開。
2. 遞歸處理剩余部分：斷開右鏈后，二叉樹根的右子樹可以看作是由森林中除第一棵樹之外的其余樹轉換而來的二叉樹。對這個右子樹重復上述操作，即繼續斷開右鏈，提取下一顆樹，直到最后只剩下一棵沒有右子樹的二叉樹為止。
3.轉換為樹：將每棵提取出的二叉樹依次轉換為樹。最終，這些樹組合起來就是原森林。

二叉樹轉換為樹或森林的過程是唯一的。

樹與森林的遍歷

樹的遍歷

樹的遍歷是指按照某種順序訪問樹中的每個節點，并且每個節點只被訪問一次。主要的遍歷方式有兩種：

先根遍歷

1. 如果樹非空，先訪問根節點。
2. 然后依次遍歷根節點的每棵子樹，在遍歷子樹時仍然按照“先根后子樹”的規則進行。
3. 先根遍歷的序列與這棵樹轉換為二叉樹后的先序遍歷序列相同。

后根遍歷：

1. 如果樹非空，先依次遍歷根節點的每棵子樹，在遍歷子樹時仍然按照“先子樹后根”的規則進行。
2. 遍歷完所有子樹后，再訪問根節點。
3. 后根遍歷的序列與這棵樹轉換為二叉樹后的中序遍歷序列相同。

森林的遍歷

森林的遍歷方法基于森林和樹的遞歸定義，主要有兩種遍歷方式：

先序遍歷森林：

1. 如果森林非空，先訪問森林中第一棵樹的根節點。
2. 然后先序遍歷第一棵樹中根節點的子樹森林（即第一棵樹的子樹部分）。
3. 最后，先序遍歷除去第一棵樹之后剩余的樹構成的森林。

中序遍歷森林：

1. 如果森林非空，先中序遍歷森林中第一棵樹的根節點的子樹森林（即第一棵樹的子樹部分）。
2. 然后訪問第一棵樹的根節點。
3. 最后，中序遍歷除去第一棵樹之后剩余的樹構成的森林。