第五章樹和二叉樹PPT課件

1、第五章 樹和二叉樹5.1 樹和二叉樹的概念5.2 樹和二叉樹的抽象數(shù)據(jù)類型定義5.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)5.4 遍歷二叉樹和線索二叉樹5.5 樹和森林5.6 哈夫曼樹及其應(yīng)用 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹和二叉樹樹和二叉樹樹和二叉樹的定義u 樹的定義樹(tree)是n(n0)個結(jié)點的有限集，它或為空樹(n=0)；或為非空樹，對于非空樹T： (1) 有且僅有一個特定的稱為根(Root)的結(jié)點; (2) 除根結(jié)點以外的其余結(jié)點可分為m(m0)個互不相交的有限集T1, T2, , Tm, 其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。5.1 樹

2、和二叉樹的定義樹和二叉樹的定義A只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹5.1 樹和二叉樹的定義樹和二叉樹的定義ABKLEFHMIJDGC嵌套集合表示法A B E K L F C G D H M I J凹入表示法廣義表表示法：(A( B(E(K,L),F), C(G), D(H(M),I,J) )5.1 樹和二叉樹的定義樹和二叉樹的定義u樹的基本術(shù)語l結(jié)點結(jié)點(node)樹中的一個獨立單元，包括數(shù)據(jù)元素及若干指向其子樹的分支l結(jié)點的度結(jié)點的度(degree)結(jié)點擁有的子樹數(shù)l樹的度樹的度一棵樹中最大的結(jié)點度數(shù)l葉子葉子(leaf)度為0的結(jié)點l非終端結(jié)點非終端結(jié)點-度不為0的結(jié)

3、點（分支結(jié)點）l孩子孩子(child)結(jié)點子樹的根稱為該結(jié)點的孩子l雙親雙親(parents)孩子結(jié)點的上層結(jié)點叫該結(jié)點的雙親l兄弟兄弟(sibling)同一雙親的孩子l祖先祖先從根到該結(jié)點所經(jīng)分支上的所有結(jié)點l子孫子孫以某結(jié)點為根的樹中任一結(jié)點都稱為該結(jié)點的子孫5.1 樹和二叉樹的定義樹和二叉樹的定義ABCDEFGHIJKLMl堂兄弟堂兄弟其雙親在同一層次的結(jié)點稱為堂兄弟l結(jié)點的層次結(jié)點的層次(level)從根結(jié)點算起，根為第一層，它的孩子為第二層l樹的深度樹的深度(depth)樹中結(jié)點的最大層次數(shù)l有序樹有序樹樹中結(jié)點的各子樹看成從左到右是有序的（不能互換）l無序樹無序樹結(jié)點各子樹可互換位

4、置l森林森林(forest)m(m0)棵互不相交的樹的集合5.1 樹和二叉樹的定義樹和二叉樹的定義ABCDEFGHIJKLMABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先5.1 樹和二叉樹的定義樹和二叉樹的定義u二叉樹定義二叉樹(Binary Tree) 是n(n0)個結(jié)點所構(gòu)成的集合，它或為空樹(n = 0)；或為非空樹，對于非空樹T

5、：(1) 有且僅有一個稱之為根的結(jié)點；(2) 除根結(jié)點以外的其余結(jié)點分為兩個互不相交的子集T1和T2，分別稱為T的左子樹和右子樹，且T1和T2本身又都是二叉樹。二叉樹基本特點：結(jié)點的度小于等于2有序樹（子樹有序，不能顛倒）二叉樹的五種不同形態(tài)5.1 樹和二叉樹的定義樹和二叉樹的定義u樹的抽象數(shù)據(jù)類型定義ADT Tree 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(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 剩下的數(shù)據(jù)元素，可分為m(m0)個互不相

6、交的有限集T1,T2,Tm個劃分，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)基本操作P： InitTree(&T); / 構(gòu)造空樹T DestoryTree(&T); / 銷毀樹T CreateTree(&T,definition); / 按definition構(gòu)造樹T樹和二叉樹的抽象數(shù)據(jù)類型定義5.2 樹和二叉樹的抽象數(shù)據(jù)類型定義樹和二叉樹的抽象數(shù)據(jù)類型定義ClearTree(&T); / 將樹T清為空樹TreeEmpty(T); / 若樹T為空，則返回true, 否則false;TreeDepth(T); /獲得樹T的深度Root(T);

7、/獲得樹T的根Value(T, cur_e); /獲得樹T中cur_e結(jié)點的值A(chǔ)ssign(T, cur_e,value); / 把結(jié)點cur_e賦值為valueParent(T, cur_e); /獲得cur_e的雙親結(jié)點LeftChild(T,cur_e); /獲得cur_e的最左孩子結(jié)點RightSibling(T,cur_e); /獲得cur_e的右兄弟結(jié)點InsertChild(&T, p, i, c); / 插入c為樹T中p結(jié)點的第i棵子樹DeleteChild(&T, p, i); / 刪除樹T中p結(jié)點的第i棵子樹TraverseTree(T); / 按某種次序?qū)?/p>

