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

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

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

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

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

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

7、 2k-1n2k-1，即。 2k-1n2k，同時(shí)取對(duì)數(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) /訪問(wèn)結(jié)點(diǎn)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) /訪問(wèn)結(jié)點(diǎn)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為一個(gè)棧 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é)點(diǎn) int b,top=0,s2100;/s2棧存放進(jìn)棧標(biāo)志 p=T; do while

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

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

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

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

15、,對(duì)每個(gè)數(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)/中序遍歷二叉樹(shù)，并線索化，Thrt指向頭結(jié)點(diǎn) 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ù)組存儲(chǔ)樹(shù)的結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)字段指示其父結(jié)點(diǎn)的位置。012345678A-1B0C0D0E1F1G3H6I6ABCDEFHIG/-樹(shù)的雙親表存儲(chǔ)表示-#define MAX_TREE_SIZE 100typedef struct PTNode /樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu) TElemType data;

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

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

20、指針CTNode;typedef struct /樹(shù)結(jié)構(gòu) CTNode nodesMAX_TREE_SIZE; int r,n; /根的位置和結(jié)點(diǎn)數(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é)點(diǎn): 數(shù)據(jù) 孩子 兄弟 data firstchildnextsiblingA B C D E F G H I 結(jié)點(diǎn): 數(shù)據(jù) 孩子 兄弟ABCDE

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

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

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

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

25、分別為w1,w2,wn的二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)。52745274WPL=49WPL=(7+5+2+4)*2 =3652475247WPL=36WPL=7+5*2+2*3+4*3 =35赫夫曼樹(shù)帶權(quán)路徑長(zhǎng)度的例子帶權(quán)路徑長(zhǎng)度的例子將百分制轉(zhuǎn)換成五級(jí)計(jì)分制 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個(gè)學(xué)生中5個(gè)不及格15個(gè)60幾分40個(gè)70幾分30個(gè)80幾分10個(gè)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，則說(shuō)明找到了合適的解 */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;例如，如右圖所示的樹(shù)結(jié)構(gòu),可用二元組表示為：K=A，B，C，D，E，F(xiàn)，G，H，I，