數據結構講義

第6章樹和二叉樹樹與二叉樹第1頁

樹型結構是一類非常主要非線性結構。直觀地，樹型結構是以分支關系定義層次結構。樹在計算機領域中也有著廣泛應用，比如在編譯程序中，用樹來表示源程序語法結構；在數據庫系統中，可用樹來組織信息；在分析算法行為時，可用樹來描述其執行過程等等。本章將詳細討論樹和二叉樹數據結構，主要介紹樹和二叉樹概念、術語，二叉樹遍歷算法。樹和二叉樹各種存放結構以及建立在各種存放結構上操作及應用等。樹與二叉樹第2頁6.1

樹基本概念1

樹定義

樹(Tree)是n(n≧0)個結點有限集合T，若n=0時稱為空樹，不然：⑴有且只有一個特殊稱為樹根(Root)結點；⑵若n>1時，其余結點被分為m(m>0)個互不相交子集T1,T2,T3…Tm，其中每個子集本身又是一棵樹，稱其為根子樹(Subtree)。這是樹遞歸定義，即用樹來定義樹，而只有一個結點樹必定僅由根組成，如圖6-1(a)所表示。

6.1.1

樹定義和基本術語樹與二叉樹第3頁2

樹基本術語⑴

結點(node)：一個數據元素及其若干指向其子樹分支。⑵

結點度(degree)

、樹度：結點所擁有子樹棵數稱為結點度。樹中結點度最大值稱為樹度。

圖6-1樹示例形式AABDCEGFHIMJNKL(a)

只有根結點(b)普通樹樹與二叉樹第4頁

如圖6-1(b)中結點A度是3，結點B度是2，結點M度是0，樹度是3。⑶

葉子(left)結點、非葉子結點：樹中度為0結點稱為葉子結點(或終端結點)。相對應地，度不為0結點稱為非葉子結點(或非終端結點或分支結點)。除根結點外，分支結點又稱為內部結點。如圖6-1(b)中結點H、I、J、K、L、M、N是葉子結點，而全部其它結點都是分支結點。(內部結點?)⑷

孩子結點、雙親結點、弟兄結點

一個結點子樹根稱為該結點孩子結點(child)或子結點；對應地，該結點是其孩子結點雙親結點(parent)或父結點。樹與二叉樹第5頁

如圖6-1(b)中結點B、C、D是結點A子結點，而結點A是結點B、C、D父結點；類似地結點E、F是結點B子結點，結點B是結點E、F父結點。同一雙親結點全部子結點互稱為弟兄結點。

如圖6-1(b)中結點B、C、D是弟兄結點；結點E、F是弟兄結點。⑸

層次、堂弟兄結點

要求樹中根結點層次為1，其余結點層次等于其雙親結點層次加1。若某結點在第l(l≧1)層，則其子結點在第l+1層。雙親結點在同一層上全部結點互稱為堂弟兄結點。如圖6-1(b)中結點G與結點E、F、H、I、J。樹與二叉樹第6頁⑹

結點層次路徑、祖先、子孫

從根結點開始，抵達某結點p所經過全部結點成為結點p層次路徑(有且只有一條)。

結點p層次路徑上全部結點（p除外）稱為p祖先(ancester)。以某一結點為根子樹中任意結點稱為該結點子孫結點(descent)。⑺

樹深度(depth)：樹中結點最大層次值，又稱為樹高度，如圖6-1(b)中樹高度為4。⑻

有序樹和無序樹：對于一棵樹，若其中每一個結點子樹（若有）含有一定次序，則該樹稱為有序樹，不然稱為無序樹。樹與二叉樹第7頁⑼

森林(forest)：是m(m≧0)棵互不相交樹集合。顯然，若將一棵樹根結點刪除，剩下子樹就組成了森林。3樹表示形式⑴倒懸樹。是最慣用表示形式，如圖6-1(b)。⑵嵌套集合。是一些集合集體，對于任何兩個集合，或者不相交，或者一個集合包含另一個集合。圖6-2(a)是圖6-1(b)樹嵌套集合形式。⑶廣義表形式。圖6-2(b)是樹廣義表形式。⑷凹入法表示形式。見P120樹表示方法多樣化說明了樹結構主要性。樹與二叉樹第8頁圖6-2樹表示形式(a)

