第6章樹和二叉樹講述

1、第6章 樹和二叉樹 樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。其中以樹和二叉樹最為常用，直觀看來，樹是以分支關(guān)系定義的層次結(jié)構(gòu)。 6.1 樹的定義和基本術(shù)語 樹樹(Tree)是n(n0)個結(jié)點的有限集。在任意一棵非空樹中： (1)有且僅有一個特定的稱為根根(Root)的結(jié)點； (2)當(dāng)n1時，其余結(jié)點可分為m(m0)個互不相交的有限集T1，T2，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹子樹(SubTree)。 例如， (a)是只有一個根結(jié)點的樹；(b)是有13個結(jié)點的樹，其中A是根，其余結(jié)點分成三個互不相交的子集：T1= B，E，F(xiàn)，K，L，T2=C，G，T3=D，H，I，J，M；T1、

2、T2和T3都是根A的子樹，且本身也是一棵樹。 (a)只有根結(jié)點的樹 (b)一般的樹 樹的結(jié)構(gòu)定義是一個遞歸的定義，即在樹的定義中又用到樹的概念，它道出了樹的固有特性?；拘g(shù)語 樹的結(jié)點結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。 度為0的結(jié)點稱為葉子葉子(1eaf)或終端結(jié)點終端結(jié)點。 度不為0的結(jié)點稱為非終端結(jié)點非終端結(jié)點或分支結(jié)分支結(jié)點點。除根結(jié)點之外，分支結(jié)點也稱為內(nèi)部結(jié)點。 樹的度樹的度是樹內(nèi)各結(jié)點的度的最大值。 結(jié)點的子樹的根稱為該結(jié)點的孩子孩子(child)，相應(yīng)地，該結(jié)點稱為孩子的雙親雙親(Parent)。 同一個雙親的孩子之間互稱兄弟兄弟(sibling) 結(jié)點的祖先祖先是從根

3、到該結(jié)點所經(jīng)分支上的所有結(jié)點。 結(jié)點的層次層次(level)從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點在第i層，則其子樹的根就在第i+1層。其雙親在同一層的結(jié)點互為堂兄弟堂兄弟。 樹中結(jié)點的最大層次稱為樹的深度深度(Depth)或高度高度。 如果將樹中結(jié)點的各子樹看成從左至右是有次序的(即不能互換)，則稱該樹為有序樹有序樹，否則稱為無序樹無序樹。在有序樹中最左邊的子樹的根稱為第一個孩子，最右邊的稱為最后一個孩子。 森林森林(Forest)是m(m0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。由此，也可以森林和樹相互遞歸的定義來描述樹。 就邏輯結(jié)構(gòu)而言，任何一棵

4、樹是一個二元組Tree= (root，F(xiàn))，其中：root是數(shù)據(jù)元素，稱做樹的根結(jié)點；F是m(m0)棵樹的森林；F=(T1，T2，Tn)，其中Ti=(ri，F(xiàn)i)稱做根root的第i棵子樹；當(dāng)m!=0時，在樹根和其子樹森林之間存在下列關(guān)系： RF=| i=1 , 2 , , m , m 0 1層2層4層3層height= 4ACGBDE FK LHMIJ層次層次 根為第根為第1層層 最大層數(shù)為樹的深度（高度）最大層數(shù)為樹的深度（高度） 雙親雙親 (直接前驅(qū)）直接前驅(qū)） 孩子孩子（直接后繼）（直接后繼） 兄弟兄弟 堂兄弟堂兄弟 子孫子孫 祖先祖先d=3d=0d=2K LFGMI JABCDEH抽

5、象數(shù)據(jù)類型樹的定義。 ADT Tree 數(shù)據(jù)對象數(shù)據(jù)對象D： D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 若D為空集，則稱為空樹；若D僅含一個數(shù)據(jù)元素，則R為空集，否則R=H， H是如下二元關(guān)系： (1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)； (2)若D-root!=，則存在D-root)的一個劃分D1，D2，Dm (m0)，對任意j!=k(1j，km)有DjDk=，且對任意的i(1im)，唯一存在數(shù)據(jù)元素xiDi，有H； (3)對應(yīng)于D-root的劃分，H-，有唯一的一個劃分H1，H2，Hm(m0)，對任意j!=k(1j，km)有HjHk=，對任意i(1

6、im)，Hi是Di上的二元關(guān)系，（Di ,Hi)是一棵符合本定義的子樹，稱為根root的子樹。 基本操作基本操作： InitTree(T)； 操作結(jié)果：構(gòu)造空樹T。 DestroyTree(&T)； 初始條件：樹T存在。 操作結(jié)果：銷毀樹T。CreateTree(&T，definition)； 初始條件：definition給出樹T的定義。 操作結(jié)果：按definition構(gòu)造樹T。 ClearTree(T)； 初始條件：樹T存在。 操作結(jié)果：將樹T清為空樹。 TreeEmpty(T)； 初始條件：樹T存在。 操作結(jié)果：若T為空樹，則返回TRUE，否則FALSE； TreeDe

