第五章 樹與二叉樹
小題考頻：30
大題考頻：8
5.4 樹、森林
難度：☆☆☆
知識總覽
5.4.1 樹的存儲結構
5.4.2 樹、森林與二叉樹的轉化
5.4.3 樹和森林的遍歷
5.4.1 樹的存儲結構
樹的邏輯結構
樹是一種遞歸定義的數據結構
一棵樹要么是空樹，要么至少有一個根結點，根結點的下方可能有零棵或多棵互不相交的子樹。
二叉樹：一個分支結點最多只能有兩棵子樹
樹：一個分支結點可以有多棵子樹
如何用順序存儲來存儲樹這種數據結構？
回顧：二叉樹的順序存儲
二叉樹的順序存儲：按照完全二叉樹中的結點順序，將各結點存儲到數組的對應位置。數組下標反映結點之間的邏輯關系
順序存儲二叉樹時，結點編號會和完全二叉樹對應。
那么這種思路能否推廣到普通的樹？
如何實現樹的順序存儲？
由于每個分支結點的子樹數量不確定，所以沒有與之對應的“完全樹”，單純依靠數組下標無法判斷結點之間的邏輯關系。
可以發(fā)現樹中，除了根結點外，其他任意結點都有且只有一個雙親結點（父結點）。
思路：用數組順序存儲各個結點。每個結點對應一個數組下標，在其中保存數據元素、指向雙親結點（父結點）的“指針”
樹的存儲1：雙親表示法
數組元素中，包含兩個字段，第一個字段表示數據元素，第二個字段用一個int型變量指明雙親在數組中的下標是多少。
用剛才定義的結構體聲明一個數組。
最后記錄結點的總數。
拓展：雙親表示法存儲“森林”
雙親表示法的優(yōu)缺點
優(yōu)點：找雙親（父結點）好
缺點：找孩子難，要遍歷整個數組
應用場景：找父親多，找孩子少，Eg.并查集
樹的存儲2：孩子表示法
在每個數組在鏈表元素中，保留一個鏈表頭指針，如果其有孩子，在鏈表中保存所有孩子結點的編號
孩子表示法是順序存儲+鏈式存儲結合
一個數組元素中包含data和一個鏈表CTNode的指針，鏈表結點中保存孩子的編號以及指向下一個鏈表結點的指針。
用剛才定義的結構體CTBox聲明一個數組，存儲各結點的信息。
并記錄結點總數和根的位置。
拓展：孩子表示法存儲“森林”
用孩子表示法存儲森林，需要記錄多個根的位置
孩子表示法的優(yōu)缺點
優(yōu)點：找孩子好
缺點：找雙親（父結點）難，要遍歷整個數組
應用場景：找孩子多，找父親少，Eg.服務流程樹【辦理業(yè)務請按1】
樹的存儲3：孩子兄弟表示法
鏈式實現
結構體包含數據，和兩個指針，第一個指針指向第一個孩子，第二個指針指向右邊一個兄弟【類似二叉樹結點的定義】
采用二叉鏈表實現
根結點是A，左指針指向B，右指針指向NULL；
C是B的右邊第一個兄弟結點，連到B的右指針，D結點連到C的右指針；
E是B的第一個孩子，連到B的左指針；
F是E的右邊第一個兄弟結點，連到E的右指針，G結點連到F的右指針，H連到G的右指針，I連到H的右指針，J連到I的右指針；
K是E的第一個孩子，連到E的左指針。
孩子兄弟表示法形態(tài)和二叉樹類似。
拓展：孩子兄弟表示法存儲“森林”
把樹根C看做B的兄弟，連到B右指針上，以此類推。
5.4.2 樹、森林與二叉樹的轉化
樹->二叉樹的轉換
用孩子兄弟表示法存儲樹或者森林的時候會呈現出和二叉樹類似的形態(tài)。
樹、森林與二叉樹的轉換本質上就是畫出用孩子兄弟表示法表示的樹和森林。
樹 -> 二叉樹轉換技巧：
① 先在二叉樹中，畫一個根結點。
② 按**“樹的層序”**依次處理每個結點。
處理一個結點的方法是：如果當前處理的結點在樹中有孩子，就把所有孩子結點“用右指針串成糖葫蘆”，并在二叉樹中把第一個孩子掛在當前結點的左指針下方
Eg1：
A結點：
----->
B結點：
----->
C結點：
H結點：
Eg2.
森林->二叉樹的轉換
思路同上。
注意，第一步：森林中各樹的根結點視為兄弟，用右指針串起來。
Eg2.
二叉樹->樹的轉換
還原A結點：
以此類推還原。
Eg2.
二叉樹->森林的轉換
原理類似。
注意，先將根節(jié)點和一串右指針還原成多棵樹的根結點。
Eg2.
5.4.3 樹和森林的遍歷
樹的邏輯結構
有遞歸特性，可以用遞歸算法來實現對樹的遍歷
樹的先根遍歷
訪問根結點
visit(R)，接下來用while循環(huán)來檢查其還有沒有下一個沒有被訪問過的子樹。
如果有，那么對子樹也采取先根遍歷的策略。
樹的先根遍歷序列與這棵樹相應二叉樹的先序序列相同。
樹的后根遍歷
原理類似，處理完所有子樹時訪問結點。
樹的后根遍歷序列與這棵樹相應二叉樹的后序序列相同。
樹的層次遍歷
實現思路和二叉樹一樣，用一個輔助隊列來實現
根結點入隊：
隊頭元素出隊，該元素的孩子依次入隊
重復該過程
盡量橫向探索，也叫廣度優(yōu)先遍歷。
那么先根遍歷和后根遍歷，也叫深度優(yōu)先遍歷。
森林的先序遍歷
森林去掉根結點后各子樹又組成森林，森林這種數據結構是和樹相互遞歸定義的
可以用遞歸的思想來遍歷森林
首先，訪問森林中第一棵樹的根結點B
先序遍歷第一棵樹中根結點的子樹森林，E、F兩棵樹組成的森林
重復第一步，先訪問森林中第一棵樹的根結點E
遍歷E的兩個子樹森林，即K、L兩棵樹組成的森林
遍歷完K后，再遍歷除了第一棵樹K之后的剩余的樹構成的森林，即L
效果等同于依次對各個樹進行先根遍歷
可以對各個子樹進行一個先序遍歷，然后排出一個完整的序列
另一種方法：轉換成與之對應的二叉樹：
效果等同于依次對二叉樹的先序遍歷
森林的中序遍歷
同樣可以轉換成與之對應的二叉樹：
效果等同于依次對二叉樹的中序遍歷
知識回顧與重要考點
5.4.1 樹的存儲結構
- 雙親表示法：順序存儲，保存父結點下標，易找父，難找孩
- 孩子表示法：順序存儲，保存孩子鏈表頭指針（順序+鏈式），易找孩，難找父
- 孩子兄弟表示法：二叉鏈表存儲，左孩子右兄弟，形態(tài)上和二叉樹類似
重要考點：樹、森林與二叉樹的轉換
5.4.2 樹、森林與二叉樹的轉化
文章來源：http://www.zghlxwxcb.cn/news/detail-773487.html
- 本質上就是用孩子兄弟表示法存儲樹或森林
- 存儲森林時，將每棵樹的根結點視為兄弟
- Tips：記“本質”，不記方法。方法只是表象，“本質”才是內核。
5.4.3 樹和森林的遍歷
文章來源地址http://www.zghlxwxcb.cn/news/detail-773487.html
- 對森林的遍歷可以轉換成對二叉樹的遍歷
到了這里，關于[入門必看]數據結構5.4：樹、森林的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