嵌套集合形式(b)廣義表形式(A(B(E(K,L),F),C(G(M,N)),D(H,I,J)HIJDFBKLECMNGA樹與二叉樹第9頁6.1.2

樹抽象數據類型定義ADTTree{數據對象D：D是含有相同數據類型數據元素集合。數據關系R：若D為空集，則稱為空樹；

……基本操作：……}ADTTree詳見p118~119。樹與二叉樹第10頁6.2

二叉樹6.2.1

二叉樹定義1二叉樹定義

二叉樹(Binarytree)是n(n≥0)個結點有限集合。若n=0時稱為空樹，不然：⑴

有且只有一個特殊稱為樹根(Root)結點；⑵

若n>1時，其余結點被分成為二個互不相交子集T1,T2，分別稱之為左、右子樹，而且左、右子樹又都是二叉樹。由此可知，二叉樹定義是遞歸。樹與二叉樹第11頁

二叉樹在樹結構中起著非常主要作用。因為二叉樹結構簡單，存放效率高，樹操作算法相對簡單，且任何樹都很輕易轉化成二叉樹結構。上節中引入相關樹術語也都適合用于二叉樹。2

二叉樹基本形態二叉樹有5種基本形態，如圖6-3所表示。AAAA(a)(b)(c)(d)(e)(a)空二叉樹(b)單結點二叉樹(c)右子樹為空(d)左子樹為空(e)左、右子樹都不空圖6-3

二叉樹基本形態樹與二叉樹第12頁6.2.2

二叉樹性質性質1：在非空二叉樹中，第i層上至多有2i-1個結點(i≧1)。證實：用數學歸納法證實。當i=1時：只有一個根結點，21-1=20=1，命題成立。現假設對i>1時，處于第i-1層上至多有2(i-1)-1個結點。由歸納假設知，第i-1層上至多有2i-2個結點。因為二叉樹每個結點度最大為2，故在第i層上最大結點數為第i-1層上最大結點數2倍。即2×2i-2＝2i-1

證畢性質2：深度為k二叉樹至多有2k-1個結點（k≧1)。樹與二叉樹第13頁證實：深度為k二叉樹最大結點數為二叉樹中每層上最大結點數之和。由性質1知，二叉樹第1層、第2層?第k層上結點數至多有：20、21…2k-1。∴總結點數至多有：20+21+

…+2k-1=2k-1證畢

性質3：對任何一棵二叉樹，若其葉子結點數為n0，度為2結點數為n2，則n0=n2+1。證實：設二叉樹中度為1結點數為n1，二叉樹中總結點數為N，因為二叉樹中全部結點均小于或等于2，則有：N=n0+n1+n2再看二叉樹中分支數：樹與二叉樹第14頁除根結點外，其余每個結點都有唯一一個進入分支，而全部這些分支都是由度為1和2結點射出。設B為二叉樹中分支總數，則有：N=B+1

∴

B＝n1+2n2

∴N=B+1=n1+2n2+1

∴n0+n1+n2=n1+2n2+1

即n0=n2+1證畢滿二叉樹和完全二叉樹

一棵深度為k且有2k-1個結點二叉樹稱為滿二叉樹(FullBinaryTree)。如圖6-4(a)就是一棵深度為4滿二叉樹。樹與二叉樹第15頁894101151213614157213894101152112673(a)滿二叉樹(b)完全二叉樹1362455674213(c)非完全二叉樹圖6-4特殊形態二叉樹樹與二叉樹第16頁滿二叉樹特點：基本特點是每一層上結點數總是最大結點數。滿二叉樹全部支結點都有左、右子樹。可對滿二叉樹結點進行連續編號，若要求從根結點開始，按“自上而下、自左至右”標準進行。完全二叉樹(CompleteBinaryTree)：假如深度為k，由n個結點二叉樹，當且僅當其每一個結點都與深度為k滿二叉樹中編號從1到n結點一一對應，該二叉樹稱為完全二叉樹。或深度為k滿二叉樹中編號從1到n前n個結點組成了一棵深度為k完全二叉樹。其中2k-1≦

n≦2k-1

。樹與二叉樹第17頁

完全二叉樹是滿二叉樹一部分，而滿二叉樹是完全二叉樹特例。完全二叉樹特點：

若完全二叉樹深度為k，則全部葉子結點都出現在第k層或k-1層。對于任一結點，假如其右子樹最大層次為l，則其左子樹最大層次為l或l+1。性質4：n個結點完全二叉樹深度為：㏒2n

+1。

其中符號：x表示小于x最大整數。

x

表示大于x最小整數。證實：假設完全二叉樹深度為k，則依據性質2及完全二叉樹定義有：樹與二叉樹第18頁2k-1-1<n≦2k-1

或

2k-1≦n<2k取對數得：k－1<㏒2n<k

因為k是整數。∴k=㏒2n

+1證畢性質5：若對一棵有n個結點完全二叉樹(深度為㏒2n+1)結點按層（從第1層到第㏒2n

+1層)序自左至右進行編號,則對于編號為i（1≦i≦n)結點：⑴若i=1：則結點i是二叉樹根，無雙親結點；不然，若i>1，則其雙親結點編號是

i/2

。⑵假如2i>n：則結點i為葉子結點，無左孩子；不然，其左孩子結點編號是2i。⑶假如2i+1>n：則結點i無右孩子；不然，其右孩子結點編號是2i+1。樹與二叉樹第19頁

證實：用數學歸納法證實。首先證實⑵和⑶，然后由⑵和⑶導出⑴。當i=1時，由完全二叉樹定義知，結點i左孩子編號是2，右孩子編號是3。若2>n，則二叉樹中不存在編號為2結點，說明結點i左孩子不存在。若3>n，則二叉樹中不存在編號為3結點，說明結點i右孩子不存在。現假設對于編號為j(1≦j≦i)結點，(2)和(3)成立。即：◆

當2j≦n：結點j左孩子編號是2j；當2j>n時，結點j左孩子結點不存在。樹與二叉樹第20頁◆當2j+1≦n：結點j右孩子編號是2j+1；當2j+1>n時，結點j右孩子結點不存在。當i=j+1時，由完全二叉樹定義知，若結點i左孩子結點存在，則其左孩子結點編號一定等于編號為j右孩子編號加1，即結點i左孩子編號為：(2j+1)+1=2(j+1)=2i如圖6-5所表示，且有2i≦n。相反，若2i>n，則左孩子結點不存在。一樣地，若結點i右孩子結點存在，則其右孩子編號為：2i+1，且有2i+1≦n。相反，若2i+1>n，則左孩子結點不存在。結論(2)和(3)得證。再由(2)和(3)來證實(1)。當i=1時，顯然編號為1是根結點，無雙親結點。樹與二叉樹第21頁當i>1時，設編號為i結點雙親結點編號為m，若編號為i結點是其雙親結點左孩子，則由(2)有：i=2m，即m=i/2；若編號為i結點是其雙親結點右孩子，則由(3)有：i=2m+1，即m=(i-1)

/2；∴當i>1時，其雙親結點編號為i/2

。證畢ii+12i2i+12i+22i+3└i/2┘(a)i和i+1結點在同一層i+12i+22i+3i2i2i+1……(b)i和i+1結點不在同一層圖6-5完全二叉樹中結點i和i+1左右孩子樹與二叉樹第22頁6.2.3

二叉樹存放結構1次序存放結構