7、pth(T)； 初始條件：樹T存在。 操作結(jié)果：返回T的深度。 Root(T)； 初始條件：樹T存在。 操作結(jié)果：返回T的根。 Value(T，cur_e)； 初始條件：樹T存在，cur_e是T中某個結(jié)點。 操作結(jié)果：返回cur_e的值。 Assign(T，cur_e，value)； 初始條件：樹T存在，cur_e是T中某個結(jié)點。 操作結(jié)果：結(jié)點cur_e賦值為value。 Parent(T，cur_e)； 初始條件：樹T存在，cur_e是T中某個結(jié)點。 操作結(jié)果：若cur_e是T的非根結(jié)點，則返回它的雙親。 否則函數(shù)值為“空”。 LeftChild(T，cur_e)； 初始條件：樹T存在，c

8、ur_e是T中某個結(jié)點。 操作結(jié)果：若cur_e是T的非葉子結(jié)點，則返回它的最左孩子，否則返回“空”。Rightsibling(T，cur_e)； 初始條件：樹T存在，cur_e是T中某個結(jié)點。 操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。 InsertChild(&T，&p，i，c)； 初始條件：樹T存在，p指向T中某個結(jié)點，1ip指結(jié)點的度+1，非空樹c與T不相交。 操作結(jié)果：插入c為T中p指結(jié)點的第i棵子樹。 DeleteChild(T，&p，i)； 初始條件：樹T存在，p指向T中某個結(jié)點，1ip指結(jié)點的度。 操作結(jié)果：刪除T中p所指結(jié)點

9、的第i棵子樹。TraverseTree(T，Visit()； 初始條件：樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)。 操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)，visit()一次至多次，一旦visit()失敗，則操作失敗。ADT Tree6.2 二 叉 樹 在討論一般樹的存儲結(jié)構(gòu)及其操作之前，我們首先研究一種稱為二叉樹的抽象數(shù)據(jù)。 6.2.1 二叉樹的定義 二叉樹二叉樹(BinaryTree)是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有二棵子樹(即二叉樹中不存在度大于2的結(jié)點)，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。 ADT BinaryTree 數(shù)據(jù)對象數(shù)據(jù)對象D： D是具有相

