說(shuō)起樹，想必大多數(shù)人第一反應(yīng)都是二叉樹以及二叉樹的各種親戚，包括紅黑樹、平衡二叉樹等。但是其實(shí)除了二叉樹外，普通的樹結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)中也占據(jù)著非常重要的一部分。

[[337315]]

不僅如此，所謂百川成海，白木成林。既然有了樹結(jié)構(gòu)，自然而然也會(huì)有相應(yīng)的森林結(jié)構(gòu)。因此，本文就將從普通的樹結(jié)構(gòu)出發(fā)，探討并介紹一下樹和森林的那些事。

1 樹的定義

樹實(shí)際上就是由許多個(gè)節(jié)點(diǎn)組成的集合，只不過(guò)每個(gè)節(jié)點(diǎn)的的組成是根據(jù)樹狀結(jié)構(gòu)進(jìn)行劃分。一顆普通的樹結(jié)構(gòu)可以通過(guò)以下圖來(lái)定義。

還是再來(lái)羅嗦一遍，樹的結(jié)構(gòu)就像是一顆倒掛的樹，結(jié)點(diǎn)的組成是以層級(jí)往下。一棵樹由若干子樹構(gòu)成，而子樹又有更小的子樹構(gòu)成。

樹的血緣關(guān)系

對(duì)于樹中的某個(gè)結(jié)點(diǎn)，最多只和上一層的結(jié)點(diǎn)有直接的關(guān)系，而與其下一層的多個(gè)結(jié)點(diǎn)有直接關(guān)系。其上一層的結(jié)點(diǎn)稱為雙親結(jié)點(diǎn)，下一層的結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)。所有位于樹的最底部，沒有孩子結(jié)點(diǎn)的結(jié)點(diǎn)被稱之為葉子節(jié)點(diǎn)。具有相同雙親的結(jié)點(diǎn)互為兄弟節(jié)點(diǎn)。

樹的家族等級(jí)

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

2 樹的存儲(chǔ)結(jié)構(gòu)

由于普通的樹結(jié)構(gòu)并不像二叉樹那么規(guī)則，可能是多叉樹的組合，因此很難用常規(guī)的線性結(jié)構(gòu)來(lái)存儲(chǔ)。因此樹結(jié)構(gòu)的存儲(chǔ)需要將樹家族中的關(guān)系剝離出來(lái)進(jìn)行存儲(chǔ)，保存了每個(gè)結(jié)點(diǎn)之間的關(guān)系，整個(gè)樹結(jié)構(gòu)也就能依次進(jìn)行恢復(fù)。

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

雙親表示法

樹的雙親表示，顯然就是通過(guò)記錄每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)來(lái)存儲(chǔ)整顆樹的層次關(guān)系。這里常用的一種存儲(chǔ)結(jié)構(gòu)就是數(shù)組。在連續(xù)的地址中存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)將之與其雙親結(jié)點(diǎn)在數(shù)組中的序號(hào)進(jìn)行對(duì)應(yīng)，這樣一來(lái)就能夠保存所有結(jié)點(diǎn)的雙親信息。

雙親表示法直接存儲(chǔ)的是結(jié)點(diǎn)的雙親位置(對(duì)應(yīng)于數(shù)組的下標(biāo))，因此在求某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)以及祖先結(jié)點(diǎn)時(shí)非常方便。但是卻無(wú)法直接獲得該結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置。

若需要查找指定結(jié)點(diǎn)的孩子以及后代結(jié)點(diǎn)，需要遍歷整個(gè)數(shù)組并進(jìn)行多次判斷才行。

孩子表示法

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

所以在使用孩子表示法來(lái)存儲(chǔ)樹的結(jié)構(gòu)時(shí)，常使用數(shù)組+鏈表的結(jié)構(gòu)。這種結(jié)構(gòu)是不是很常見，跟解決哈希沖突的鏈地址法有異曲同工之意。在這樣的鏈?zhǔn)浇Y(jié)構(gòu)中，用指針指示出結(jié)點(diǎn)的每個(gè)孩子，每個(gè)孩子的位置通過(guò)鏈表依次相連，這樣就十分方便與查找每個(gè)結(jié)點(diǎn)的子孫。