二叉樹存放結構類型定義：#defineMAX_SIZE100typedeftelemtypesqbitree[MAX_SIZE];用一組地址連續存放單元依次“自上而下、自左至右”存放完全二叉樹數據元素。對于完全二叉樹上編號為i結點元素存放在一維數組下標值為i-1分量中，如圖6-6(c)所表示。對于普通二叉樹，將其每個結點與完全二叉樹上結點相對照，存放在一維數組中，如圖6-6(d)所表示。樹與二叉樹第23頁abcdhiejklfg(a)完全二叉樹(b)非完全二叉樹abcdefgh???123456789101112

abcdefghijkl

(c)完全二叉樹次序存放形式1234567891011abcde?h?

?

fg(d)非完全二叉樹次序存放形式圖6-6二叉樹及其次序存放形式樹與二叉樹第24頁最壞情況下，一個深度為k且只有k個結點單支樹需要長度為2k-1一維數組。2鏈式存放結構

設計不一樣結點結構可組成不一樣鏈式存放結構。(1)結點類型及其定義①二叉鏈表結點。有三個域：一個數據域，兩個分別指向左右子結點指針域，如圖6-7(a)所表示。typedefstructBTNode{ElemTypedata;structBTNode*Lchild,*Rchild;}BTNode,*BTree;樹與二叉樹第25頁②三叉鏈表結點。除二叉鏈表三個域外，再增加一個指針域，用來指向結點父結點，如圖6-7(b)所表示。typedefstructBTNode_3{ElemTypedata;structBTNode_3*Lchild,*Rchild,*parent;}BTNode_3;

LchilddataRchildLchilddataparentRchild(a)二叉鏈表結點(b)三叉鏈表結點圖6-7鏈表結點結構形式樹與二叉樹第26頁(2)二叉樹鏈式存放形式

例有一棵普通二叉樹，如圖6-8(a)所表示。以二叉鏈表和三叉鏈表方式存放結構圖分別如圖6-8(b)、6-8(c)所表示。圖6-8二叉樹及其鏈式存放結構(a)二叉樹afedcbg(c)三叉鏈表a?

?b?c?d?e?f??g?T(b)二叉鏈表

a?

b?c?

d?e?g??f?T樹與二叉樹第27頁6.3

遍歷二叉樹及其應用遍歷二叉樹(TraversingBinaryTree)：是指按指定規律對二叉樹中每個結點訪問一次且僅訪問一次。

所謂訪問是指對結點做某種處理。如：輸出信息、修改結點值等。二叉樹是一個非線性結構，每個結點都可能有左、右兩棵子樹，所以，需要尋找一個規律，使二叉樹上結點能排列在一個線性隊列上，從而便于遍歷。二叉樹基本組成：根結點、左子樹、右子樹。若能依次遍歷這三部分，就是遍歷了二叉樹。樹與二叉樹第28頁

若以L、D、R分別表示遍歷左子樹、遍歷根結點和遍歷右子樹，則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若要求先左后右，則只有前三種情況三種情況，分別是：DLR——先(根)序遍歷。LDR——中(根)序遍歷。LRD——后(根)序遍歷。對于二叉樹遍歷，分別討論遞歸遍歷算法和非遞歸遍歷算法。遞歸遍歷算法含有非常清楚結構，但初學者往往難以接收或懷疑，不敢使用。實際上，遞歸算法是由系統經過使用堆棧來實現控制。而非遞歸算法中控制是由設計者定義和使用堆棧來實現。樹與二叉樹第29頁6.3.1

先序遍歷二叉樹1遞歸算法算法遞歸定義是：

若二叉樹為空，則遍歷結束；不然⑴訪問根結點；⑵先序遍歷左子樹(遞歸調用本算法)；⑶先序遍歷右子樹(遞歸調用本算法)。樹與二叉樹第30頁先序遍歷遞歸算法voidPreorderTraverse(BTNode*T){if(T!=NULL){visit(T->data);/*訪問根結點*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}/*圖6-8(a)二叉樹，輸出次序是：abccegf*/說明：visit()函數是訪問結點數據域，其要求視詳細問題而定。樹采取二叉鏈表存放結構，用指針變量T來指向。樹與二叉樹第31頁2非遞歸算法設T是指向二叉樹根結點指針變量，非遞歸算法是：若二叉樹為空，則返回；不然，令p=T；⑴訪問p所指向結點；⑵q=p->Rchild，若q不為空，則q進棧；⑶p=p->Lchild，若p不為空，轉(1)，不然轉(4)；⑷退棧到p，轉(1)，直到棧空為止。算法實現：樹與二叉樹第32頁#defineMAX_NODE50voidPreorderTraverse(BTNode*T){BTNode*Stack[MAX_NODE],*p=T,*q;inttop=0;if(T==NULL)printf(“BinaryTreeisEmpty!\n”);else{do{visit(p->data);q=p->Rchild;if(q!=NULL)stack[++top]=q;p=p->Lchild;if(p==NULL){p=stack[top];top--;}}while(p!=NULL);}}樹與二叉樹第33頁6.3.2

中序遍歷二叉樹1遞歸算法算法遞歸定義是：

若二叉樹為空，則遍歷結束；不然⑴中序遍歷左子樹(遞歸調用本算法)；⑵訪問根結點；⑶中序遍歷右子樹(遞歸調用本算法)。樹與二叉樹第34頁中序遍歷遞歸算法voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*訪問根結點*/InorderTraverse(T->Rchild);}}

/*圖6-8(a)二叉樹，輸出次序是：cbegdfa*/樹與二叉樹第35頁2非遞歸算法設T是指向二叉樹根結點指針變量，非遞歸算法是：若二叉樹為空，則返回；不然，令p=T⑴若p不為空，p進棧，p=p->Lchild；⑵不然(即p為空)，退棧到p，訪問p所指向結點；⑶p=p->Rchild，轉(1)；直到棧空為止。算法實現：樹與二叉樹第36頁#defineMAX_NODE50voidInorderTraverse(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,bool=1;if(T==NULL)printf(“BinaryTreeisEmpty!\n”);else{do{while(p!=NULL){stack[++top]=p;p=p->Lchild;}if(top==0)bool=0;else{p=stack[top];top--;visit(p->data);p=p->Rchild;}}while(bool!=0);}}樹與二叉樹第37頁6.3.3

