目錄

一、樹
二、二叉樹
三、樹、森林與二叉樹的轉(zhuǎn)換

一、樹

樹形結(jié)構(gòu) 是數(shù)據(jù)元素(結(jié)點)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，可用于表示數(shù)據(jù)元素之間存在的一對多關(guān)系。
樹(Tree) 是由n(n≥0)個結(jié)點構(gòu)成的有限集合，當(dāng)n=0時稱為空樹。若樹非空，則具有以下兩個性質(zhì)：
(1)有且僅有一個特定的結(jié)點，稱為根(Root)。
(2)其余的結(jié)點可分為m個互不相交的集合T1，T2，…，Tm，其中每一個集合都是一棵樹，并且稱為根的子樹( Subtree)。
如下圖所示是有13個結(jié)點的樹，A是根，其余結(jié)點分成三個互斥的集合T1={B，E，F(xiàn)，K，L}、T2={C，G}、T3={D，H，I，J，M}，T1、T2、T3都是A的子樹，其本身也是一棵樹。

image

樹的基本術(shù)語：

**樹結(jié)點( Tree Node)** ：樹中一個獨立單元。包含一個數(shù)據(jù)元素及若干指向其子樹的分支，如上圖中的A、B、C、D等。
**樹根(Root)** ：樹中唯一沒有前驅(qū)的結(jié)點，如上圖中的A結(jié)點。
**結(jié)點的度( Node Degree)** ：結(jié)點擁有的子樹數(shù)，稱為結(jié)點的度。例如，在上圖中A的度為3，B的度為2，K的度為0。
**樹的度( Tree Degree)** ：樹中各結(jié)點的度的最大值。如上圖中樹的度為3。
**樹葉(Leaf)** ：度為0的結(jié)點。例如，在圖中，K、L、F、G、1、J、M都是樹葉，也稱葉結(jié)點。除根和葉子以外的其他結(jié)點稱為中間結(jié)點。
**雙親( Parent)和孩子( Child)** ：把一個樹結(jié)點的直接前驅(qū)稱為該結(jié)點的雙親；反之；把一個樹結(jié)點的所有直接后繼稱為該結(jié)點的孩子。例如，上圖中，結(jié)點B是結(jié)點A的孩子，結(jié)點A是結(jié)點B的雙親。
**兄弟( Sibling)** ：同一雙親的孩子之間互稱為兄弟。例如，上圖中，結(jié)點K、L互為兄弟，結(jié)點H、I、J互為兄弟。將這些關(guān)系進一步推廣，結(jié)點的祖先就是從根到該結(jié)點的所經(jīng)分支上的所有結(jié)點。以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。此外雙親在同一層上的結(jié)點互為堂兄弟.
**樹的層次( Level)和深度( Depth)** ：從根算起，根為第一層，根的孩子為第二層，樹中任一結(jié)點的層次等于它的雙親的層次加1。樹中各結(jié)點層次的最大值稱為樹的深度或高度。例如，上圖中的樹的深度為4。
**有序樹和無序樹( Ordered Tree8。 Unordered Tree)** ：如果樹中結(jié)點的各子樹可看成從左至右是有次序的(即不能互換)，則稱該樹為有序樹，否則稱為無序樹。在有序樹最左邊子樹的根稱為第一孩子，最右邊子樹的根稱為最后一個孩子。
**森林( Forest)** ：m(m≥0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。由此也可以以森林和樹的相互遞歸定義來描述樹。

1.1、樹的存儲結(jié)構(gòu)

樹是一種非線性結(jié)構(gòu)。為了存儲一探樹，必須把樹中各結(jié)點之間一對多的關(guān)系反映在存儲結(jié)構(gòu)中。由于在一個m階的普通樹中，每一個結(jié)點的孩子可是0~m個，所以相對于二又樹而言，樹的存錯結(jié)構(gòu)要復(fù)雜，一般有如下幾種存儲結(jié)構(gòu)：

• 1.1.1、雙親表示法

雙親表示法是以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個標(biāo)志指示其雙親結(jié)點在表中的位置，該存儲結(jié)構(gòu)定義如下；

image

• 1.1.2、孩子表示法

由于樹中的每個結(jié)點可能有多棵子樹，因此可以采用多重鏈表來表示，即每個結(jié)點有多個指針域，分別指向其孩子結(jié)點。
如圖6-13所示，樹的孩子表示法需要按照樹的度m為每個結(jié)點分配指針域，而每個結(jié)點的孩子個數(shù)可不同，當(dāng)m很大時，指針域的存儲單元利用率很低。如果按每個結(jié)點的實際孩子數(shù)來分配指針單元，結(jié)點的大小可變，會給存儲管理帶來不便。一個較好的解決辦法就是為每個結(jié)點建立一個孩子鏈表，n個結(jié)點的樹由n個這樣的單鏈表組成，每個鏈表的表頭結(jié)點存放該結(jié)點的值和指向其孩子的頭指針，如圖614所示

image

• 1.1.3、孩子兄弟表示法

孩子兄弟表示法又稱樹的二又鏈表表示法。樹中的每個結(jié)點由三個域組成：data域 結(jié)點的數(shù)據(jù)信息， firstchild域為指向結(jié)點的第一個孩子的指針， nextbrother域為指向下一個兄弟的指針，如下圖所示。
由下圖可以看出，每個結(jié)點的左指針指向孩子結(jié)點，而右指針指向兄弟結(jié)點，并且根結(jié)點的右指針為空。樹的孩子兄弟表示法為實現(xiàn)樹、森林與二又樹之間的轉(zhuǎn)換提供了基礎(chǔ)。

image

二、二叉樹

二叉樹 就是度為2的有序樹，是最重要的一種樹形結(jié)構(gòu)。二又樹的存儲和處理比普通樹簡單，同時普通樹都可以方便地轉(zhuǎn)化為二又樹來存儲和處理。
二叉樹( Binary Tree) 是一種特殊的樹形結(jié)構(gòu)。定義如下:
(1)由n(n≥0)個結(jié)點所構(gòu)成的集合，此集合可以為空。
(2)二叉樹的根結(jié)點下可分為兩個互不相交的子樹，子樹有左右之分，次序不能任意顛倒，稱為左子樹和右子樹：且左右子樹均為二叉樹。

image

2.1、二叉樹的性質(zhì)

二叉樹是有序樹的特例，具有下列重要性質(zhì)：
性質(zhì)1、在二叉樹的第i層上至多有2^(i-1)個結(jié)點(i>=1)。
性質(zhì)2、深度為k的二叉樹至多有2^(k) - 1個結(jié)點，(k>=1)。
性質(zhì)3、對任何一顆二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0 = n2 + 1；
性質(zhì)4、具有n個結(jié)點的完全二叉樹的深度為 (logn以2為底的對數(shù) + 1) 。
性質(zhì)5、如果對一棵有n結(jié)點的深度為(logn以2為底的對數(shù) + 1) ，完全二叉樹的結(jié)點按層序編號，同層按從左至右，則對任一結(jié)點i(1 ≤ i ≤ n)。于是有:
(1)如果=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1，則其雙親 PARENT(i)是結(jié)點i/2。
(2)如果2i>n，則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點)；否則，其左孩子 LCHILD(i)是結(jié)點2i。
(3)如果2i+1>n，則結(jié)點i無右孩子；否則，其右孩子 RCHILD(i)是結(jié)點2i+1。

