如何理解Java中的樹

這篇文章主要講解了“如何理解Java中的樹”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何理解Java中的樹”吧！

1 樹的定義

樹實際上就是由許多個節點組成的集合，只不過每個節點的的組成是根據樹狀結構進行劃分。一顆普通的樹結構可以通過以下圖來定義。

還是再來羅嗦一遍，樹的結構就像是一顆倒掛的樹，結點的組成是以層級往下。一棵樹由若干子樹構成，而子樹又有更小的子樹構成。

樹的血緣關系

對于樹中的某個結點，最多只和上一層的結點有直接的關系，而與其下一層的多個結點有直接關系。其上一層的結點稱為雙親結點，下一層的結點稱為孩子結點。所有位于樹的最底部，沒有孩子結點的結點被稱之為葉子節點。具有相同雙親的結點互為兄弟節點。

樹的家族等級

樹是一個大家族，等級十分森嚴。樹中某個結點的子樹個數稱為該結點的度。所以葉子結點也就是度為0的結點。而度不為0的結點被稱之為內部結點。每一個結點都具有自己的層次，該層次由高往低遞增，根結點為第一層，根的孩子結點為第二層，依次類推。一棵樹最大的層數稱之為樹的高度(或深度)。

2 樹的存儲結構

由于普通的樹結構并不像二叉樹那么規則，可能是多叉樹的組合，因此很難用常規的線性結構來存儲。因此樹結構的存儲需要將樹家族中的關系剝離出來進行存儲，保存了每個結點之間的關系，整個樹結構也就能依次進行恢復。

這就好比家族中的族譜一樣，記錄的是我們和雙親以及兄弟姐妹的關系。對于樹而言，則根據存儲關系的不同，可分為雙親表示、孩子表示以及孩子兄弟表示三種存儲方法。

雙親表示法

樹的雙親表示，顯然就是通過記錄每個結點的雙親結點來存儲整顆樹的層次關系。這里常用的一種存儲結構就是數組。在連續的地址中存儲樹的結點，同時將之與其雙親結點在數組中的序號進行對應，這樣一來就能夠保存所有結點的雙親信息。

雙親表示法直接存儲的是結點的雙親位置(對應于數組的下標)，因此在求某個結點的雙親結點以及祖先結點時非常方便。但是卻無法直接獲得該結點的孩子結點的位置。

若需要查找指定結點的孩子以及后代結點，需要遍歷整個數組并進行多次判斷才行。

孩子表示法

樹的雙親表示法的缺點顯而易見，所以最直接的解決辦法就是干脆存孩子結點算了。還別說，孩子表示法就是這樣一種表示方法。但是相較于雙親結點的存儲，存儲孩子結點有一個需要考慮的問題，就是某個結點的雙親結點最多只有一個，但是其孩子結點可能有多個。如果每個孩子結點都存儲在數組里，這樣的方式不是一個明智的選擇，并且也沒有必要。

所以在使用孩子表示法來存儲樹的結構時，常使用數組+鏈表的結構。這種結構是不是很常見，跟解決哈希沖突的鏈地址法有異曲同工之意。在這樣的鏈式結構中，用指針指示出結點的每個孩子，每個孩子的位置通過鏈表依次相連，這樣就十分方便與查找每個結點的子孫。

只不過問題依舊，若要找出尋找某個結點的雙親則同樣需要遍歷所有鏈表。不過，既然雙親表示和孩子表示都有了，簡單粗暴的合并一下不就可以相互補充，共同進退嗎。

所謂的雙親孩子表示法，直接將雙親表示和孩子表示組合起來即可。這樣即可滿足雙親的查找，也可以滿足孩子的查找。

孩子兄弟表示法

本來有了雙親孩子表示法就已經足夠用來存儲樹中的數據信息了，為什么還要來一個孩子兄弟法呢?其實不然，孩子兄弟表示法反而是一種很有意思且很有價值的表示方式。