后序遍歷二叉樹1遞歸算法算法遞歸定義是：

若二叉樹為空，則遍歷結束；不然⑴后序遍歷左子樹(遞歸調用本算法)；⑵后序遍歷右子樹(遞歸調用本算法)；⑶訪問根結點。樹與二叉樹第38頁后序遍歷遞歸算法voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*訪問根結點*/

}}

/*圖6-8(a)二叉樹，輸出次序是：cgefdba*/遍歷二叉樹算法中基本操作是訪問結點，所以，不論是哪種次序遍歷，對有n個結點二叉樹，其時間復雜度均為O(n)。樹與二叉樹第39頁6.3.4

層次遍歷二叉樹

層次遍歷二叉樹，是從根結點開始遍歷，按層次次序“自上而下，從左至右”訪問樹中各結點。為確保是按層次遍歷，必須設置一個隊列，初始化時為空。設T是指向根結點指針變量，層次遍歷非遞歸算法是：若二叉樹為空，則返回；不然，令p=T，p入隊；⑴隊首元素出隊到p；⑵訪問p所指向結點；⑶將p所指向結點左、右子結點依次入隊。直到隊空為止。樹與二叉樹第40頁#defineMAX_NODE50voidLevelorderTraverse(BTNode*T){BTNode*Queue[MAX_NODE],*p=T;intfront=0,rear=0;if(p!=NULL){Queue[++rear]=p;/*根結點入隊*/while(front<rear){p=Queue[++front];visit(p->data);if(p->Lchild!=NULL)Queue[++rear]=p;/*左結點入隊*/if(p->Rchild!=NULL)Queue[++rear]=p;/*左結點入隊*/}}}樹與二叉樹第41頁

如圖6-9所表示二叉樹表示表示式：(a+b*(c-d)-e/f)按不一樣次序遍歷此二叉樹，將訪問結點按先后次序排列起來次序是：其先序序列為：-+a*b-cd/ef其中序序列為：a+b*c-d-e/f其后序序列為：abcd-*+ef/-－/fe-dcb*a+圖6-9

表示式(a+b*(c-d)-e/f)二叉樹樹與二叉樹第42頁已知二叉樹(存放結構),能夠確認先序遍歷,中序遍歷,后序遍歷得到序列結果.若先序遍歷(中序遍歷,后序遍歷)得到序列結果,能夠確認二叉樹形式?只有已知序遍歷與中序遍歷,或者中序遍歷與后序遍歷才能能夠確認二叉樹.(見練習p41t27,t28)樹與二叉樹第43頁

“遍歷”是二叉樹最主要基本操作，是各種其它操作基礎，二叉樹許多其它操作都能夠經過遍從來實現。如建立二叉樹存放結構、求二叉樹結點數、求二叉樹深度等。6.3.5

二叉樹遍歷算法應用樹與二叉樹第44頁二叉樹二叉鏈表創建(1)按先序遍歷建立二叉鏈表(p131)按滿二叉樹方式建立二叉鏈表(補充)

在此補充按滿二叉樹方式對結點進行編號建立鏈式二叉樹。對每個結點，輸入i、ch。i：結點編號，按從小到大次序輸入ch：結點內容，假設是字符

在建立過程中借助一個一維數組S[n]，編號為i結點保留在S[i]中。算法實現：樹與二叉樹第45頁#defineMAX_NODE50typedefstructBTNode{chardata;structBTNode*Lchild,*Rchild;}BTNode;BTNode*Create_BTree(void)

/*建立鏈式二叉樹，返回指向根結點指針變量*/{BTNode*T,*p,*s[MAX_NODE];charch;inti,j;while(1){scanf(“%d”,&i);if(i==0)break;/*以編號0作為輸入結束*/else{ch=getchar();樹與二叉樹第46頁p=(BTNode*)malloc(sizeof(BTNode));

p–>data=ch;p–>Lchild=p–>Rchild=NULL;s[i]=p;if(i==1)T=p;else{j=i/2;/*j是i雙親結點編號*/

if(i%2==0)s[j]->Lchild=p;elses[j]->Rchild=p;}}}return(T);}樹與二叉樹第47頁2求二叉樹葉子結點數能夠直接利用先序遍歷二叉樹算法求二叉樹葉子結點數。只要將先序遍歷二叉樹算法中vist()函數簡單地進行修改就能夠。算法實現：#defineMAX_NODE50intsearch_leaves(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,num=0;if(T!=NULL)樹與二叉樹第48頁{stack[++top]=p;while(top>0){p=stack[top--];if(p->Lchild==NULL&&p->Rchild==NULL)num++;if(p->Rchild!=NULL)stack[++top]=p->Rchild;if(p->Lchild!=NULL)stack[++top]=p->Lchild;}}return(num);}樹與二叉樹第49頁//遞歸實現voidTraverse(BTNode*T,int&count){if(T!=NULL)

{if(T->Lchild==null&&T->Rchild==null);count++;

Traverse(T->Lchild,count);

Traverse(T->Rchild,count);

}}樹與二叉樹第50頁

用遍歷方式求二叉樹深度樹與二叉樹第51頁voidTraverse(BTNode*T,int&height){if(T!=NULL)

{if(height>maxH)//maxH是全局變量

maxH=height;

Traverse(T->Lchild,height+1);

Traverse(T->Rchild,height+1);

}}樹與二叉樹第52頁

遍歷二叉樹是按一定規則將樹中結點排列成一個線性序列，即是對非線性結構線性化操作。怎樣找到遍歷過程中動態得到每個結點直接前驅和直接后繼(第一個和最終一個除外)?怎樣保留這些信息?設一棵二叉樹有n個結點，則有n-1條邊(指針連線)

