第六章?樹和二叉樹

6.1 樹的定義和基本術語

樹 Tree 是n個結點的有限集。

任意一棵非空樹中：

（1）有且僅有一個特定的稱為根（root）的結點；

（2）當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1，T2，...，Tm，其中，每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。

?

結點：包含一個數據元素及若干指向其子樹的分支。

結點的度（degree）：結點擁有的子樹數。

葉子（Leaf）/終端結點：度為0的結點。

分支結點/非終端結點：度不為0的結點。 除根結點外，分支結點也稱為內部結點。

孩子（Child）：結點的子樹的根稱為該結點的孩子。

雙親（Parent）：該結點稱為孩子的雙親。

兄弟（Sibling）：同一個雙親的孩子之間互稱兄弟。

祖先：從根到該結點所經的所有結點。

子孫：以某結點為根的子樹中的任一結點。

層次（Level）:根為第一層，根的孩子為第二層。

若某結點在第l層，則其子樹的根在第l+1層。

其雙親在同一層的結點互為堂兄弟。

深度（Depth）/高度：樹中結點的最大層次。

?

有序樹：樹中結點的各子樹從左至右是有次序的。

無序樹：樹中結點的各子樹從左至右是無次序的。

森林（Forest）：m棵互不相交的樹的集合。

對樹中每個結點而言，其子樹的集合即為森林。

?

6.2 二叉樹

二叉樹 Binary Tree

每個結點至多只有兩棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。

?

二叉樹的5種基本形態：

空二叉樹

僅有根節點

右子樹為空

左子樹為空

左右子樹均非空

?

二叉樹的性質：

1、在二叉樹第i層上至多有2^(i-1)個結點。

2、深度為k的二叉樹至多有2^k-1個結點。

3、對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。

結點：n=n0+n1+n2

入度：n=n1+2n2+1

?

?

滿二叉樹：一棵深度為k且有2^k-1個結點的二叉樹稱為滿二叉樹。

特點：每一層上的結點數都是最大結點數。

可以對滿二叉樹的結點進行連續編號，約定編號從根結點起，自上而下，自左至右。

?

由此可引出完全二叉樹的定義：

深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中的編號從1至n的結點一一對應時，稱之為完全二叉樹。

特點：

（1）葉子結點只可能在層次最大的兩層上出現；

（2）對任一結點，若其右分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1。

?

完全二叉樹的兩個重要性質：

1、具有n個結點的完全二叉樹的深度為；

2、對于完全二叉樹的編號：

（1）如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親結點是i/2；

（2）如果2i>n，則i結點無左孩子；否則，其左孩子為2i；

（3）如果2i+1>n，則i結點無右孩子；否則，其右孩子為2i+1。

?

?

二叉樹的存儲結構：

（1）順序存儲結構：完全二叉樹。

（2）鏈式存儲結構：

二叉鏈表：左孩子、右孩子

三叉鏈表：左孩子、右孩子、父結點

?

二叉鏈表存儲結構的許多基本操作都采用了遞歸函數，因為二叉樹的層數是不定的，正確采用遞歸函數可簡化編程。
遞歸函數特點：1、降階；2、出口。

?

?

在含有n個結點的二叉鏈表中有n+1個空鏈域。

可以利用這些空鏈域存儲其他有用信息，從而得到另一種鏈式存儲結構——線索鏈表。

?

6.3 遍歷二叉樹和線索二叉樹

6.3.1 遍歷二叉樹

將非線性的二叉樹結構線性化。

Traversing binary tree

二叉樹是由三個基本單元組成：根節點、左子樹、右子樹。

限定先左后右，有三種遍歷方式：先序遍歷、中序遍歷、后續遍歷。

對二叉樹做中序遍歷和先序遍歷（或者中序遍歷和后續遍歷），就可以確定二叉樹的形狀。

?

先序遍歷二叉樹：

若二叉樹為空，則空操作；否則

1、訪問根節點；

2、先序遍歷左子樹；

3、先序遍歷右子樹。

?