在孩子兄弟表示法中，我們約定只存儲每個結點的第一個孩子結點和下一個兄弟結點。不僅如此，結點的存儲是通過鏈表進行的。話說不太清，還是直接看圖吧。

看起來似乎有些詭異的形狀，每個結點都作為鏈表的一個節點，通過兩個指針分別指向第一個孩子結點和下一個兄弟結點。為了防止大家看不懂，我舉個例子。拿結點B來說，它的第一個孩子結點是E，而它的下一個兄弟是與它處于同一層級的C。因此結點B的兩個指針分別指向了E和C。

孩子兄弟表示法這樣看起來似乎很雞肋，但是假如我們調整一下右邊這個圖，就能看出其中的蹊蹺了。

看出來了嗎，孩子兄弟表示法實際上就是將一顆普通的樹轉換成了二叉樹的形式。所以說二叉樹為什么這么重要，因為萬變不離其中呀。看到這，其實也透露出樹和二叉樹之間的轉換關系，許多二叉樹上的性質和操作也可以借此運用在普通的樹結構中。

3 樹的遍歷

學過二叉樹的同學想必應該對前序遍歷、中序遍歷、后序遍歷、中序遍歷爛熟于心了吧，無論是迭代還是非迭代的寫法，都是基礎得不能再基礎的東西了。而對于普通的樹而言，由于每個結點子樹的個數并不一定，因此不好規定前、中、后序的順序。

所以一般而言對于樹的遍歷方式有兩種，根據根結點被遍歷的先后可分為先根遍歷和后根遍歷。

樹的先根遍歷是先訪問樹的根節點，然后依次遍歷根結點的各個子樹。如此遞推。當將一顆普通樹轉換為對應的二叉樹時(孩子兄弟表示法)，其實就相當于是前序遍歷。

樹的后根遍歷就不用多說了吧，跟先根遍歷相反，先訪問根結點的各顆子樹，再訪問樹根結點。而樹的后根遍歷就相當于轉換后二叉樹的中序遍歷。不信的話你試試。

4 樹、森林和二叉樹的相互轉換

寫到這，突然發現好像忘記介紹森林是什么東西了。其實森林的概念很簡單，就是很多顆樹。對，就是這樣。

樹、森林和二叉樹本質上都是類似的結構，因此相互之間可以進行轉換。任意一個森林或者一棵樹都可以對應表示為一顆二叉樹，而任何一顆二叉樹也能夠對應到一個森林或一棵樹上。

樹轉換為二叉樹，我們在前面已經介紹過，就是通過樹的孩子兄弟表示法。通過孩子兄弟法進行表示時，每一個樹都可以用一顆唯一的二叉樹來表示。但是轉換過來的二叉樹卻有一個非常顯著的特點。仔細觀察。

很顯然，這不是一顆平衡的二叉樹。并且，根節點是沒有右子樹的，我敢肯定的說。這是因為根節點是沒有兄弟結點的，它只有孩子結點，所以在轉換為二叉樹之后，一定是沒有右子樹的。

不過這樣的缺陷可以在森林中進行彌補。由于森林中有很多棵樹，因此可以將其它樹作為右子樹。具體的實現步驟，先將森林中的每一棵樹轉換為二叉樹，再將第一顆樹的根結點作為轉換后的二叉樹的根。第一棵樹的左子樹作為轉換后二叉樹根結點的左子樹，第二棵樹作為轉換后二叉樹的右子樹。第三顆樹作為轉換后二叉樹根結點的右子樹的右子樹。以此類推。

咱們來舉個例子。這里有一個由三顆樹構成的森林。

將上面三棵樹分辨轉換二叉樹是以下形式。

然后將綠色二叉樹作為藍色二叉樹根節點的右子樹，將黃色二叉樹作為綠色二叉樹根節點的右子樹，就可以得到森林轉換為二叉樹的結果。

根據以上的規則，同樣可以將一顆二叉樹轉換為樹和森林。

感謝各位的閱讀，以上就是“如何理解Java中的樹”的內容了，經過本文的學習后，相信大家對如何理解Java中的樹這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！