，而n個結點共有2n個指針域(Lchild和Rchild)，顯然有n+1個空閑指針域未用。則能夠利用這些空閑指針域來存放結點直接前驅和直接后繼信息。對結點指針域做以下要求：6.4

線索樹樹與二叉樹第53頁◆若結點有左孩子，則Lchild指向其左孩子，不然，指向其直接前驅；◆

若結點有右孩子，則Rchild指向其右孩子，不然，指向其直接后繼；為防止混同,對結點結構加以改進，增加兩個標志域，如圖6-10所表示。LchildLtagdataRchildRtag圖6-10線索二叉樹結點結構0：Lchild域指示結點左孩子1：Lchild域指示結點前驅Ltag=0：Rchild域指示結點右孩子1：Rchild域指示結點后繼Rtag=樹與二叉樹第54頁

這種結點結構中,指向結點前驅和后繼指針叫做線索；用這種結點結構組成二叉樹存放結構；叫做線索鏈表；按照某種次序遍歷，加上線索二叉樹稱之為線索二叉樹。線索二叉樹結點結構與示例typedefstructBiThrNode{ElemTypedata;structBiTreeNode*Lchild,*Rchild;intLtag,Rtag;}BiThrNode;如圖6-11是二叉樹及對應各種線索樹示例。樹與二叉樹第55頁在線索樹上進行遍歷,只要找到序列中第一個結點,然后依此找到結點后繼直至其后繼為空時止.那么怎樣找結點后繼與前驅?;不一樣遍歷方式找結點后繼與前驅規則也不一樣.

P133:中序遍歷得到線索規則;后序遍歷得到線索規則;

樹與二叉樹第56頁AFHIEGBDC(a)二叉樹

(b)先序線索樹邏輯形式結點序列：ABDCEGFHIAFHIEGBDCNIL(d)后序線索樹邏輯形式結點序列：DBGEHIFCA(c)中序線索樹邏輯形式結點序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL樹與二叉樹第57頁0A00B10C0?1D10E10F0

1G11H11F1?(e)中序線索樹鏈表結構圖6-11線索二叉樹及其存放結構說明：畫線索二叉樹時，實線表示指針，指向其左、右孩子；虛線表示線索，指向其直接前驅或直接后繼。在線索樹上進行遍歷，只要先找到序列中第一個結點，然后就能夠依次找結點直接后繼結點直到后繼為空為止。樹與二叉樹第58頁

怎樣在線索樹中找結點直接后繼?以圖6-11(d)，(e)所表示中序線索樹為例：◆樹中全部葉子結點右鏈都是線索。右鏈直接指示了結點直接后繼，如結點G直接后繼是結點E。◆樹中全部非葉子結點右鏈都是指針。依據中序遍歷規律，非葉子結點直接后繼是遍歷其右子樹時訪問第一個結點，即右子樹中最左下(葉子)結點。如結點C直接后繼：沿右指針找到右子樹根結點F，然后沿左鏈往下直到Ltag=1結點即為C直接后繼結點H。樹與二叉樹第59頁

怎樣在線索樹中找結點直接前驅?若結點Ltag=1，則左鏈是線索，指示其直接前驅；不然，遍歷左子樹時訪問最終一個結點(即沿左子樹中最右往下結點)為其直接前驅結點。對于后序遍歷線索樹中找結點直接后繼比較復雜，可分以下三種情況：

◆若結點是二叉樹根結點：其直接后繼為空；

◆若結點是其父結點左孩子且其父結點沒有右子樹或結點是其父結點右孩子：直接后繼為其父結點；

◆若結點是其父結點左孩子且其父結點有右子樹：直接后繼是對其父結點右子樹按后序遍歷第一個結點。樹與二叉樹第60頁6.4.1

線索化二叉樹

二叉樹線索化指是依照某種遍歷次序使二叉樹成為線索二叉樹過程。線索化過程就是在遍歷過程中修改空指針使其指向直接前驅或直接后繼過程。仿照線性表存放結構，在二叉樹線索鏈表上也添加一個頭結點head，頭結點指針域安排是：

◆Lchild域：指向二叉樹根結點；

◆Rchild域：指向中序遍歷時最終一個結點；

◆二叉樹中序序列中第一個結點Lchild指針域和最終一個結點Rchild指針域均指向頭結點head。樹與二叉樹第61頁

如同為二叉樹建立了一個雙向線索鏈表，對一棵線索二叉樹既可從頭結點也可從最終一個結點開始按尋找直接后繼進行遍歷。顯然，這種遍歷不需要堆棧，如圖6-12所表示。結點類型定義#defineMAX_NODE50typedefenmu{Link,Thread}PointerTag;/*Link=0表示指針，Thread=1表示線索*/typedefstructBiThrNode{ElemTypedata;structBiTreeNode*Lchild,*Rchild;PointerTagLtag,Rtag;}BiThrNode;樹與二叉樹第62頁(a)二叉樹(b)中序線索樹邏輯形式AFHIEGBDCNILNILAFHIEGBDC圖6-12中序線索二叉樹及其存放結構(c)中序線索二叉鏈表0A00B10C01D10E10F0

1G11H11F1Thrt01head樹與二叉樹第63頁1先序線索化二叉樹voidpreorder_Threading(BiThrNode*T){BiThrNode*stack[MAX_NODE];BiThrNode

*last=NULL,*p;inttop=0;if(T!=NULL){stack[++top]=T;while(top>0){p=stack[top--];if(p->Lchild!=NULL)p->Ltag=0;else{p->Ltag=1;p->Lchild!=last;}if(last!=NULL)if(last->Rchild!=NULL)last->Rtag=0;樹與二叉樹第64頁else{last->Rtag=1;last->Rchild!=p;}last=p;if(p->Rchild!=NULL)stack[++top]=p->Rchild

;if(p->Lchild!=NULL)stack[++top]=p->Lchild

;}Last->Rtag=1;/*最終一個結點是葉子結點*/}}樹與二叉樹第65頁2中序線索化二叉樹voidinorder_Threading(BiThrNode*T){BiThrNode*stack[MAX_NODE];BiThrNode

*last=NULL,*p=T;inttop=0;while(p!=NULL||top>0)if(p!=NULL){stack[++top]=p;p=p->Lchild;}else{p=stack[top--];if(p->Lchild!=NULL)p->Ltag=0;else{p->Ltag=1;p->Lchild!=last;}if(last!=NULL)if(last->Rchild!=NULL)last->Rtag=0;樹與二叉樹第66頁else{last->Rtag=1;last->Rchild!=p;}last=p;P=p->Rchild;}last->Rtag=1;/*最終一個結點是葉子結點*/}}樹與二叉樹第67頁6.4.2