只不過(guò)問(wèn)題依舊，若要找出尋找某個(gè)結(jié)點(diǎn)的雙親則同樣需要遍歷所有鏈表。不過(guò)，既然雙親表示和孩子表示都有了，簡(jiǎn)單粗暴的合并一下不就可以相互補(bǔ)充，共同進(jìn)退嗎。

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

孩子兄弟表示法

本來(lái)有了雙親孩子表示法就已經(jīng)足夠用來(lái)存儲(chǔ)樹中的數(shù)據(jù)信息了，為什么還要來(lái)一個(gè)孩子兄弟法呢?其實(shí)不然，孩子兄弟表示法反而是一種很有意思且很有價(jià)值的表示方式。

在孩子兄弟表示法中，我們約定只存儲(chǔ)每個(gè)結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。不僅如此，結(jié)點(diǎn)的存儲(chǔ)是通過(guò)鏈表進(jìn)行的。話說(shuō)不太清，還是直接看圖吧。

看起來(lái)似乎有些詭異的形狀，每個(gè)結(jié)點(diǎn)都作為鏈表的一個(gè)節(jié)點(diǎn)，通過(guò)兩個(gè)指針?lè)謩e指向第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。為了防止大家看不懂，我舉個(gè)例子。拿結(jié)點(diǎn)B來(lái)說(shuō)，它的第一個(gè)孩子結(jié)點(diǎn)是E，而它的下一個(gè)兄弟是與它處于同一層級(jí)的C。因此結(jié)點(diǎn)B的兩個(gè)指針?lè)謩e指向了E和C。

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

看出來(lái)了嗎，孩子兄弟表示法實(shí)際上就是將一顆普通的樹轉(zhuǎn)換成了二叉樹的形式。所以說(shuō)二叉樹為什么這么重要，因?yàn)槿f(wàn)變不離其中呀。看到這，其實(shí)也透露出樹和二叉樹之間的轉(zhuǎn)換關(guān)系，許多二叉樹上的性質(zhì)和操作也可以借此運(yùn)用在普通的樹結(jié)構(gòu)中。

3 樹的遍歷

學(xué)過(guò)二叉樹的同學(xué)想必應(yīng)該對(duì)前序遍歷、中序遍歷、后序遍歷、中序遍歷爛熟于心了吧，無(wú)論是迭代還是非迭代的寫法，都是基礎(chǔ)得不能再基礎(chǔ)的東西了。而對(duì)于普通的樹而言，由于每個(gè)結(jié)點(diǎn)子樹的個(gè)數(shù)并不一定，因此不好規(guī)定前、中、后序的順序。

所以一般而言對(duì)于樹的遍歷方式有兩種，根據(jù)根結(jié)點(diǎn)被遍歷的先后可分為先根遍歷和后根遍歷。

樹的先根遍歷是先訪問(wèn)樹的根節(jié)點(diǎn)，然后依次遍歷根結(jié)點(diǎn)的各個(gè)子樹。如此遞推。當(dāng)將一顆普通樹轉(zhuǎn)換為對(duì)應(yīng)的二叉樹時(shí)(孩子兄弟表示法)，其實(shí)就相當(dāng)于是前序遍歷。

樹的后根遍歷就不用多說(shuō)了吧，跟先根遍歷相反，先訪問(wèn)根結(jié)點(diǎn)的各顆子樹，再訪問(wèn)樹根結(jié)點(diǎn)。而樹的后根遍歷就相當(dāng)于轉(zhuǎn)換后二叉樹的中序遍歷。不信的話你試試。

4 樹、森林和二叉樹的相互轉(zhuǎn)換

寫到這，突然發(fā)現(xiàn)好像忘記介紹森林是什么東西了。其實(shí)森林的概念很簡(jiǎn)單，就是很多顆樹。對(duì)，就是這樣。