8、樹T的每個結(jié)點訪問一次 ADT Tree5.2 樹和二叉樹的抽象數(shù)據(jù)類型定義樹和二叉樹的抽象數(shù)據(jù)類型定義u二叉樹的抽象數(shù)據(jù)類型定義ADT BinaryTree 數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(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)系HlH; 若Dr ,則Dr中存在唯一的元素xr,H,且存在 Dr上的關(guān)系HrH;

9、H=, ,Hl, Hr;(4) (Dl, Hl)是一棵符合本定義的二叉樹,稱為根的左子樹, (Dr, Hr )是一棵符合本定義的二叉樹,稱為根的右子樹。5.2 樹和二叉樹的抽象數(shù)據(jù)類型定義樹和二叉樹的抽象數(shù)據(jù)類型定義注意:表示元素與集合的從屬關(guān)系； 代表一個集合是另外一個集合的子集。 H、 Hl、 Hr都是關(guān)系的集合?；静僮鱌：InitBiTree( &T ); / 構(gòu)造空二叉樹TDestroyBiTree( &T );/銷毀二叉樹TCreateBiTree(&T, definition)；/按definition構(gòu)造二叉樹TPreOrderTraverse( T )

10、; /先序遍歷T。InOrderTraverse( T ); /中序遍歷T。PostOrderTraverse( T ); /后序遍歷T。 ADT BinaryTree;5.2 樹和二叉樹的抽象數(shù)據(jù)類型定義樹和二叉樹的抽象數(shù)據(jù)類型定義二叉樹的性質(zhì)l性質(zhì)1：(1)i i-1在二叉樹的第i層上至多有2 個結(jié)點l性質(zhì)2：深度為k的二叉樹至多有 個結(jié)點(k1)12 kl性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1證明: 設(shè)1度結(jié)點數(shù)為n1, 總結(jié)點數(shù)為n, 分支數(shù)為B則 n = n0 + n1 + n2; n = B + 1;/ 結(jié)點數(shù)比分支數(shù)多1又 B

11、= n1 + 2n2 n = n1 + 2n2 + 1 = n0 + n1 + n2 n0 = n2 + 15.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)二叉樹的性質(zhì)和存儲結(jié)構(gòu)幾種特殊形式的二叉樹滿二叉樹定義：滿二叉樹。1個結(jié)點的二叉樹稱為k一棵深度為k且有2特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)完全二叉樹定義：深度為k，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。特點 葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)(最深的兩層) 對任一結(jié)點，若其右分支下子孫的最大層次為i，則其左分支下子孫的最大層次必為i或i+1（左邊不比右邊小）l性質(zhì)4：1nlog叉樹