image

一棵深度為k且有2^k - 1個結(jié)點的二叉樹稱為 滿二叉樹 。滿二叉樹的特點是每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。
對滿二叉樹的結(jié)點進行連續(xù)編號，約定編號從根結(jié)點起，自上而下，自左至右。由此可引出完全二叉樹的定義。深度為k、有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1~n的結(jié)點一一對應(yīng)時，稱為 完全二叉樹 。如上圖所示完全二叉樹具有的特點是：
(1)葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。
(2)對任一結(jié)點，若其右分支下的子孫的最大層次為r，則其左分支下的子孫的最大層次必為r或r+1。

2.2、二叉樹的存儲結(jié)構(gòu)

• 2.2.1、順序存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元存儲二叉樹中的各個結(jié)點。為了便于對二叉樹結(jié)點進行查找或處理，存儲時需要將普通二叉樹的各個結(jié)點按照它們在完全二叉樹的對應(yīng)結(jié)點位置依次存放到數(shù)組相應(yīng)的存儲單元中。如圖所示，二又樹的順序存儲結(jié)構(gòu)定義如下：

image

一般來說，順序存儲結(jié)構(gòu)只適用于完全二叉樹或滿二叉樹的存儲，因為普通二叉樹采用順序存儲結(jié)構(gòu)進行存儲時，將導(dǎo)致存儲單元的浪費。最壞情況下，對于一個深度為k且只有k個結(jié)點的右支樹來說，存儲時需要2^k-1個存儲單元。

• 2.2.2、鏈?zhǔn)酱鎯Y(jié)構(gòu)