樹、森林和二叉樹本質(zhì)上都是類似的結(jié)構(gòu)，因此相互之間可以進(jìn)行轉(zhuǎn)換。任意一個(gè)森林或者一棵樹都可以對(duì)應(yīng)表示為一顆二叉樹，而任何一顆二叉樹也能夠?qū)?yīng)到一個(gè)森林或一棵樹上。

樹轉(zhuǎn)換為二叉樹，我們?cè)谇懊嬉呀?jīng)介紹過(guò)，就是通過(guò)樹的孩子兄弟表示法。通過(guò)孩子兄弟法進(jìn)行表示時(shí)，每一個(gè)樹都可以用一顆唯一的二叉樹來(lái)表示。但是轉(zhuǎn)換過(guò)來(lái)的二叉樹卻有一個(gè)非常顯著的特點(diǎn)。仔細(xì)觀察。

很顯然，這不是一顆平衡的二叉樹。并且，根節(jié)點(diǎn)是沒有右子樹的，我敢肯定的說(shuō)。這是因?yàn)楦?jié)點(diǎn)是沒有兄弟結(jié)點(diǎn)的，它只有孩子結(jié)點(diǎn)，所以在轉(zhuǎn)換為二叉樹之后，一定是沒有右子樹的。

不過(guò)這樣的缺陷可以在森林中進(jìn)行彌補(bǔ)。由于森林中有很多棵樹，因此可以將其它樹作為右子樹。具體的實(shí)現(xiàn)步驟，先將森林中的每一棵樹轉(zhuǎn)換為二叉樹，再將第一顆樹的根結(jié)點(diǎn)作為轉(zhuǎn)換后的二叉樹的根。第一棵樹的左子樹作為轉(zhuǎn)換后二叉樹根結(jié)點(diǎn)的左子樹，第二棵樹作為轉(zhuǎn)換后二叉樹的右子樹。第三顆樹作為轉(zhuǎn)換后二叉樹根結(jié)點(diǎn)的右子樹的右子樹。以此類推。

咱們來(lái)舉個(gè)例子。這里有一個(gè)由三顆樹構(gòu)成的森林。

將上面三棵樹分辨轉(zhuǎn)換二叉樹是以下形式。

然后將綠色二叉樹作為藍(lán)色二叉樹根節(jié)點(diǎn)的右子樹，將黃色二叉樹作為綠色二叉樹根節(jié)點(diǎn)的右子樹，就可以得到森林轉(zhuǎn)換為二叉樹的結(jié)果。

根據(jù)以上的規(guī)則，同樣可以將一顆二叉樹轉(zhuǎn)換為樹和森林。

5 總結(jié)

在數(shù)據(jù)結(jié)構(gòu)中，估計(jì)樹和森林不算很熱門的結(jié)構(gòu)，甚至許多工作過(guò)很多年的老碼農(nóng)都不曾用過(guò)。寫這篇文章的時(shí)候，我也在想樹和森林到底在實(shí)際中有什么用，似乎最重要的部分就是將一顆普通的樹轉(zhuǎn)換成二叉樹來(lái)處理。但是我想這就是它的價(jià)值所在吧。

許多真實(shí)場(chǎng)景中，可能數(shù)據(jù)之間的關(guān)系并不能直接通過(guò)二叉樹來(lái)表示和存儲(chǔ)，一開始可能都需要通過(guò)多叉樹或者各種畸形的樹結(jié)構(gòu)來(lái)定義關(guān)系。這樣的樹肯定是不適用于快速的處理和訪問(wèn)的，因此往往需要將這些奇形怪狀的樹轉(zhuǎn)換為規(guī)則的二叉樹來(lái)進(jìn)行進(jìn)一步的處理。最終為了回歸到具體的應(yīng)用，也需要將二叉樹重新分解為最初的樹或者森林結(jié)構(gòu)來(lái)獲得應(yīng)用意義。

總的來(lái)說(shuō)，存在即是真理。不怕用不到，就怕想不到。

本文轉(zhuǎn)載自微信公眾號(hào)「業(yè)余碼農(nóng)」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系業(yè)余碼農(nóng)公眾號(hào)。