10、同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 若D= ，則R=，稱BinaryTree為空二叉樹； 若D!= ，則R=H，H是如下二元關(guān)系： (1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H 下無前驅(qū)； (2)若D-root!=，則存在D-root=Dl，Dr，且DlDr=； (3)若Dl!=，則Dl中存在唯一的元素xl，H，且存在Dl上的關(guān)系H1為H的子集；若Dr!=，則Dr中存在唯一的元素xr，H，且存在Dr上的關(guān)系Hr為H的子集； H=，Hl，Hr； (4)(Dl，Hl)是一棵符合本定義的二叉樹，稱為根的左子樹，(Dr，Hr)是一棵符合本定義的二叉樹，稱為根的右子樹。 基本操

11、作基本操作P： InitBiTree(&T)； 操作結(jié)果：構(gòu)造空二叉樹T。 DestroyBiTree(&T)； 初始條件：二叉樹T存在。 操作結(jié)果：銷毀二叉樹T。 CreateBiTree(&T，definition) 初始條件：definition給出二叉樹T的定義。 操作結(jié)果：按definition構(gòu)造二叉樹T。 ClearBiTree(&T)； 初始條件：二叉樹T存在。 操作結(jié)果：將二叉樹T清為空樹。 BiTreeEmpty(T)； 初始條件：二叉樹T存在。 操作結(jié)果：若T為空二叉樹，則返回TRUE， 否則FALSE。 BiTreeDepth(T)； 初

12、始條件：二叉樹T存在。 操作結(jié)果：返回T的深度。 Root(T)； 初始條件：二叉樹T存在。 操作結(jié)果：返回T的根。 Value(T，e)； 初始條件：二叉樹T存在，e是T中某個結(jié)點。 操作結(jié)果：返回e的值。 Assign(T，&e，value)； 初始條件：二叉樹T存在，e是T中某個結(jié)點。 操作結(jié)果：結(jié)點e賦值為value。 Parent(T，e)； 初始條件：二叉樹T存在，e是T中某個結(jié)點。 操作結(jié)果：若e是T的非根結(jié)點，則返回它的雙親。 LeftChild(T，e)； 初始條件：二叉樹T存在，e是T中某個結(jié)點。 操作結(jié)果：返回e的左孩子。若e無左孩子，則返回“空”。 RightC

13、hild(T，e)； 初始條件：二叉樹T存在，e是T中某個結(jié)點。 操作結(jié)果：返回e的右孩子。若e無右孩子，則返回“空”。 Leftsibling(T，e)； 初始條件：二叉樹T存在，e是T中某個結(jié)點。 操作結(jié)果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回“空”。 RightSibling(T，e)； 初始條件：二叉樹T存在，e是T中某個結(jié)點。 操作結(jié)果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回“空”。 InsertChild(T , p , LR , c); 初始條件：二叉樹T存在，p指向T中某個結(jié)點，LR為0或1，非空二叉樹c與T不相交且右子樹為空。 操作結(jié)果：根據(jù)LR為0

14、或1，插入c為T中p所指結(jié)點的左或右子樹。p所指結(jié)點的原有左或右子樹則成為c的右子樹。 DleteChild(T，p，LR)； 初始條件：二叉樹T存在，p指向T中某個結(jié)點，LR為0或1。 操作結(jié)果：根據(jù)Ix為0或1，刪除T中p所指結(jié)點的左或右子樹。 LevelOrderTraverse(T，Visit()； 初始條件：二叉樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)。 操作結(jié)果：層序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次， 一旦visit()失敗，則操作失敗。PreOrderTraverse(T，Visit()； 初始條件：二叉樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)。 操作結(jié)果：先

15、序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次，一旦visit失敗，則操作失敗。InOrderTraverse(T，Visit()； 初始條件：二叉樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)。 操作結(jié)果：中序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次，一旦visit失敗，則操作作失敗。 PostOrderTraverse(T，Visit()； 初始條件：二叉樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)。 操作結(jié)果：后序遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次，一旦visit失敗，則操作失敗。ADT BinaryTree 上述數(shù)據(jù)結(jié)構(gòu)的遞歸定義表明二叉樹或為空，或是由一個根結(jié)點加

16、上兩棵分別稱為左子樹和右子樹，兩棵互不相交的二叉樹組成。由于這兩棵子樹亦是二叉樹，則由二叉樹的定義它們可以是空樹。由此二叉樹可以有五種基本形態(tài) (a)空二叉樹；(b)僅有根結(jié)點的二叉樹；(c)右子樹為空的二叉樹；(d)左、右子樹均非空的二叉樹；(e)左子樹為空的二叉樹。 6.2.2 二叉樹的性質(zhì)二叉樹的性質(zhì) 二叉樹具有下列重要特性。 性質(zhì)性質(zhì)1 在二叉樹的第i層上至多有2i-1個結(jié)點(i1)。 利用歸納法容易證得此性質(zhì)。 i=1時，只有一個根結(jié)點。 顯然，2i-1=20=1是對的。 現(xiàn)在假定對所有的j，1ji，命題成立，即第j層上至多有2j-1個結(jié)點。那么，可以證明j=i時命題也成立。 由歸納

17、假設(shè)：第i-1層上至多有2i-2個結(jié)點。由于二叉樹的每個結(jié)點的度至多為 2，故在第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2*2i-2=2i-1。 性質(zhì)性質(zhì)2 深度為k的二叉樹至多有2k-1個結(jié)點，(k1)。由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為 k k (第i層上的最大結(jié)點數(shù)) =2i-1=2k -1 i=1 i=1 性質(zhì)性質(zhì)3 對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。 設(shè)n1為二叉樹T中度為1的結(jié)點數(shù)。因為二叉樹中所有結(jié)點的度均小于或等于2所以其結(jié)點總數(shù)為 n=n0+n1+n2 (61) 再看二叉樹中的分支數(shù)。除了根結(jié)點外，其

18、余結(jié)點都有一個分支進入，設(shè)B為分支總數(shù)，則n=B+1。由于這些分支是由度為1或2的結(jié)點射出的，所以又有B=n1+ 2n2。 n=n1+2n2+1 (62) 于是得由式(61)和(62)得 n0=n2+1 完全二叉樹和滿二叉樹，是兩種特殊形態(tài)的二叉樹。 一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹滿二叉樹。如圖6.4(a)所示是深度為4的滿二叉樹，這種樹的特點是每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。 6.4(a) 可以對滿二叉樹的結(jié)點進行連續(xù)編號，約定編號從根結(jié)點起，自上而下，自左至右。由此可引出完全二叉樹的定義：深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從

19、1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹完全二叉樹。 如圖6.4(b)所示為一棵深度為4的完全二叉樹。顯然，這種樹的特點是：(1)葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)；(2)對任一結(jié)點，若其右分支下的子孫的最大層次為L，則其左分支下的子孫的最大層次必為L或L+1。如圖6.4中(c)和(d)不是完全二叉樹。 6.4(b) 6.4(c) 6.4(d) 完全二叉樹將在很多場合下出現(xiàn)，下面介紹完全二叉樹的兩個重要特性。 性質(zhì)性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為 log2n +1。 證明：假設(shè)深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有 2k-1-1n2k-1 或 2k-1n2k 于是k-1log2n