中序遍歷二叉樹：

若二叉樹為空，則空操作；否則

1、中序遍歷左子樹；

2、訪問根節點；

3、中序遍歷右子樹。

?

后序遍歷二叉樹：

若二叉樹為空，則空操作；否則

1、后序遍歷左子樹；

2、后序遍歷右子樹；

3、訪問根節點。

?

非遞歸中序遍歷二叉樹

?

?

?

二叉樹表達式：

前綴表達式-波蘭式

中綴表達式

后綴表達式-逆波蘭式

?

還可以從上到下，從左到右按層次進行遍歷。即層序遍歷。

時間復雜度O(n)

空間復雜度O(n)

?

鏈式結構先序構造二叉樹時，要把度數為1的結點和葉子結點的無用指針置空。

?

?

6.3.2 線索二叉樹

遍歷二叉樹是以一定規則將二叉樹中結點排列成一個線性序列，得到二叉樹中結點的先序序列或中序序列或后序序列。即對一個非線性結構進行線性化操作。

在有n個結點的二叉鏈表中必定存在n+1個空鏈域。

利用這些空鏈域來存儲結點的前驅和后繼信息。

規定如下：

若結點有左子樹，則lchild指向其左孩子，否則，指向其前驅；

若結點有右子樹，則rchild指向其右孩子，否則，指向其后繼。

?

增加兩個標志域：LTag ?RTag ??0(Link)指向左右孩子，1(Tread)指向前驅后繼。

指向前驅和后繼的指針，叫做線索。

線索二叉樹（Threaded Binary Tree）

?

對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。

在線索樹上進行遍歷，只要先找到序列中的第一個結點，然后依次找結點后繼直至其后繼為空時為止。

?

中序線索樹：

后繼：

若其右標志為1，右鏈直接指示后繼；

非終端的后繼：遍歷右子樹時，第一個訪問的結點為后繼，即右子樹中最左下的結點。

前驅：

若其左標志為1，左鏈直接指示前驅；

非終端的前驅：遍歷左子樹時，最后一個訪問的結點為前驅，即左子樹中最右下的結點。

?

后序線索樹：

后繼：

若為根節點，后繼為空；

若結點為雙親右孩子，或為左孩子且雙親無右孩子，則其后繼為雙親；

若結點為左孩子且雙親有右孩子，則后繼為雙親右子樹上按后序遍歷列出的第一個結點。

在后序線索化樹上找后繼時需知道結點雙親，即需帶標志域的三叉鏈表作為存儲結構。

?

?

中序線索二叉樹的遍歷，雖然時間復雜度為O(n)，但常數因子要小于普通二叉樹。

若某程序對二叉樹需經常遍歷，或查找結點的前驅或后繼，應采用線索鏈表作存儲結構。

?

可以在二叉樹的線索表上添加一個頭結點，令其lchild指向二叉樹根結點，rchild指向中序遍歷時訪問的最后一個結點；令二叉樹中序序列中的第一個結點的lchild域指針和組后一個結點rchild域指針指向頭結點。

?

線索化的實質是將二叉樹鏈表中的空指針改為指向前驅或后繼的線索。

線索化的過程即為在遍歷的過程中修改空指針的過程。

附設一個指針pre始終指向前一個訪問的結點，指針p指向當前訪問結點。

指針pre指向的是p的前驅，指針p指向的是pre的后繼。

?

6.4 樹和森林

6.4.1 樹的存儲結構

1、雙親表示法

以一組連續空間存儲樹的結點，同時在每個結點中附設一個指示器指示其雙親結點的位置。

這種表示法利用了每個結點（根結點除外）只有唯一雙親的性質。

求孩子結點時需要遍歷整個結構。

?

2、孩子表示法

把每個結點的孩子結點排列起來，看成是一個線性表，以單鏈表作為存儲結構，則n個結點有n個孩子鏈表（葉子的孩子鏈表為空表）。

而n個頭指針又組成一個線性表，為了便于查找，可采用順序存儲結構。