線索二叉樹遍歷

在線索二叉樹中，因為有線索存在，在一些情況下能夠方便地找到指定結點在某種遍歷序列中直接前驅或直接后繼。另外，在線索二叉樹上進行某種遍歷比在普通二叉樹上進行這種遍歷要輕易得多，不需要設置堆棧，且算法十分簡練。樹與二叉樹第68頁1先序線索二叉樹先序遍歷voidpreorder_Thread_bt(BiThrNode*T){BiThrNode*p=T;while(p!=NULL){visit(p->data)

;if(p->Ltag==0)p=p->Lchild;elsep=p->Rchild}}樹與二叉樹第69頁2中序線索二叉樹中序遍歷voidinorder_Thread_bt(BiThrNode*T){BiThrNode*p;if(T!=NULL){p=T;while(p->Ltag==0

)p=p->Lchild;/*尋找最左結點*/while(p!=NULL){visit(p->data)

;if(p->Rtag==1)p=p->Rchild;/*經過右線索找到后繼*/else/*不然，右子樹最左結點為后繼*/{p=p->Rchild;

樹與二叉樹第70頁while(p->Ltag==0)p=p->Lchild;}}}}樹與二叉樹第71頁6.5

樹與森林

本節將討論樹存放結構、樹及森林與二叉樹之間相互轉換、樹遍歷等。樹與二叉樹第72頁6.5.1樹存放結構

樹存放結構依據應用不一樣而不一樣。1雙親表示法(次序存放結構)

用一組連續存放空間來存放樹結點，同時在每個結點中附加一個指示器(整數域)

，用以指示雙親結點位置(下標值)。數組元素及數組類型定義以下：#defineMAX_SIZE100typedefstructPTNode{ElemTypedata;intparent;}PTNode;樹與二叉樹第73頁typedefstruct{PTNodeNodes[MAX_SIZE];introot;/*根結點位置*/intnum;/*結點數*/

}Ptree;圖6-13所表示是一棵樹及其雙親表示存放結構。這種存放結構利用了任一結點父結點唯一性質。能夠方便地直接找到任一結點父結點，但求結點子結點時需要掃描整個數組。FGHIRABCDE圖6-13樹雙親存放結構R-10A01B02C03D14E15F36G67H68I69樹與二叉樹第74頁2孩子鏈表表示法

樹中每個結點有多個指針域，每個指針指向其一棵子樹根結點。有兩種結點結構。⑴定長結點結構

指針域數目就是樹度。其特點是：鏈表結構簡單，但指針域浪費顯著。結點結構如圖6-14(a)所表示。在一棵有n個結點，度為k樹中必有n(k-1)+1空指針域。⑵不定長結點結構

樹中每個結點指針域數量不一樣，是該結點度，如圖6-14(b)所表示。沒有多出指針域，但操作不便。樹與二叉樹第75頁圖6-14孩子表示法結點結構datachild1child2

?childk(a)定長結點結構(b)不定長結點結構datakichild1child2

?childki⑶復合鏈表結構(帶雙親孩子鏈表法)

對于樹中每個結點，其孩子結點用帶頭結點單鏈表表示，表結點和頭結點結構如圖6-15所表示。n個結點樹有n個(孩子)單鏈表(葉子結點孩子鏈表為空)，而n個頭結點又組成一個線性表且以次序存放結構表示。datafirstchild(a)頭結點childnext(b)表結點圖6-15孩子鏈表結點結構樹與二叉樹第76頁數據結構類型定義以下：#defineMAX_NODE100typedefstructCTNode{intchild;/*孩子結點編號*/structCTNode*next;}CTNode;/*表結點結構*/typedefstruct{ElemTypedata;CTNode*firstchild;}CTBox;/*頭結點結構*/樹與二叉樹第77頁typedefstruct{CTBoxnodes[MAX_NODE];intr;/*根結點位置*/intn;/*結點數*/}CTree;/*頭結點結構*/圖6-13所表示樹T孩子鏈表表示存放結構如圖6-16所表示。樹與二叉樹第78頁nodes789?

35?

012?

6?

0123456789MAX_NODE-1rnAB?

CD?

E?FG?H?I?┇┇R49圖6-16圖6-13樹T孩子鏈表存放結構樹與二叉樹第79頁3孩子弟兄表示法(二叉樹表示法)

以二叉鏈表作為樹存放結構，其結點形式如圖6-17(a)所表示。兩個指針域：分別指向結點第一個子結點和下一個弟兄結點。結點類型定義以下：typedefstructCSnode{ElemTypedata;structCSnode*firstchild,*nextsibing;}CSNode,*CSTree;圖6-17(b)所表示樹孩子弟兄表示存放結構如圖6-17(c)。樹與二叉樹第80頁圖6-17樹及孩子弟兄存放結構(b)樹

FGRABCDE(c)孩子弟兄存放結構R?A?DC??G?B?F??E?孩子結點弟兄結點firstchilddatanextsibing(a)結點結構樹與二叉樹第81頁6.5.2

森林與二叉樹轉換

因為二叉樹和樹都可用二叉鏈表作為存放結構，對比各自結點結構能夠看出，以二叉鏈表作為媒介能夠導出樹和二叉樹之間一個對應關系。◆