20、1，則其雙親PARENT(i)是結(jié)點 i/2 。 (2) 如果2in，則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點)；否則其左孩子LCHILD(i)是結(jié)點2i。 (3)如果2i+1n，則結(jié)點i無右孩子；否則其右孩子RCHILD(i)是結(jié)點2i+1。 (a)結(jié)點i和i+1在同一層上； (b)結(jié)點i和i+1不在同一層上。 圖6.5 完全二義樹中結(jié)點i和i+1的左、右孩子 2i+1i/2i2ii+12i+22i+32i+3i+12i+2i2i2i+16.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 一、順序存儲結(jié)構(gòu) /二叉樹的順序存儲表示 #define MAX_TREE_SIZE 100， /二叉樹的最大結(jié)點數(shù)

21、 typedef TElemType SqBiTreeMAX_TREE_SIZE; /0號單元存儲根結(jié)點 SqBiTree bt； 按照順序存儲結(jié)構(gòu)的定義，在此約定，用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素，即將完全二叉樹上編號為i的結(jié)點元素存儲在如上定義的一維數(shù)組中下標(biāo)為i-1的分量中。 (a)完全二叉樹； (b)一般二叉樹。 圖66 二叉樹的順序存儲結(jié)構(gòu)12345678910111212345000067 二、鏈?zhǔn)酱鎯Y(jié)構(gòu) 由二叉樹的定義得知，二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左、右子樹的兩個分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點至少包含三個域：數(shù)據(jù)域和左

22、、右指針域。 圖6.7 二義樹的結(jié)點及其存儲結(jié)構(gòu)DATAPARENTLCHILD RCHILD(a)二叉樹的結(jié)點；rchilddatalchild(b)含有兩個指針域的結(jié)點結(jié)構(gòu)；rchildparentdatalchild(c)含有三個指針域的結(jié)點結(jié)構(gòu) 鏈表的頭指針指向二叉樹的根結(jié)點。容易證得，在含有n個結(jié)點的二叉鏈表中有n+1個空鏈域。在6.3節(jié)中我們將會看到可以利用這些空鏈域存儲其它有用信息，從而得到另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)線索鏈表。 (a)單支樹的二叉鏈表； (b)二叉鏈表； (c)三叉鏈表。 圖68 鏈表存儲結(jié)構(gòu) ABCDCBAGFEDABCDEFG6.3 遍歷二叉樹和線索二叉樹 6.3.1

23、 遍歷二叉樹遍歷二叉樹 遍歷二叉樹(Traversing Binary Tree) ，即如何按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。 回顧二叉樹的遞歸定義可知，二叉樹是由三個基本單元組成：根結(jié)點、左子樹和右子樹。因此，若能依次遍歷這三部分，便是遍歷了整個二叉樹。假如以L、D、R分別表示遍歷左子樹、訪問根結(jié)點和遍歷右子樹，則可有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷二叉樹的方案。若限定先左后右，則只有前三種情況，分別稱之為先(根)序遍歷，中(根)序遍歷和后(根)序遍歷?；诙鏄涞倪f歸定義，可得下述遍歷二叉樹的遞歸算法定義。 先序遍歷二叉樹的操