孩子表示法便于那些涉及孩子的操作。

?

可以把雙親表示法和孩子表示法結合起來，即將雙親表示和孩子鏈表合在一起。

?

3、?孩子兄弟表示法

二叉鏈表作為樹的存儲結構。

結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點。

分別命名為firstchild域和nextsibling域。

任何一棵和樹對應的二叉樹，其右子樹必空。

?

6.4.2 森林與二叉樹的轉換

把森林中第二棵樹的根結點看成是第一棵樹的根結點兄弟，可以導出森林和二叉樹的對應關系。

?

6.4.3 樹和森林的遍歷

兩種方式：

先根遍歷，對應二叉樹的先序遍歷；

后根遍歷，對應二叉樹的后序遍歷。

?

6.6 哈夫曼樹及其應用

6.6.1 最優二叉樹（哈夫曼樹）

路徑：從一個結點到另一個結點之間的分支構成兩個結點間的路徑。

路徑長：路徑上的分支數目。

樹的路徑長度：從樹根到每一個葉子結點的路徑長度之和。

帶權路徑長度：路徑長度與結點權值的乘積。

樹的帶權路徑長度：所有葉子結點的帶權路徑長度之和。

假設有n個權值，對應n個葉子結點，帶權路徑長度WPL最小的二叉樹稱為最優二叉樹或哈夫曼樹。

?

最優二叉樹特點：

權值越小的結點，其到根結點的路徑越長。

最優二叉樹的左右子樹是可以互換的，不影響樹的帶權路徑長度。

?

哈夫曼算法：

（1）根據給定的n個權值{W1, W2, ..., Wn}構成n棵二叉樹的集合F={T1, T2, ..., Tn}，其中每棵二叉樹Ti中只用一個帶權為Wi的根結點，其左右子樹均空；

（2）在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且新的二叉樹的根結點的權值為左右子樹根結點權值之和；

（3）在F中刪除這兩棵樹，并將新的樹加入F中；

（4）重復（2）（3），直至只含一棵樹為止。

?

6.6.2 哈夫曼編碼

若想設計長短不等的編碼，必須是任一個字符的編碼都不是另一個字符的編碼的前綴，這種編碼稱作前綴編碼。

?

可以利用二叉樹來設計二進制的前綴編碼。

約定左分支為0，右分支為1。

從根結點到葉子結點的路徑上的分支01串，即為該葉子結點的前綴編碼。

?

設計電文總長最短的二進制前綴編碼即為

以n種字符出現的頻率作權，設計一棵哈夫曼樹，由此得到的二進制前綴碼便稱為哈夫曼編碼。

哈夫曼樹中沒有度為1的結點。（這類樹又稱為嚴格/正則二叉樹）

則一棵有n個葉子結點的哈夫曼樹共有2n-1個結點，可以存儲在一個大小為2n-1的一維數組中。

?

?

?

6.7 回溯法與樹的遍歷

試探與回溯：在約束條件下，先序遍歷一顆狀態樹。

在程序設計問題中，有相當一類求一組解、或求全部解、或求最優解的問題，這類問題不是根據某種確定的計算法則，而是利用試探和回溯（Backtracking）的搜索技術求解。

回溯法是設計遞歸過程的一種重要方法，它的求解過程實質上是一個先序遍歷一棵“狀態樹”的過程，這棵樹不是遍歷前預先建立的，而是隱含在遍歷過程中，認識到這一點，許多問題就迎刃而解了。

?

很多問題用回溯和試探求解時，描述求解過程的狀態樹不是一棵滿的多叉樹。

當試探過程中出現的狀態和問題所求解產生矛盾時，不再繼續試探下去，這時出現的葉子結點不是問題的解的終結狀態。

這類問題的求解過程可看成是在約束條件下進行先序遍歷，并在遍歷過程中剪去那些不滿足條件的分支。

?

八皇后問題：

任何兩個棋子不在同一行、同一列、同一斜線。

求所有合法布局的過程即為在上述約束條件下先根遍歷狀態樹的過程。

?

?