從物理結構來看，樹和二叉樹二叉鏈表是相同，只是對指針邏輯解釋不一樣而已。

◆

從樹二叉鏈表表示定義可知，任何一棵和樹對應二叉樹，其右子樹一定為空。圖6-18直觀地展示了樹和二叉樹之間對應關系。樹與二叉樹第82頁圖6-18樹與二叉樹對應關系二叉樹

CERADBR?A?D??C?B?E?樹

RABCDE對應關系R?A?D??C?B?E??C?B?E?RA?D?存放解釋存放解釋樹與二叉樹第83頁1樹轉換成二叉樹

對于普通樹，能夠方便地轉換成一棵唯一二叉樹與之對應。將樹轉換成二叉樹在“孩子弟兄表示法”中已給出，其詳細步驟是：⑴加虛線。在樹每層按從“左至右”次序在弟兄結點之間加虛線相連。(注意不是堂弟兄)⑵去連線。除最左第一個子結點外，父結點與全部其它子結點連線都去掉。⑶旋轉。將樹順時針旋轉450，原有實線左斜。⑷整型。將旋轉后樹中全部虛線改為實線，并向右斜。該轉換過程如圖6-19所表示。樹與二叉樹第84頁

這么轉換后二叉樹特點是：

◆二叉樹根結點沒有右子樹，只有左子樹；

◆左子結點依然是原來樹中對應結點左子結點，而全部沿右鏈往下右子結點均是原來樹中該結點弟兄結點。圖6-19樹向二叉樹轉換過程(a)普通樹

FGRABCDEFGRABCDE(b)加虛線，去連線后

(C)轉換后二叉樹FGRACDBE樹與二叉樹第85頁2二叉樹轉換成樹

對于一棵轉換后二叉樹，怎樣還原成原來樹?其步驟是：⑴加虛線。若某結點i是其父結點左子樹根結點，則將該結點i右子結點以及沿右子鏈不停地搜索全部右子結點，將全部這些右子結點與i結點父結點之間加虛線相連，如圖6-20(a)所表示。⑵去連線。去掉二叉樹中全部父結點與其右子結點之間連線，如圖6-20(b)所表示。⑶規整化。將圖中各結點按層次排列且將全部虛線變成實線，如圖6-20(c)所表示。樹與二叉樹第86頁圖6-20二叉樹向樹轉換過程(C)還原后樹FGRABCDE(b)去連線后(a)加虛線后FGRACDBECFGRADBE樹與二叉樹第87頁3森林轉換成二叉樹

當普通樹轉換成二叉樹后，二叉樹右子樹必為空。若把森林中第二棵樹(轉換成二叉樹后)根結點作為第一棵樹(二叉樹)根結點弟兄結點，則可導出森林轉換成二叉樹轉換算法以下：設F={T1,T2,?,Tn}是森林，則按以下規則可轉換成一棵二叉樹B=(root，LB，RB)①若n=0，則B是空樹。②若n>0，則二叉樹B根是森林T1根root(T1)，B左子樹LB是B(T11,T12,?,T1m)，其中T11,T12,?,T1m是T1子樹(轉換后)，而其右子樹RB是從森林F’={T2,T3,?,Tn}轉換而成二叉樹。樹與二叉樹第88頁轉換步驟：

①將F={T1,T2,?,Tn}中每棵樹轉換成二叉樹。②按給出森林中樹次序，從最終一棵二叉樹開始，每棵二叉樹作為前一棵二叉樹根結點右子樹，依次類推，則第一棵樹根結點就是轉換后生成二叉樹根結點，如圖6-21所表示。ACBDGMLHK(a)森林圖6-21森林轉換成二叉樹過程(b)森林中每棵樹對應二叉樹ABCDGLKHM(c)森林對應二叉樹ABCDGLKHM樹與二叉樹第89頁4二叉樹轉換成森林

若B=(root，LB，RB)是一棵二叉樹，則能夠將其轉換成由若干棵樹組成森林：F={T1,T2,?,Tn}。轉換算法：①若B是空樹，則F為空。②若B非空，則F中第一棵樹T1根root(T1)就是二叉樹根root，T1中根結點子森林F1是由樹B左子樹LB轉換而成森林；F中除T1外其余樹組成森林F’={T2,T3,?,Tn}是由B右子樹RB轉換得到森林。上述轉換規則是遞歸，能夠寫出其遞歸算法。以下給出詳細還原步驟。樹與二叉樹第90頁①去連線。將二叉樹B根結點與其右子結點以及沿右子結點鏈方向全部右子結點連線全部去掉，得到若干棵孤立二叉樹，每一棵就是原來森林F中樹依次對應二叉樹，如圖6-22(b)所表示。②二叉樹還原。將各棵孤立二叉樹按二叉樹還原為樹方法還原成普通樹，如圖6-22(c)所表示。圖6-22二叉樹還原成森林過程ACBDMGLHK(c)還原成森林(a)二叉樹ABCDGLKHM(b)去連線后ABCDMGLKH樹與二叉樹第91頁6.5.3樹和森林遍歷1樹遍歷

由樹結構定義可知，樹遍歷有二種方法。⑴

先序遍歷：先訪問根結點，然后依次先序遍歷完每棵子樹。如圖6-23樹，先序遍歷次序是：ABCDEFGIJHK⑵

后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結點。如圖6-23樹，后序遍歷次序是：CDBFGIJHEKA樹與二叉樹第92頁說明：◆樹先序遍歷實質上與將樹轉換成二叉樹后對二叉樹先序遍歷相同。◆樹后序遍歷實質上與將樹轉換成二叉樹后對二叉樹中序遍歷相同。ABDCKGJIFHE圖6-23樹樹與二叉樹第93頁2森林遍歷