12、的深度為具有n個結(jié)點的完全二25.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)二叉樹的性質(zhì)和存儲結(jié)構(gòu)不大于不大于x的最大整數(shù)的最大整數(shù) x123114589121367101415滿二叉樹123114589126710完全二叉樹1234567123456非完全二叉樹非完全二叉樹5.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)二叉樹的性質(zhì)和存儲結(jié)構(gòu)l 性質(zhì)5：如果一棵完全二叉樹有n個結(jié)點，且結(jié)點按層序編號，則對任一結(jié)點i(1in)，有： (1) 如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i1，則其雙親是i/2 (2) 如果2in，則結(jié)點i無左孩子；如果2in，則其左孩子是2i (3) 如果2i+1n，則結(jié)點i無右孩子；如果2i

13、+1n，則其右孩子是2i+15.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)二叉樹的性質(zhì)和存儲結(jié)構(gòu)123114589126710完全二叉樹注意注意:雙親節(jié)點雙親節(jié)點序號序號為為x，如果存在，左孩子節(jié)點序號，如果存在，左孩子節(jié)點序號2x，右孩子節(jié)點序號為，右孩子節(jié)點序號為2x+1u二叉樹的存儲結(jié)構(gòu)l順序存儲結(jié)構(gòu)實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素特點： 結(jié)點間關(guān)系蘊含在其存儲位置中 浪費空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 115.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)二叉樹的性質(zhì)和存儲結(jié)構(gòu)l鏈式存儲結(jié)構(gòu)二叉鏈

14、表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree;lchild data rchild ABCDEFG在n個結(jié)點的二叉鏈表中，有n+1個空指針域 AB C D E F G5.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)二叉樹的性質(zhì)和存儲結(jié)構(gòu)n n0 0 = n = n2 2 + 1 + 1練習：證明結(jié)論 三叉鏈表typedef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild, *parent; TriT

15、Node,*TriTree;lchild data parent rchildABCDEFG A B C D E F G5.3 二叉樹的性質(zhì)和存儲結(jié)構(gòu)二叉樹的性質(zhì)和存儲結(jié)構(gòu)遍歷二叉樹和線索二叉樹遍歷定義指按某條搜索路線遍訪每個結(jié)點且不重復(fù)(又稱周游)。u遍歷二叉樹 遍歷二叉樹的方法 :l先序遍歷:先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹l中序遍歷:先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹l后序遍歷:先后序遍歷左、右子樹，然后訪問根結(jié)點DLRDLR、LDR、LRDDRL、RDL、RLD5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹ADBCD L RAD L RD L RBD

16、CD L R先序遍歷序列：A B D C先序遍歷:5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹說出先序順序？ADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:B5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f前綴表示中綴表示后綴表示5.4 遍歷二叉樹和線

17、索二叉樹遍歷二叉樹和線索二叉樹若二叉樹中各結(jié)點的值均不相同，則：u已知前序序列和中序序列，二叉樹可以唯一確定；u已知后序序列和中序序列，二叉樹可以唯一確定；u已知前序序列和后序序列，二叉樹不一定能唯一確定。 5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹例:已知一棵二叉樹的 中序序列： BDCEAFHG 后序序列： DECBHGFA 請畫出這棵二叉樹。（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹注意：后序序列的最后一個一定是根，子樹也一樣注意：后序序列的最后一個一定是根，子樹也一樣 確定根

18、后，可以依據(jù)確定根后，可以依據(jù)中序序列中序序列確定左右子樹確定左右子樹l算法 遞歸算法void PreOrder(BiTree T) if (T!=NULL) coutdata; PreOrder(T-lchild); PreOrder(T-rchild); 先序遍歷void InOrder(BiTree T) if (T!=NULL) InOrder(Tlchild); coutdata; InOrder(T-rchild); 中序遍歷void PostOrder(BiTree T) if (T!=NULL) PostOrder(T-lchild); PostOrder(T-rchild);