24、作定義為： 若二叉樹為空，則空操作；否則 (1)訪問根結(jié)點； (2)先序遍歷左子樹； (3)先序遍歷右子樹。中序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 (1)中序遍歷左子樹； (2)訪問根結(jié)點； (3)中序遍歷右子樹。后序遍歷二叉樹的操作定義為： 若二叉樹為空，則空操作；否則 (1)后序遍歷左子樹； (2)后序遍歷右子樹； (3)訪問根結(jié)點。 例如圖6.9所示的二叉樹表示下述表達式 a+b*(c-d)-e/f 若先序遍歷此二叉樹，按訪問結(jié)點的先后次序?qū)⒔Y(jié)點排列起來，可得到二叉樹的先序序列為 -+a*b-cd/ef (63) 類似地，中序遍歷此二叉樹，可得此二叉樹的中序序列為 a

25、+b*c-d-e/f (64) 后序遍歷此二叉樹，可得此二叉樹的后序 序列為 abcd -*+ef/- (65) 從表達式來看，以上三個序列(63)、 (64)和(65)恰好為表達式的前綴表 示(波蘭式)、中綴表示和后綴表示 (逆波蘭式)。 圖6.9表達式的二叉樹Status PreOrderTraverse ( Bitree T, Status (*Visit)(TElemType e)1if(T) 2 if(Visit(T-data)3 if(PreOrderTraverse(T-lchild，Visit) if(PreOrderTraverse(T-rchild，Visit) retur

26、n OK;5 return ERROR；6 else return OK；7/PreOrderTraverse 二叉樹操作 計算一棵二叉樹的葉子結(jié)點數(shù)目 這個操作可以使用三種遍歷順序中的任何一種，只是需要將訪問操作變成判斷該結(jié)點是否為葉子結(jié)點，如果是葉子結(jié)點將累加器加1即可。下面這個算法是利用先序遍歷實現(xiàn)的。 理解定義：如果二叉樹有左（右）子樹，則分別求出左右子樹葉子結(jié)點數(shù)目（指針換成左或右子樹），然后求和。 三種情況，1、空樹；2、只有一個根節(jié)點；3、有子樹 void Leaf(BTree BT,int &count) if (BT) if (!BT-lchild) & (!

27、BT-rchild) count+; Leaf(BT-lchild, count); /計算左子樹的葉子結(jié)點個數(shù) Leaf(BT-rchild, count); /計算右子樹的葉子結(jié)點個數(shù) 求二叉樹的高度 這個操作使用后序遍歷比較符合人們求解二叉樹高度的思維方式。首先分別求出左右子樹的高度，在此基礎(chǔ)上得出該棵樹的高度，即左右子樹較大的高度值加1。 int hight(BTree BT) /h1和h2分別是以BT為根的左右子樹的高度 if (BT=NULL) return 0; else h1 = hight(BT-lchild); h2 = hight(BT-right); return ma

28、xh1,h2+1; 復(fù)制二叉樹 根據(jù)已有的一個二叉樹，復(fù)制一棵二叉樹。 BiTNode *GetTreeNode(TelmentType item, BiTNode *lptr, BiTNode *rptr) if (!(T=(BitNode *)malloc(sizeof(BiTNode) exit (1);T-data = item;T-lchild = lptr;T-rchild = rptr;Retrun T; BiTNode *CopyTree(BiTNode *T) if(!T) return NULL; if(T-lchild) newlptr = CopyTree (T-lch

29、ild); else newlptr = NULL; if(T-rchild) newrptr = CopyTree (T-rchild); else newrptr = NULL; newnode = GetTreeNode(T-data, newlptr,newrptr); return newnode; 建立二叉樹根據(jù)先序序列（包含空格）創(chuàng)建二叉樹。 先序遍歷和中序遍歷共同確定一個二叉樹 Status CreateBiTree(BiTree&T)scanf(&ch)； if(ch= ) T=NULL； else if(!(T=(BiTNode*)malloc(sizeof

30、(BiTNode) exit(OVERFLOW) ; T-data=ch； /生成根結(jié)點 CreateBiTree(T-lchild)； /構(gòu)造左子樹 CreateBiTree(T-rchild)； /構(gòu)造右子樹 return OK; /CreateBiTree 6.4 樹和森林 這一節(jié)我們將討論樹的表示及其遍歷操作，并建立森林與二叉樹的對應(yīng)關(guān)系。 6.4.1 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu) 在大量的應(yīng)用中，人們曾使用多種形式的存儲結(jié)構(gòu)來表示樹。這里，我們介紹三種常用的鏈表結(jié)構(gòu)。 一、雙親表示法 假設(shè)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在鏈表中的位置，其形式說明如

31、下： /樹的雙親表存儲表示 #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data； int parent； /雙親位置域 PTNode；typedef struct PTNode nodesMAX_TREE_SIZE int n； /結(jié)點數(shù)PTree；例如，圖6.13展示一棵樹及其雙親表示的存儲結(jié)構(gòu)。 ABFKHGEDCR 6 K 6 H 6 G 3 F 1 E 1 D 0 C 0 B 0 A -1 這種存儲結(jié)構(gòu)利用了每個結(jié)點(除根以外)只有唯一的雙親的性質(zhì)。PARENT(T，x)操作可以在常量時

32、間內(nèi)實現(xiàn)。反復(fù)調(diào)用PARENT操作，直到遇見無雙親的結(jié)點時，便找到了樹的根，這就是ROOT(x)操作的執(zhí)行過程。但是，在這種表示法中，求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)。二、孩子表示法 由于樹中每個結(jié)點可能有多棵子樹，則可用多重鏈表，即每個結(jié)點有多個指針域，其中每個指針指向一棵子樹的根結(jié)點，此時鏈表中的結(jié)點可以有如下兩種結(jié)點格式 若采用第一種結(jié)點格式，則多重鏈表中的結(jié)點是同構(gòu)的，其中d為樹的度。由于樹中很多結(jié)點的度小于d，所以鏈表中有很多空鏈域，空間較浪費，不難推出，在一棵有n個結(jié)點度為k的樹中必有n(k-1)+1個空鏈域。若采用第二種結(jié)點格式，則多重鏈表中的結(jié)點是不同構(gòu)的，其中d為結(jié)點的度，de

33、gree域的值同d。此時，雖能節(jié)約存儲空間，但操作不方便。datachild1child2 childddatadegreechild1child2 childd 另一種辦法是把每個結(jié)點的孩子結(jié)點排列起來，看成是一個線性表，且以單鏈表作存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表(葉子的孩子鏈表為空表)。而n個頭指針又組成一個線性表，為了便于查找，可采用順序存儲結(jié)構(gòu)。 對應(yīng)圖6.13 K H G F E R D C B A3521987060123456789412986073K6H6G6F2E0R-1D0C4B4A40123456789這種存儲結(jié)構(gòu)可形式地說明如下：/樹的孩子鏈表存儲表示 typede

34、f struct CTNode /孩子結(jié)點 int child； struct CTNode *next； *ChildPtr； typedef struct TElemType data； ChildPtr firstchild；/孩子鏈表頭指針 CTBox； typedef struct CTBox nodesMAX_TREE_SXZE； int n，r； /結(jié)點數(shù)和根的位置 CTree； 三、孩子兄弟表示法 又稱二叉樹表示法，或二叉鏈表表示法。即以二叉鏈表作樹的存儲結(jié)構(gòu)。鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點，分別命名為 firstchild域和nextsib

35、ling域。/樹的二叉鏈表(孩子兄弟)存儲表示 typedef struct CSNode ElemType data； struct CSNode * firstchild， *nextsibling； CSNode，*CSTree； 圖6.15是圖6.13中的樹的孩子兄弟鏈表。利用這種存儲結(jié)構(gòu)便于實現(xiàn)各種樹的操作，首先易于實現(xiàn)找結(jié)點孩子等的操作。例如：若要訪問結(jié)點x的第i個孩子，只要先從firstchild域找到第1個孩子結(jié) 點 ， 然 后 沿 著 孩 子 結(jié) 點 的 nextsibling域連續(xù)走i-1步，便可找到x的第i個孩子。當(dāng)然，如果為每個結(jié)點增設(shè)一個PARENT域，則同樣能方便地

36、實現(xiàn)PARENT(T，x)操作。 KFACDEGHBR 6.4.2 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換 由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。也就是說，給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)，從物理結(jié)構(gòu)來看，它們的二叉鏈表是相同的，只是解釋不同而已。 圖6.16 樹與二叉樹的對應(yīng)關(guān)系示例 DECBAEDCBAEDCBAADECB樹二叉樹 對應(yīng)ABCDE存儲存儲解釋解釋 從樹的二叉鏈表表示的定義可知，任何一棵樹和對應(yīng)的二叉樹，其右子樹必空。若把森林中第二棵樹的根結(jié)點看成是第一棵樹的根結(jié)點的兄弟，則同樣可導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系

37、。例如， 森林與二叉樹對應(yīng) 樹與二叉樹對應(yīng) 樹根連接DCBAFEJIHGDCBAFEJIHGJIHDCGFEBA 這個一一對應(yīng)的關(guān)系導(dǎo)致森林或樹與二叉樹可以相互轉(zhuǎn)換，其形式定義如下 一、森林轉(zhuǎn)換成二叉樹 如果F=Tl，T2，Tm是森林，則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹B=(root，LB，RB)。 (1)若F為空，即m=0，則B為空樹； (2)若F非空，即m!=0，則B的根root即為森林中第一棵樹的根ROOT(T1)；B的左子樹LB是從Tl中根結(jié)點的子樹森Fl=T11,T12,T1m轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F=T2,T3,Tm轉(zhuǎn)換而成的二叉樹。 二、二叉樹轉(zhuǎn)換成森林 如果B=(r

38、oot，LB，RB)是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F=T1，T2，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)換而成的森林。 從上述遞歸定義容易寫出相互轉(zhuǎn)換的遞歸算法。同時，森林和樹的操作亦可轉(zhuǎn)換成二叉樹的操作來實現(xiàn)。 6.6 赫夫曼樹及其應(yīng)用 赫夫曼(Huffman)樹，又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。 6.6.1 最優(yōu)二叉樹(赫夫曼樹) 首先給出路徑和路徑長度的概念。從樹中

39、一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路徑上的分支數(shù)目稱做路徑長度。樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和。6.2.1節(jié)中定義的完全二叉樹就是這種路徑長度最短的二叉樹。 若將上述概念推廣到一般情況，考慮帶權(quán)的結(jié)點。結(jié)點的帶權(quán)路徑長度為從該結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積。樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記作 n WPL= wklk k=1 假設(shè)有n個權(quán)值w1,w2,wn，試構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子結(jié)點帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。 例如，圖6.22中的三棵二叉樹，都有4個葉子結(jié)

40、點a、b、c、d，分別帶權(quán)7、5、2、4，它們的帶權(quán)路徑長度分別為 (a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4* 3=35 其中以(c)樹的為最小。可以驗證，它恰為赫夫曼樹，即其帶權(quán)路徑長度在所有帶權(quán)為7、 5、2、4的四個葉子結(jié)點的二叉樹中居最小。cbda(c)abdc(b)dcba(a) 利用赫夫曼樹可以得到最佳判定算法。 例如，要編制一個將百分制轉(zhuǎn)換成五級分制的程序。顯然，此程序很簡單，只要利用條件語句便可完成。如： if(a60)b=“bad”； else if(a70) b=“pas

41、s”； else if(a80) b=“general”； else if(a90) b=“good”； else b=“excellent”； 這個判定過程可以圖6.23(a)的判定樹來表示。如果上述程序需反復(fù)使用，而且每次的輸入量很大，則應(yīng)考慮上述程序的質(zhì)量問題，即其操作所需時間。因為在實際生活中，學(xué)生的成績在五個等級上的分布是不均勻的。假設(shè)其分布規(guī)律如下表所示： 分?jǐn)?shù) 0-5960-69 70-79 80-8990-100比例數(shù) 0.05 0.15 0.40 0.30 0.10 則80以上的數(shù)據(jù)需進行三次或三次以上的比較才能得出結(jié)果。假定以5，15，40，30和 10為權(quán)構(gòu)造一棵有五個葉

42、子結(jié)點的赫夫曼樹，則可得到如圖6.23(b)所示的判定過程，它可使大部分的數(shù)據(jù)經(jīng)過較少的比較次數(shù)得出結(jié)果。 圖6.23(a) (b)A60A70A80A90良好優(yōu)秀中等及格不及格YYYYNNNNa6060=a7080=a9070=a80良好中等及格優(yōu)秀不及格YYNYNNNY 但由于每個判定框都有兩次比較，將這兩次比較分開，我們得到如圖6.23(c)所示的判定樹，按此判定樹可寫出相應(yīng)的程序。假設(shè)現(xiàn)有10000個輸入數(shù)據(jù)，若按圖6.23(a)的判定過程進行操作，則總共需進行31500次比較；而若按圖6.23(c)的判定過程進行操作，則總共僅需進行22000次比較。 (c)A60A70A80A1時，

43、其余結(jié)點可分為m(m0)個互不相交的有限集T1，T2，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹子樹(SubTree)。 2.2 樹的特性及表示方式 樹的結(jié)構(gòu)定義是一個遞歸的定義，即在樹的定義中又用到樹的概念，它道出了樹的固有特性。 樹是以分支關(guān)系定義的層次結(jié)構(gòu)。 樹中除根結(jié)點外其它結(jié)點都由一個分支引入，而每個結(jié)點可有至多個分支，因此樹中除根結(jié)點無前趨結(jié)點外，其它結(jié)點都只有一個直接前趨結(jié)點，但可有至多個直接后繼結(jié)點。顯然數(shù)是一種非線性的結(jié)構(gòu)。 樹有多種表示形式，如：樹形表示法、嵌套集合表示法、凹入式表示法、廣義表表示法。.3 樹的相關(guān)術(shù)語結(jié)點結(jié)點的度樹的度葉子結(jié)點雙親結(jié)點孩子結(jié)點兄弟

44、結(jié)點樹的深度（高度）路徑路徑長度樹的路徑長度祖先結(jié)點子孫結(jié)點有序樹森林 2.4 二叉樹的定義和它的五種形態(tài) 二叉樹(BinaryTree)是一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有二棵子樹(即二叉樹中不存在度大于2的結(jié)點)，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。 五種形態(tài)為空二叉樹、只有一個根結(jié)點的二叉樹、右子樹為空的二叉樹、左子樹為空的二叉樹、左右子樹非空的二叉樹。 2.5 二叉樹的性質(zhì) 熟練掌握二叉樹的結(jié)構(gòu)特性，掌握完全二叉樹和滿二叉樹的定義，了解相應(yīng)的證明方法。 性質(zhì)性質(zhì)1 在二叉樹的第i層上至多有2i-1個結(jié)點(i1)。 性質(zhì)性質(zhì)2 深度為k的二叉樹至多有2k-1個結(jié)點，(

45、k1)。 性質(zhì)性質(zhì)3 對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。 性質(zhì)性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為 log2n +1。 性質(zhì)性質(zhì)5 如果對一棵有n個結(jié)點的完全二叉樹(其深度為log2n+1)的結(jié)點按層序編號(從第1層到第log2n+1層，每層從左到右)，則對任一結(jié)點i(1in)，有 (1)如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i1，則其雙親PARENT(i)是結(jié)點 i/2 。 (2)如果2in，則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點)；否則其左孩子LCHILD(i)是結(jié)點2i。 (3)如果2i+1n，則結(jié)點i無右孩子；否則其右孩子RCH

46、ILD(i)是結(jié)點2i+1。 2.7 遍歷二叉樹和線索二叉樹 遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實現(xiàn)二叉樹遍歷的各種算法與所采用的存儲結(jié)構(gòu)有關(guān)。不僅要熟練掌握各種遍歷策略的遞歸和非遞歸算法，了解遞歸過程中棧的作用和狀態(tài)，而且能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作。 理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟悉掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。2.8 樹的存儲結(jié)構(gòu)及與二叉樹的轉(zhuǎn)換 熟悉樹的各種存儲結(jié)構(gòu)（雙親表示法 、孩子表示法、孩子兄弟

47、表示法）及其特點，因為樹和二叉樹都可以用二叉鏈表表示，則以二叉鏈表為媒介很容易導(dǎo)出樹與二叉樹之間的對應(yīng)關(guān)系。掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結(jié)構(gòu)是其它操作的前提，因此應(yīng)掌握1至2種建立二叉樹和樹的存儲結(jié)構(gòu)方法（雙親表示法、孩子表示法、孩子兄弟表示法）。2.9 森林與二叉樹的轉(zhuǎn)換（略） 2.10 樹和森林的遍歷 樹與森林的先根序遍歷結(jié)果與對應(yīng)的二叉樹的先序序列相同，后根序遍歷與對應(yīng)二叉樹的中序序列相同。2.11 最優(yōu)二叉樹（哈夫曼樹）的概念 樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記作WPL，帶權(quán)路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。 2.13 赫夫曼樹構(gòu)造算法。 (1) 根據(jù)給定的n個權(quán)值Wl，W2，Wn構(gòu)成n棵二叉樹的集合F=T1，T2，Tn，其中每棵二叉樹Ti中只有一個帶權(quán)為Wi的根結(jié)點，其左右子樹均空。 (2) 在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點