天津科技大學(xué)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹課件

1、6.1 樹的定義和基本術(shù)語6.2 二叉樹 6.2.1 二叉樹的定義 6.2.2 二叉樹的性質(zhì) 6.2.3 二叉樹的存儲結(jié)構(gòu)6.3 遍歷二叉樹和線索二叉樹 6.3.1 遍歷二叉樹 6.3.2 線索二叉樹 6.4 樹和森林 6.4.1 樹的存儲結(jié)構(gòu) 6.4.2 森林與二叉樹的轉(zhuǎn)換 6.4.3 樹和森林的遍歷6.6 赫夫曼樹及其應(yīng)用 6.6.1 最優(yōu)二叉樹（赫夫曼樹） 6.6.2 赫夫曼編碼是一類重要的, 是以定義的。如家譜、行政組織機構(gòu)等。源程序的語法結(jié)構(gòu)等。ABCDEFGHIJA(a) (b) (c)樹的例子:6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語：n(n0)個結(jié)點組成的有限集合。若n=0

2、，則為；若n0，則滿足如下兩個條件：(1)有且僅有一個特定的；(2)當n1時，根結(jié)點以外的其它結(jié)點可分為m(m0) 個互不相交的有限集合T1, T2, Tm，其中每個集合本身又是一棵樹，稱其為根的。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。ABCDEFGHIJ(A(B(E(K,L),F),C(G),D(H(M),I,J)嵌套括號表示法 I JFKLGMCCDBEA嵌套集合凹入表樹形表示樹的表示方法：樹的表示方法：ABCDEFGHIJKLMABCDEFGHIJKLM 構(gòu)造空樹T。 求樹T的根結(jié)點。 求樹T中值為x的結(jié)點的雙親。 求樹T中值為x的結(jié)點的第i個孩子。樹T中將值

3、為x的結(jié)點作為值為y的結(jié)點的第i個孩子插入到樹中。刪除值為x的結(jié)點的第i個孩子。 遍歷或訪問樹T。由n(n0)個結(jié)點構(gòu)成的有限集合，此集合或者為空集，或者由一個根結(jié)點及兩棵互不相交的左、右子樹組成，并且左右子樹都是二叉樹。每個結(jié)點最多有兩個孩子，即不存在度大于2的結(jié)點，有序樹，其子樹的順序不能顛倒，即使只有一棵子樹也要區(qū)分其是左子樹還是右子樹。 操作算法簡單，且任何樹都可與二叉樹 相互轉(zhuǎn)換，解決了樹的存儲結(jié)構(gòu)及其運算中存在的復(fù)雜性。(a)空二叉樹(b)僅有根結(jié)點的二叉樹(c)右子樹為空的二叉樹(d)左子樹為空的二叉樹 (e)根和左右子樹圖：二叉樹的5種形式注：圖(c) 和圖(d)是不同的兩棵二

4、叉樹。AABABACB構(gòu)造空二叉樹T。 銷毀二叉樹T。 求T的根結(jié)點。求T中值為e的結(jié)點的雙親。求T中值為e的結(jié)點的左/右孩子。 求T中值為e的結(jié)點的左/右兄弟。 遍歷二叉樹T。 在T中，將值為y的結(jié)點作為值為x的結(jié)點的左/右孩子插入。 在T中，刪除值為x的結(jié)點的左/右孩子。性質(zhì)性質(zhì)1：采用歸納法證明： i=1時，只有一個根結(jié)點，2i-1=20 =1,命題成立。 現(xiàn)假定對所多的 j，1ji，命題成立，即第j層上至多有2j-1個結(jié)點。 由假設(shè)可知，第i1層上至多有2i-2個結(jié)點。 由于二叉樹每個結(jié)點的度最大為2，所以在第i層上最大結(jié)點數(shù)為第i1層上最大結(jié)點數(shù)的二倍，即22i-22i-1。命題得到

5、證明。性質(zhì)性質(zhì)2：性質(zhì)性質(zhì)3： kikiii11k1122)(層上的最大結(jié)點數(shù)第設(shè)二叉樹中度為1的結(jié)點數(shù)為n1，二叉樹中總結(jié)點數(shù)為N。因為二叉樹中所有結(jié)點均小于或等于2，所以：Nn0n1n2而二叉樹中的分支數(shù)，除根結(jié)點外，其余結(jié)點都有一個進入分支，設(shè)B為二叉樹中的分支總數(shù)，則有：NB1。由于這些分支都是由度為1和2的結(jié)點射出的，所以有：Bn1+2*n2 NB1n12n21從而得到：n0+n1+n2=n1+2*n2+1n0n2+1兩種特殊形態(tài)的二叉樹：深度為k且具有2k-1個結(jié)點的二叉樹。滿二叉樹結(jié)點：從根結(jié)點開始，自上而下、從左至右的順序。如果一棵具有n個結(jié)點且深度為k的二叉樹，其各結(jié)點都與深

6、度為k的滿二叉樹中編號為1 n的結(jié)點一一對應(yīng)的二叉樹。：(1)所有的葉子結(jié)點都出現(xiàn)在第k層或k-1層。(2)對任一結(jié)點，若其右子樹的最大層次為l，則其左子樹的最大層次為l或l1。滿二叉樹的葉子結(jié)點全部在最底層，而完全二叉樹的葉子結(jié)點可以分布在最下面兩層。(a)完全二叉樹(b)非完全二叉樹(c)非完全二叉樹圖:特殊形態(tài)的二叉樹圖:滿二叉樹245367124536124537123671性質(zhì)4：。假設(shè)此二叉樹的深度為k，則該二叉樹的前k-1層為滿二叉樹，共有2k-1-1個結(jié)點；而該二叉樹有k層，第k層至少有1個結(jié)點，最多有2k-1個結(jié)點。因此有：(2k-1-1)+1n(2k-1-1)+2k-1，即

7、 2k-1n2k-1，即。 2k-1n2k，同時取對數(shù)得： k-1log2ndata=c; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK; /先序遍歷Status PreOrderTraverse(BiTree T, Status (*Visit)(BiTree t)if(T) if(*Visit)(T) /訪問結(jié)點if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit)return OK; return ERROR; else retur

8、n OK;/中序遍歷Status InOrderTraverse(BiTree T, Status (*Visit)(BiTree t)if(T) if(InOrderTraverse(T-lchild, Visit) if(*Visit)(T) if(InOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK;/后序遍歷Status PostOrderTraverse(BiTree T, Status (*Visit)(BiTree e) if(T) if(PostOrderTraverse(T-lchil

9、d,Visit) if(PostOrderTraverse(T-rchild,Visit) if(*Visit)(T) /訪問結(jié)點return OK; return ERROR; else return OK;void PreOrderNRTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree p,s100; int top=0; /top為棧頂指針為棧頂指針 p=T; while( p | top0 ) while(p) (*Visit)(p); stop+=p; p=p-lchild; p=s-top; p=p-rchild; void In

10、OrderNRTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree p,s100; /s為一個棧 int top=0; p=T; while( p | top0 ) while(p) stop+=p; p=p-lchild; p=s-top; (*Visit)(p); p=p-rchild; void PostOrderNRTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree p,s1100; /s1棧存放結(jié)點 int b,top=0,s2100;/s2棧存放進棧標志 p=T; do while

11、(p) s1top = p; s2top+ = 0; /第一次進棧標志為0 p=p-lchild; if(top0) b=s2-top; p=s1top; if(b=0) s1top=p;s2top+=1; /第二次進棧標志為1 p=p-rchild; else (*Visit)(p); p=NULL; while(top0);/先序非遞歸遍歷二叉樹先序非遞歸遍歷二叉樹Status PreOrderNoRecursionTraverse(BiTree T, Status (*Visit)(BiTree t) BiTree stackMaxSize,p; int top; if(T) top=0

12、; /根結(jié)點入棧根結(jié)點入棧 stacktop+=T; while(top0) /棧不為空時循環(huán)棧不為空時循環(huán) p=stack-top;/退棧并訪問該結(jié)點退棧并訪問該結(jié)點 (*Visit)(p); if(p-rchild)/右孩子入棧右孩子入棧stacktop+=p-rchild; if(p-lchild)/左孩子入棧左孩子入棧stacktop+=p-lchild; return OK; 當以二叉鏈表作為存儲結(jié)構(gòu)時,只能找到結(jié)點的左右孩子的信息,而不能在結(jié)點的任一序列的前驅(qū)與后繼信息,這種信息只有在遍歷的動態(tài)過程中才能得到,為了能保存所需的信息,可增加標志域;其中: 0 lchild 域指示結(jié)點

13、的左孩子 ltag=ltag= 1 lchild 域指示結(jié)點的前驅(qū) 0 rchild 域指示結(jié)點的右孩子 rtag=rtag= 1 rchild 域指示結(jié)點的后驅(qū) 以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu),叫做,其中指向結(jié)點前驅(qū)與后繼的指針叫做線索.加上線索的二叉樹稱之為.rchildrtagdataltaglchild/-二叉樹的二叉線索存儲表示-typedef enumLink,ThreadPointerTag; /Link:指針,Thread:線索typedef struct BiThrNode TElemType data; struct BiTreeNode *lchild,*r

14、child; PointerTag LTag, Rtag;BiTreeNode,*BiThrTree; 一般地，在二叉樹的線索鏈表上添加一個頭結(jié)點,令其lchild域的指針指向二叉樹的根結(jié)點,其rchild域的指針指向中序遍歷時訪問的最后一個結(jié)點;同時,令二叉樹中序序列中的第一個結(jié)點lchild域指針和最后一個結(jié)點rchild域的指針均指向頭結(jié)點;就像為二叉樹建立了一個雙向線索鏈表。Status InorderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType)/T指向頭結(jié)點,頭結(jié)點的左鏈lchild指向根結(jié)點/中序遍歷二叉線索樹T的非遞歸算法

15、,對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit P=Tlchild; while(p!=T) while(p LTag = Link) p=plchild; if(!Visit(p data) return ERROR; while(p RTag = =Thread&p rchild!=T) p=p rchild; Visit(p data); p= prchild; return OK;/InorderTraverse_ThrStatus InOrderThreading(BiThrTree &Thrt,BiThrTree T)/中序遍歷二叉樹，并線索化，Thrt指向頭結(jié)點 if(!(T

16、hrt =(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); Thrt LTag = Link; Thrt RTag = Thread; Thrt rchild = Thrt; if(!T) Thrt lchild = Thrt; else Thrt lchild=T; pre=Thrt; InThrTreading(T); pre rchild=Thrt; pre RTag =Thread; Thrt rchild=pre; return OK;/InOrderThreading void InThreading(BiThrTree p)

17、if(p) InThreading(p lchild); if(!p lchild)p LRag =Thread; p lchild=pre; if(!pre rchild) pre RRag =Thread;pre rchild=p; pre=p; InThreading(p rchild); 用數(shù)組存儲樹的結(jié)點,每個結(jié)點中附設(shè)一個字段指示其父結(jié)點的位置。012345678A-1B0C0D0E1F1G3H6I6ABCDEFHIG/-樹的雙親表存儲表示-#define MAX_TREE_SIZE 100typedef struct PTNode /樹中結(jié)點的結(jié)構(gòu) TElemType data;

18、 int parent; /結(jié)點的雙親位置域PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int r,n; /根的位置和結(jié)點數(shù)PTree, *PPTree;：容易找到父結(jié)點及其所有的祖先；也能找到結(jié)點的子女和兄弟(比較麻煩)。但沒有表示出結(jié)點之間的左右次序，所以無法求樹中某個指定結(jié)點的最左子結(jié)點和右兄弟結(jié)點等基本運算。:按某種遍歷次序在數(shù)組中存放結(jié)點。較常見的方法是依次存放樹的先根序列。datachild1child2 childkA BCDEFG HIABCDEFHIG1.k叉樹結(jié)點表示(固定長結(jié)點）datadegreechild1chil

19、d2 childkA 3 B 2C 0D 1E0F 0G 2 H 0I0ABCDEFHIG1.k叉樹結(jié)點表示(固定長結(jié)點）2.變長結(jié)點表示012345678ABCDEFGHI78456ABCDEFHIG1.k叉樹結(jié)點表示(固定長結(jié)點）2.變長結(jié)點表示3.孩子鏈表表示/-樹的孩子鏈表存儲表示-typedef struct EdgeNode/孩子鏈表中結(jié)點的結(jié)構(gòu) int child; struct EdgeNode *next;EdgeNode;typedef struct /結(jié)點表中結(jié)點的結(jié)構(gòu) TElemType data; struct EdgeNode *firstchild; /孩子鏈表頭

20、指針CTNode;typedef struct /樹結(jié)構(gòu) CTNode nodesMAX_TREE_SIZE; int r,n; /根的位置和結(jié)點數(shù)CTree, *PCTree;012345678ABCDEFGHI123 78 45 6 012345678-1A 0B 0C 0D 1E 1F 3G 5H 5I帶雙親的帶雙親的ABCDEFHIG data firstchildnextsiblingA B C D E F G H I ABCDEFHIG結(jié)點: 數(shù)據(jù) 孩子 兄弟 data firstchildnextsiblingA B C D E F G H I 結(jié)點: 數(shù)據(jù) 孩子 兄弟ABCDE

21、FHIG/-樹的二叉鏈表(孩子兄弟)存儲表示-typedef struct CSNodeTElemTypedata;struct CSNode*firstchild,*nextsibling;CSTree, *PCSTree;可以分為三步：(1)連線：相鄰兄弟之間連線。 (2)抹線：抹掉雙親與孩子(除左孩子)之間的連線。 (3)旋轉(zhuǎn)：將樹作適當?shù)男D(zhuǎn)。例：畫出如下圖所示的樹所對應(yīng)的二叉樹。123457681234576812345768(1)將森林中每一棵樹分別轉(zhuǎn)換成二叉樹 (2)合并:使第n棵樹接入到第n-1棵的右邊并成為它的右子樹，第 n-1 棵二叉樹接入到第n-2 棵的右邊并成為它的右子

22、樹，第2棵二叉樹接入到第1棵的右邊并成為它的右子樹，直到最后剩下一棵二叉樹為止。ABCDEFGHIABCDEFGHIABCDEFGHI例：畫出如下圖所示的森林所對應(yīng)的二叉樹。(1) 若某結(jié)點是其雙親的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子、 都與該結(jié)點的雙親結(jié)點連線。(2)刪除原二叉樹中所有雙親結(jié)點與右孩子結(jié)點的連線。(3)整理由(1)、(2)兩步所得的樹或森林，使之結(jié)構(gòu)層次分明。ABCDEFGABCDEFGABCDEFGABCDEFG例：將如下圖所示的二叉樹還原為森林。 在樹和森林中，一個結(jié)點可能有兩棵以上的子樹，所以不宜討論它們的中序遍歷， 即樹和森林只有先根(序)遍歷和后根(序)遍歷

23、。(1)樹的先序遍歷 若樹非空，則先訪問根結(jié)點，然后依次先序遍歷各子樹。 (2)森林的先序遍歷 若森林非空，則先訪問森林中第一棵樹的根結(jié)點，再先序遍歷第一棵樹各子樹，接著先序遍歷第二棵樹、第三棵樹、直到最后一棵樹。(1)樹的后序遍歷 若樹非空，則依次后序遍歷各子樹，最后訪問根結(jié)點。 (2)森林的后序遍歷 依次后序遍歷森林中的每一棵樹。 基本術(shù)語基本術(shù)語從樹中某結(jié)點到其子孫結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑。路徑上的分支數(shù)目。從根結(jié)點到第L層結(jié)點的路徑長度為L-1。從樹根到各結(jié)點的路徑長度之和。完全二叉樹是路徑長度最短的二叉樹。 若將樹中各結(jié)點賦予一個具有某種含義的數(shù)值，則該數(shù)值稱為該。從根

24、結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。 所有葉子結(jié)點的帶權(quán)路徑長度之和，記為WPL=。 mkkklw1D到H的路徑 DGHD到H路徑的長為2 A到H的路徑 ADGHA到H路徑的長為3樹的路徑長度 =1+1+1+2+2+2+3+3=15n個結(jié)點的二叉樹路徑長度最小的是完全二叉樹ABCDEFHIGABCDEFGHI每個葉子結(jié)點都帶權(quán)的二叉樹叫帶權(quán)二叉樹7524葉結(jié)點C的權(quán)為7，根結(jié)點A到C走7次的路徑長度稱為A到C的帶權(quán)路徑的長根到每個葉的帶權(quán)路徑的長的總和叫二叉樹的帶權(quán)路徑的長本樹帶權(quán)路徑的長=7*3+5*2+2*3+4*3=49 帶權(quán)路徑的長WPL= wklkk=1n n個葉子結(jié)點權(quán)值

25、分別為w1,w2,wn的二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹。52745274WPL=49WPL=(7+5+2+4)*2 =3652475247WPL=36WPL=7+5*2+2*3+4*3 =35赫夫曼樹帶權(quán)路徑長度的例子帶權(quán)路徑長度的例子將百分制轉(zhuǎn)換成五級計分制 if(a60) b=E; else if(a70) b=D; else if(a80) b=C; else if(a90) b=B; else b=A;a60b=Ea70b=Da80b=Ca90b=Bb=A100個學(xué)生中5個不及格15個60幾分40個70幾分30個80幾分10個90幾分515403010需比較5+2*15+3*

26、40+4*30+4*10=315次a60b=Ea70b=Da80b=Ca90b=Bb=A5154030a80b=Ca90b=Bb=Aa60b=Ea70b=Dif(a80) if(a70) if(a60)b=E; else b=D; else b=C;else if(a n，則說明找到了合適的解 */if( i n)OutputBoardStatus();elsefor(j = 1; j = n)+total;OutPut();elsefor(j=0; j n; j+)chessij=1;if(CheckBoard()Queen(i+1,n);chessij=0;例如，如右圖所示的樹結(jié)構(gòu),可用二元組表示為：K=A，B，C，D，E，F(xiàn)，G，H，I，