19、 coutdata; 后序遍歷5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹void PreOrder(BiTree T) if (T!=NULL) cout data; PreOrder(T-lchild); PreOrder(T-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBPrint (B);pre(T L);BTAPrint (A);pre(T L);ATDPrint (D);pre(T L);DTCPrint (C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空

20、返回pre(T R);先序序列:A B D C5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 中序非遞歸算法void InOrder(BiTree T) int i=0; BiTree p, sM; / i和sM構(gòu)成一個棧，M為某常數(shù) p = T; / 根結(jié)點 do while ( p != NULL ) / 沿左子樹找到第一個空結(jié)點，并記錄下訪問過的結(jié)點 si+ = p; / 入棧 push(s,p) p=p-lchild; if (i0) / 棧不空 p = s-i; / 出棧 pop(s,p) coutdata; / 訪問該結(jié)點 p=p-rchild; / 找該結(jié)點的右子樹的根 w

21、hile( i0 | p != NULL ); / 棧不空 或 還有末處理的結(jié)點5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 非遞歸算法執(zhí)行過程ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：C(4)5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹pABCDEFGiP-A訪問：C B(5)ABCDEFGiP-AP-D訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：C Bp(7)ABCDEFGiP-AP-D訪問：C B Ep(8)5.4 遍歷二叉樹和線索二叉樹遍歷二叉

22、樹和線索二叉樹ABCDEFGiP-AP-DP-G訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：C B E Gp(10)5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹ABCDEFGiP-A訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：C B E G D F Ap(14)ABCDEFGi訪問：C B E G D F Ap=NULL(15)5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹l 遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的

23、二叉鏈表，已知先序序列為： A B C # # D E # G # # F # # #ABCDEFG A B C D E F G void CreateBiTree( BiTree &T) cin ch; if (ch=#) T=NULL; else T= new BiTNode; T-data=ch; CreateBiTree(T-lchild); CreateBiTree (T-rchild); 5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹注：如不給出空節(jié)點，則不能確定二叉樹計算二叉樹的深度。(1) 如果是空樹，則深度為0；(2) 否則，遞歸計算左子樹的深度記為m， 遞歸計

24、算右子樹的深度記為n， 二叉樹的深度則為m與n的較大者加1。 5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹int Depth( BiTree T ) int m,n; if (T=NULL) return 0; / 如果是空樹，則深度為0 else m=Depth(T-lchild); /遞歸計算左子樹的深度記為m n =Depth(T-rchild); /遞歸計算右子樹的深度記為nif ( m n ) return m+1; /二叉樹的深度則為m與n的較大者加1else return n+1; 5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹計算二叉樹中結(jié)點的個數(shù)。(1)如果是空

25、樹，則結(jié)點個數(shù)為0；(2)非空，結(jié)點個數(shù)為:左子樹的結(jié)點個數(shù)+右子樹的結(jié)點個數(shù)+1int NodeCount(BiTree T) if (!T) return 0; return NodeCount(T-lchild)+NodeCount(T-rchild)+1; 5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹計算二叉樹中葉子結(jié)點的個數(shù)。(1)如果是空樹，則葉子結(jié)點個數(shù)為0；(2)如果是葉子結(jié)點，則葉子結(jié)點數(shù)為1；(3)否則，為左子樹的葉子結(jié)點個數(shù)+右子樹的葉子結(jié)點個數(shù)。int LeadCount(BiTree T) if( !T ) return 0; /如果是空樹返回0 if ( !

26、T-lchild & !T-rchild ) return 1; /葉子結(jié)點返回1 return LeafCount(T-lchild) + LeafCount(T-rchild);5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹u 線索二叉樹l定義：前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為前驅(qū)與后繼。線索：指向前驅(qū)或后繼結(jié)點的指針稱為線索。線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫線索二叉樹。線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫線索化。5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹u 線索二叉樹l實現(xiàn)1增加兩個指針域，一個指

27、向前驅(qū)，一個指向后續(xù)5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹lchild pre data next rchild特點：特點： 每個節(jié)點增加存儲空間占用量為每個節(jié)點增加存儲空間占用量為2 2* *sizeofsizeof(pre),(pre),一般為一般為8 8個字節(jié)個字節(jié) 算法設(shè)計容易算法設(shè)計容易u 線索二叉樹l實現(xiàn)2在有n個結(jié)點的二叉鏈表中必定有n+1個空鏈域在線索二叉樹的結(jié)點中增加兩個標志域 ltag: 若 ltag =0, lchild 域指向左孩子；若 ltag=1, lchild域指向其前驅(qū) rtag: 若 rtag =0, rchild 域指向右孩子；若 rtag=1

28、, rchild域指向其后繼5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹lchild ltag data rtag rchild注注: :加上兩個標志后，實現(xiàn)空指加上兩個標志后，實現(xiàn)空指針域的充分利用，輔助二叉樹針域的充分利用，輔助二叉樹遍歷，標志占用空間最小為遍歷，標志占用空間最小為0 0結(jié)點定義：typedef struct BiThrNode TElemType data; int ltag, rtag; struct BiThrNode *lchild, *rchild; BiThrNode, *BiThrTree;lchild ltag data rtag rchildlta

29、g: 若 ltag=0, lchild域指向左孩子； 若 ltag=1, lchild域指向其前驅(qū)。rtag: 若 rtag=0, rchild域指向右孩子； 若 rtag=1, rchild域指向其后繼。 5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹ABCDE A B D C ET先序序列：ABCDE先序線索二叉樹00001111 11ABCDENULL5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹先序線索化：先序線索化： 指針指針 線索線索線索化ABCDE A B D C ET中序序列：BCAED中序線索二叉樹0000111111ABCDENULLNULL5.4 遍歷二叉樹和

30、線索二叉樹遍歷二叉樹和線索二叉樹中序中序線索化：線索化： 指針指針 線索線索線索化ABCDE A B D C ET后序序列：CBEDA后序線索二叉樹0000111111ABCDENULL5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹后后序線索化：序線索化： 指針指針 線索線索線索化ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹 0 1頭結(jié)點：ltag=0, lchild指向根結(jié)點rtag=1, rchild指向遍歷序列中最后一個結(jié)點遍歷序列中第一個結(jié)點的lchild域和最后一個結(jié)點的rchild域都指向頭結(jié)點 A B

31、 D C ET中序序列：BCAED中序線索二叉樹00001111115.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹加頭結(jié)點在中序線索二叉樹中找結(jié)點后繼的方法：（1）若rtag=1, 則rchild域直接指向其后繼（2）若rtag=0, 則結(jié)點的后繼應(yīng)是其右子樹的左鏈尾(ltag=1)的結(jié)點（即中序遍歷右子樹的第一個節(jié)點）在中序線索二叉樹中找結(jié)點前驅(qū)的方法：（1）若ltag=1, 則lchild域直接指向其前驅(qū)（2）若ltag=0, 則結(jié)點的前驅(qū)應(yīng)是其左子樹的右鏈尾(rtag=1)的結(jié)點（即中序遍歷左子樹的最后一個節(jié)點）ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1

32、 t中序序列：BCAED帶頭結(jié)點的中序線索二叉樹 0 15.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹查找后繼和前驅(qū)l 算法 遍歷中序線索二叉樹void InOrderTraverse_Thr(BiThrTree T) BiThrNode *p; p=T-lchild; while ( p!= T ) while( p-ltag=0 ) p = p-lchild; cout data; while( (p-rtag =1)&(p-rchild!=T) p=p-rchild; cout data; p=p-rchild; 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1

33、T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹 0 15.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹中序的訪問規(guī)則：一旦訪問了一個節(jié)點，則下一次訪問一定是右子樹中序的訪問規(guī)則：一旦訪問了一個節(jié)點，則下一次訪問一定是右子樹不用棧和遞歸，實現(xiàn)了二叉樹遍歷不用棧和遞歸，實現(xiàn)了二叉樹遍歷 按中序線索化二叉樹(遞歸算法)ABCDE輸出: B C A E D A B D C Ethrt 0 11111110000pre：上次訪問節(jié)點的指針；p：本次訪問節(jié)點的指針；/遞歸方式線索化一個子遞歸方式線索化一個子樹樹void InThreading( BiThrTree p ) if ( p ) InThr

34、eading( p-lchild ); if ( !p-lchild ) /左孩子為空 p-lagt=1; p-lchild = pre; if ( !pre-rchild) /右孩子為空 pre-tag=1; pre-rchild = p; pre = p; InThreading( p-rchild); t5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 按中序線索化二叉樹(遞歸算法)ABCDE輸出: B C A E D A B D C Ethrt 0 11111110000pre：上次訪問節(jié)點的指針； /將T線索化為一個帶頭結(jié)點的二叉樹thrtStatus InOrderThread

35、ing( BiThrTree &thrt, BiThrTree T ) if ( !(thrt=new BiThrNode) / 建頭結(jié)點return OVERFLOW; thrt-ltag = 0; thrt-rtag = 1; thrt-rchild = thrt; if( !T ) /T為空 thrt-lchild = thrt; else thrt-lchild = T; pre = thrt; InThreading(T); pre-rchild = thrt; pre-rtag = 1; thrt-rchild = pre; return OK;t5.4 遍歷二叉樹和線索二

36、叉樹遍歷二叉樹和線索二叉樹 按中序線索化二叉樹(非遞歸算法)BiThrTree InOrderThread(BiThrTree bt) /思路：在中序遍歷過程中線索化 BiThrTree p,pre,sM,t; int i=0; t=new BiThrNode; t-ltag=0; t-rtag=1; t-rchild=t; if (bt=NULL) t-lchild=t; else t-lchild=bt; pre=t; p=bt; / pre用作指向前驅(qū)結(jié)點 do while( p!=NULL) si+=p; p=p-lchild; if( i0 ) p=s-i; / cout data;

37、 if( p-lchild=NULL) p-ltag=1; p-lchild=pre; if(pre-rchild = NULL) pre-rtag=1; pre-rchild=p; pre=p; p=p-rchild; while( i0 | p!=NULL); pre-rchild=t; pre-rtag=1; t-rchild=pre; /最后設(shè)置頭結(jié)點和最后訪問節(jié)點 return(t);5.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹u樹的存儲結(jié)構(gòu)l雙親表示法實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域： 數(shù)據(jù)域:存放結(jié)點本身信息 雙親域:指示本結(jié)點的雙親結(jié)點在數(shù)組中位置特點：

38、找雙親容易，找孩子難typedef struct node ElemType data; int parent; / 雙親位置 PTNode; / 結(jié)點結(jié)構(gòu)typedef struct PTNode nodesM; int n; PTree; / 樹結(jié)構(gòu)5.5 樹和森林樹和森林abcdefhgiacdefghib012235551096012345789dataparent0號單元不用或存結(jié)點個數(shù)如何找孩子結(jié)點樹的雙親表示法5.5 樹和森林樹和森林l孩子表示法多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根 結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度D 結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度

39、d孩子鏈表：每個結(jié)點的孩子結(jié)點信息用單鏈表存儲，再用含n個元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈表data child1 child2 . childDdata degree child1 child2 . childd5.5 樹和森林樹和森林孩子結(jié)點：typedef struct node int child; /該結(jié)點在表頭數(shù)組中下標 struct node *next; /指向下一孩子結(jié)點 *ChildPtr;結(jié)點信息：typedef struct tnode ElemType data; /數(shù)據(jù)域 ChildPtr fc; /指向第一個孩子結(jié)點 CTBox;樹： typedef struct C

40、TBox nodesM;int n, r; / 結(jié)點數(shù)和根的位置 CTree;5.5 樹和森林樹和森林abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點樹的孩子鏈表表示法5.5 樹和森林樹和森林 帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi樹的帶雙親的孩子鏈表表示法5.5 樹和森林樹和森林l孩子兄弟表示法（二叉樹表示法）實現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點特點操作容易破壞

41、了樹的層typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;abcdefhgi a b c d e f g h i5.5 樹和森林樹和森林樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹 A B C D E A B C D E A B C D E 對應(yīng)存儲存儲解釋解釋5.5 樹和森林樹和森林理解成樹理解成二叉樹存儲結(jié)構(gòu)樹和二叉樹的相互轉(zhuǎn)換 樹轉(zhuǎn)換成二叉樹后，可以利用二叉樹的某些性質(zhì)進行算法設(shè)計。5.5 樹和森林樹和森林l 將樹轉(zhuǎn)換成二叉樹 加線：在兄弟之間加一連線

42、抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系 旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空5.5 樹和森林樹和森林l 將二叉樹轉(zhuǎn)換成樹 加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來 抹線：抹掉原二叉樹中雙親與右孩子之間的連線 調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI5.5 樹和森林樹和森林l森林轉(zhuǎn)換成二叉樹

43、將各棵樹分別轉(zhuǎn)換成二叉樹 將每棵樹的根結(jié)點用線相連 以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ5.5 樹和森林樹和森林l 二叉樹轉(zhuǎn)換成森林 抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹 還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ5.5 樹和森林樹和森林u樹的遍歷l遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所

44、有結(jié)點的一個線性排列l(wèi)常用方法 先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹 后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點5.5 樹和森林樹和森林ABCDEFGHIJKLMNO先根(序)遍歷：ABE F I GCDHJ KL NOM樹的遍歷:5.5 樹和森林樹和森林先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹相當于與二叉樹的什么訪問？相當于與二叉樹的什么訪問？ABCDEFGHIJKLMNO后根(序)遍歷：E I F G B C J K N O L M H D A樹的遍歷:5.5 樹和森林樹和森林先依次后根遍歷每棵子樹，然后訪問根結(jié)點相當于與二叉樹的什么訪問？相當于

45、與二叉樹的什么訪問？u森林的遍歷l 先序遍歷森林: 若森林非空;(1)訪問森林中第一棵樹的根結(jié)點;(2)先序遍歷第一棵樹中根結(jié)點的子樹森林;(3)先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林;5.5 樹和森林樹和森林注：子樹森林就是一棵樹去掉根節(jié)點后形成的森林先序遍歷森林：ABCDE F GHI J相當于先序遍歷森林對應(yīng)的二叉樹中序遍歷森林：BCDA F E H J I G5.5 樹和森林樹和森林u森林的遍歷l 中序遍歷森林: 若森林非空;(1)中序遍歷森林中第一棵樹的根結(jié)點的子樹森林;(2)訪問第一棵樹的根結(jié)點;(3)中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林;注：相當于中序遍歷森林對應(yīng)的二叉

46、樹對于森林來說，由于沒有根節(jié)點，因此利用森林對應(yīng)的二叉樹確定遍歷順序名字更合適哈夫曼樹及其應(yīng)用u哈夫曼樹(Huffman)帶權(quán)路徑長度最短的樹l定義路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的路徑路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和結(jié)點到根的路徑長度權(quán)值其中：記作：kknkkklwlwwpl1Huffman樹：設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫哈夫曼樹5.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用例 有4個結(jié)點，權(quán)值分別為7，5

47、，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL15.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用，4nl構(gòu)造Huffman樹的方法Huffman算法n 構(gòu)造Huffman樹步驟 根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令其權(quán)值為wj 在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和 在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森

48、林中 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹5.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d4611185.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487152958113581923422914871529581005.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用n Huffman算法實現(xiàn) 一棵有n個葉子結(jié)點的Huffman樹有2n-1個結(jié)點 采用順序存儲結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組 結(jié)點類型定義typedef struct int weig