采用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲二叉樹時，可以根據(jù)樹中的結(jié)點數(shù)動態(tài)申請所需要的結(jié)點，從而避免存儲空間的浪費。
由二叉樹的定義可知，每個二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左、右子樹的兩個分支組成。因此，定義二叉樹的結(jié)點結(jié)構(gòu)時至少應(yīng)包含三個域：數(shù)據(jù)域和左、右指針域。其中，數(shù)據(jù)域保存結(jié)點的信息左指針域存放指向其左子樹根的信息右指針域存放指向其右子樹根的信息，如下圖所示。有時，為了便于找到結(jié)點的雙親，則可在上述結(jié)點結(jié)構(gòu)中增加一個指向其雙親結(jié)點的指針域，如下圖所示。利用這兩種結(jié)點結(jié)構(gòu)所得的二叉樹的存儲結(jié)構(gòu)分別稱為二又鏈表和三又鏈表。如下圖所示二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

image

image

2.3、遍歷二叉樹

二叉樹的遍歷 是指按照一定次序訪問樹中所有結(jié)點，并且每個結(jié)點僅被訪問一次的過程。它是二叉樹最基本的運算，也是二叉樹中所有其他運算的基礎(chǔ)。遍歷二叉樹的實質(zhì)是對二叉樹的線性化過程，即遍歷的結(jié)果是將非線性結(jié)構(gòu)的樹中結(jié)點排成一個線性序列，二叉樹的遍歷按訪問根結(jié)點的先后次序不同，可分為 先序遍歷、中序遍歷 和 后序遍歷 。
下面對二叉樹的遍歷討論中，二叉樹都采用二叉鏈表的存儲結(jié)構(gòu)。

• 1、二叉樹的先序遍歷

根據(jù)二叉樹的遞歸特性，先序遍歷二叉樹的遞歸
過程如下：
(1)訪問根結(jié)點。
(2)先序遍歷左子樹
(3)先序遍歷右子樹。

• 2、二叉樹的中序遍歷

中序遍歷二叉樹的遞歸過程如下：
(1)中序遍歷左子樹。
(2)訪問根結(jié)點。
(3)中序遍歷右子樹。

• 3、二叉樹的后序遍歷

后序遍歷二叉樹的遞歸過程如下:
(1)后序遍歷左子樹。
(2)后序遍歷右子樹。
(3)訪問根結(jié)點。

image

遍歷二又樹的算法中的基本操作是訪問結(jié)點，則無論按哪種次序進行遍歷，對含有n個結(jié)點的二又樹，其時間復(fù)雜度均為0(n)。所需輔助空間為遍歷過程中棧的最大容量，即樹的深度，最壞情況下為n,則空間復(fù)雜度也為O(n)。

三、樹、森林與二叉樹的轉(zhuǎn)換

二叉樹的二叉鏈表表示法和樹的孩子兄弟表示法都是以二叉鏈表作為存儲結(jié)構(gòu)，結(jié)點的定義相同，只是解釋不同。因此，可以找到樹和二又樹之間的對應(yīng)關(guān)系，即給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。

image

森林是樹的有限集合，可以將森林看成一棵樹，其中所有樹的根結(jié)點彼此看成兄弟結(jié)點。這樣也可以導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系。

image

下面給出森林和二叉樹相互轉(zhuǎn)換的遞歸定義：
1、森林轉(zhuǎn)換成二叉樹
若F={T1，T2，…，Tm}是森林(m≥0)，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B=(root,LB,RB)。
(1)若m=0，則B為空樹。
(2)若m>0，則B的根root即為森林F中第一棵樹的根ROOT(T1)；B的左子樹LB是從森林的第一棵樹T1中根結(jié)點的子樹森林F1={T1，T2，…，Tm}轉(zhuǎn)換而成的二叉樹；B的右子樹RB是從森林F中除T1外的剩余部分F={T2，T3，…，Tm}轉(zhuǎn)換而成的二叉樹。
具體操作步驟如下：
(1)先將森林中的每一棵樹轉(zhuǎn)換為二叉樹。
(2)按森林中樹的次序，依次將后一棵樹作為前一棵樹的右子樹，并將第一棵樹的根作為目標(biāo)二又樹的根。
2、二叉樹轉(zhuǎn)換成森林
如果B=(roo，LB，RB)是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F={T，，…，Tm}。
(1)若B為空，則F為空。
(2)若B非空，則F中第一棵樹T1的根ROOT(T1)即為二叉樹B的根root；T1中根結(jié)點的子樹森林F1是由B的左子樹LB轉(zhuǎn)換而成的森林；F中除T1之外其余樹組成的森林F'={T2，T3，…，Tm}是由B的右子樹RB轉(zhuǎn)換而成的森林。
具體操作步驟如下：
(1)若二叉樹非空，則二叉樹根及其左子樹為第一棵樹的二叉樹形式。
(2)二又樹根的右子樹又可看作是剩余二叉樹構(gòu)成的森林，再繼續(xù)分離出一棵樹，直至產(chǎn)生一顆沒有右子樹的二叉樹為止。

注：文中的圖片均轉(zhuǎn)摘自網(wǎng)絡(luò)