設F={T1,T2,?,Tn}是森林，對F遍歷有二種方法。⑴先序遍歷：按先序遍歷樹方式依次遍歷F中每棵樹。⑵中序遍歷：按后序遍歷樹方式依次遍歷F中每棵樹。樹與二叉樹第94頁6.6

赫夫曼樹及其應用赫夫曼(Huffman)樹又稱最優樹，是一類帶權路徑長度最短樹，有著廣泛應用。樹與二叉樹第95頁6.6.1最優二叉樹(Huffman樹)1

基本概念①結點路徑：從樹中一個結點到另一個結點之間分支組成這兩個結點之間路徑。②路徑長度：結點路徑上分支數目稱為路徑長度。③樹路徑長度：從樹根到每一個結點路徑長度之和。例圖6-23樹。A到F：結點路徑AEF；路徑長度(即邊數目)2；樹路徑長度：31+52+23=19

樹與二叉樹第96頁④

結點帶權路徑長度：從該結點到樹根結點之間路徑長度與結點權(值)乘積。權(值)：各種開銷、代價、頻度等抽象稱呼。⑤

樹帶權路徑長度：樹中全部葉子結點帶權路徑長度之和，記做：WPL=w1l1+w2l2+?+wnln=∑wili(i=1,2,?,n)其中：n為葉子結點個數；wi為第i個結點權值；

li為第i個結點路徑長度。⑥

Huffman樹：含有n個葉子結點(每個結點權值為wi)二叉樹不止一棵，但在全部這些二叉樹中，必定存在一棵WPL值最小樹，稱這棵樹為Huffman樹(或稱最優樹)。樹與二叉樹第97頁在許多判定問題時，利用Huffman樹能夠得到最正確判斷算法。如圖6-24是權值分別為2、3、6、7，含有4個葉子結點二叉樹，它們帶權路徑長度分別為：(a)WPL=22+32+62+72=36；(b)WPL=21+32+63+73=47；(c)WPL=71+62+23+33=34。其中(c)WPL值最小，能夠證實是Huffman樹。樹與二叉樹第98頁236736726723(a)(b)(c)圖6-24含有相同葉子結點，不一樣帶權路徑長度二叉樹2Huffman樹結構①依據n個權值{w1,w2,?,wn}，結構成n棵二叉樹集合F={T1,T2,?,Tn}，其中每棵二叉樹只有一個權值為wi根結點，沒有左、右子樹；樹與二叉樹第99頁②在F中選取兩棵根結點權值最小樹作為左、右子樹結構一棵新二叉樹，且新二叉樹根結點權值為其左、右子樹根結點權值之和；③在F中刪除這兩棵樹，同時將新得到樹加入F中；④

重復②、③，直到F只含一顆樹為止。結構Huffman樹時，為了規范，要求F={T1,T2,?,Tn}中權值小二叉樹作為新結構二叉樹左子樹，權值大二叉樹作為新結構二叉樹右子樹；在取值相等時，深度小二叉樹作為新結構二叉樹左子樹，深度大二叉樹作為新結構二叉樹右子樹。樹與二叉樹第100頁

圖6-25是權值集合W={8,3,4,6,5,5}結構Huffman樹過程。所結構Huffman樹WPL是：

WPL=62+33+43+82+53+53=79345568第一步5568第二步34768第三步34755108第四步5510634713第六步1111100000855101863471331圖6-25Huffman樹結構過程第五步8551018634713樹與二叉樹第101頁6.6.2

赫夫曼編碼及其算法1Huffman編碼

在電報收發等數據通訊中，常需要將傳送文字轉換成由二進制字符0、1組成字符串來傳輸。為了使收發速度提升，就要求電文編碼要盡可能地短。另外，要設計長短不等編碼，還必須確保任意字符編碼都不是另一個字符編碼前綴，這種編碼稱為前綴編碼。Huffman樹能夠用來結構編碼長度不等且譯碼不產生二義性編碼。設電文中字符集C={c1,c2,?,ci,?,cn}，各個字符出現次數或頻度集W={w1,w2,?,wi,?,wn}。樹與二叉樹第102頁Huffman編碼方法以字符集C作為葉子結點，次數或頻度集W作為結點權值來結構Huffman樹。要求Huffman樹中左分支代表“0”，右分支代表“1”。從根結點到每個葉子結點所經歷路徑分支上“0”或“1”所組成字符串，為該結點所對應編碼，稱之為Huffman編碼。因為每個字符都是葉子結點，不可能出現在根結點到其它字符結點路徑上，所以一個字符Huffman編碼不可能是另一個字符Huffman編碼前綴。樹與二叉樹第103頁若字符集C={a,b,c,d,e,f}所對應權值集合為W={8,3,4,6,5,5}，如圖6-25所表示，則字符a,b,c,d,e,f所對應Huffman編碼分別是：10，010，011，00，110，111。2Huffman編碼算法實現(1)數據結構設計Huffman樹中沒有度為1結點棵有n個葉子結點Huffman樹共有2n-1個結點，則可存放在大小為2n-1一維數組中。實現編碼結點結構如圖6-26所表示。原因：◆

求編碼需從葉子結點出發走一條從葉子到根路徑；樹與二叉樹第104頁◆譯碼需從根結點出發走一條到葉子結點路徑。

結點類型定義：#defineMAX_NODE200/*Max_Node>2n-1

*/

typedefstruct{unsignedintWeight;/*權值域*/unsingedintParent,Lchild,Rchild;}HTNode;WeightParentLchildRchildWeight：權值域；Parent：雙親結點下標Lchild,Rchild：分別標識左、右子樹下標圖6-26Huffman編碼結點結構樹與二叉樹第105頁(2)Huffman樹生成算法實現voidCreate_Huffman(unsignedn,HTNodeHT[],unsignedm)

/*創建一棵葉子結點數為nHuffman樹*/{unsignedintw;intk,j;for(k=1;k<m;k++){if(k<=n){printf(“\nPleaseInputWeight:w=?”);scanf(“%d”,&w);HT[k].weight=w;}