五章樹和二叉樹課件

1、應(yīng)用第五章 樹和二叉樹8/21/20221 二叉樹在一般情況下無法直接找到某結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)。若增加指針域來存放前驅(qū)和后繼結(jié)點(diǎn)信息，將大大降低存儲(chǔ)空間的利用率（密度）。考察 n 個(gè)結(jié)點(diǎn)的二叉樹，其中有 n+1 個(gè)空指針域，它們可以被用來存放“線索”加了線索的二叉樹稱為線索二叉樹。一、線索二叉樹8/21/20222線索二叉樹結(jié)點(diǎn)的描述typedef int datatype;typedef struct node int ltag,rtag; datatype data; struct node *lchild,*rchild; bithptr;bithptr *pre;lc

2、hildltagrtagdatarchild標(biāo)志位如果為0，表示指針指向孩子結(jié)點(diǎn)，為1表示指針為線索8/21/202230 A 00 B 00 E 11 C 11 D 11 F 00 G 01 H 11 I 1NULLNULLt8/21/20224中序線索化算法INTHREAD(bithptr *p,bithptr *pre)/ p為當(dāng)前結(jié)點(diǎn)，pre為p的前驅(qū)結(jié)點(diǎn)，開始調(diào)用時(shí)p為根結(jié)點(diǎn)指針，pre為NULL if (p!=NULL) INTHREAD(p-lchild,pre); / 左子樹線索化 / 若當(dāng)前結(jié)點(diǎn)的左子樹為空，則建立指向其前驅(qū)結(jié)點(diǎn)的前驅(qū)線索 if (p-lchild = = N

3、ULL) p-ltag1; p-lchildpre; else p-ltag0; / 若前驅(qū)結(jié)點(diǎn)不為空，且其右孩子為空，則建立該前驅(qū)結(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)的后續(xù)線索 if (pre!=NULL & pre-rchild = = NULL) pre-rtag1; pre-rchildp; else p-rtag0; prep; / 中序向前遍歷一個(gè)結(jié)點(diǎn) INTHREAD(p-rchild, pre); 8/21/202251、若 *p 的右子樹為空，則 p-rchild 為右線 索，直接指向 *p 的中序后繼結(jié)點(diǎn)。2、若 *p 的右子樹非空，則 *p 的中序后繼必是 其右子樹中第一個(gè)遍歷到的結(jié)點(diǎn)，也就

4、是從 *p的右孩子開始，沿左指針鏈往下查找，直 到找到一個(gè)沒有左孩子的結(jié)點(diǎn)為止。中序線索二叉樹中，查找指定結(jié)點(diǎn)*p的中序后繼結(jié)點(diǎn)8/21/20226pR1R2Rk最左下結(jié)點(diǎn)8/21/20227中序線索二叉樹中求中序后繼結(jié)點(diǎn)的算法bithptr *INORDERNEXT(bithptr *p) bithptr *q; if (p-rtag=1) return(p-rchild); else qp-rchild; while (q-ltag=0) qq-lchild; return(q); 8/21/202281、若 *p 的左子樹為空，則 p-lchild 為左線 索，直接指向 *p 的中序前驅(qū)

5、結(jié)點(diǎn)。2、若 *p 的左子樹非空，則從 *p 的左孩子出發(fā) ，沿右指針鏈往下查找，直到找到一個(gè)沒有右 孩子的結(jié)點(diǎn)為止。中序線索二叉樹中，查找指定結(jié)點(diǎn)*p的中序前驅(qū)結(jié)點(diǎn)8/21/20229pR1R2Rk最右下結(jié)點(diǎn)8/21/202210線索二叉樹的遍歷算法TRAVERSEINTHREAD(bithptr *p) if (p!=NULL) while (p-ltag=0) pp-lchild; do printf(“t%dn”,p-data); pINORDERNEXT(p); while(p!=NULL); 8/21/202211線索二叉樹的結(jié)點(diǎn)插入算法INSERTRIGHT(bithptr *p

6、,bithptr *q) bithptr *s; sINORDERNEXT(p); q-ltag1; q-lchildp; q-rtagp-rtag; q-rchildp-rchild; p-rtag0; p-rchildq; if (s!=NULL)&(s-ltag=1) s-lchildq;8/21/202212 二叉排序樹又稱為二叉查找樹，其定義為：二叉排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：1、若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值 均小于根結(jié)點(diǎn)；2、若它的右左子樹非空，則右子樹上所有結(jié)點(diǎn)的 值均大于根結(jié)點(diǎn)；3、左、右子樹本身又各是一棵二叉樹。二、二叉排序樹8/21/202

7、213caozhaodingchenwangmaxiaduni8/21/202214二叉排序樹結(jié)點(diǎn)的結(jié)構(gòu)描述typedef struct node datatype data; struct node *lchild,*rchild; bitree;8/21/202215二叉排序樹的結(jié)點(diǎn)插入/ 向一個(gè)二叉排序樹中插入一個(gè)結(jié)點(diǎn)svoid INSERT(bitree *b, bitree *s) if ( b = NULL ) b=s; else if ( s-data = b-data ) return; / 不做任何插入操作 else if ( s-data data ) INSERT(b-l

8、child, s); / 將s插入到左子樹中 else if ( s-data b-data ) INSERT(b-rchild, s); / 將s插入到右子樹中 8/21/202216二叉排序樹的生成void CREAT(bitree *b) int x; bitree *s; b=NULL; do scanf(“%d”,&x); / 讀入一個(gè)整數(shù) s=(bitree *)malloc(sizeof(bitree); / 產(chǎn)生一個(gè)樹結(jié)點(diǎn) s-data=x; s-lchild=NULL; s-rchild=NULL; INSERT(b,s); / 插入該結(jié)點(diǎn) while(x!=-1);8/21

9、/202217452453122890關(guān)鍵字輸入順序：45，24，53，12，28，908/21/202218二叉排序樹的結(jié)點(diǎn)刪除(被刪除結(jié)點(diǎn)無左孩子)qpqpp是左孩子p是右孩子8/21/202219二叉排序樹的結(jié)點(diǎn)刪除(被刪除結(jié)點(diǎn)有左孩子)qpqpp是左孩子p是右孩子8/21/202220二叉排序樹的結(jié)點(diǎn)刪除算法/ 在二叉排序樹b中刪除一個(gè)數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)的算法函數(shù)void DELNODE(bitree *b, int x) bitree *p, *q, *r, *t; p=b; / p指向待比較的結(jié)點(diǎn) q=NULL; / q指向p的前驅(qū)結(jié)點(diǎn) while (p!=NULL & p-data

10、!=x) if (x data) q=p; p=p-lchild; else q=p; p=p-rchild; if (p=NULL) printf(“未發(fā)現(xiàn)數(shù)據(jù)域?yàn)?d的結(jié)點(diǎn)n”, x); else if (p-lchild=NULL) / 被刪結(jié)點(diǎn)無左子樹 if (q=NULL) t=p-rchild; else if (q-lchild=p) q-lchild=p-rchild; else q-rchild=p-rchild; 8/21/202221 else / 被刪結(jié)點(diǎn)有左子樹 / 查找被刪結(jié)點(diǎn)的左子樹中的最右結(jié)點(diǎn)，即剛好小于x的結(jié)點(diǎn) r=p-lchild; while (r-rch

11、ild != NULL) r=r-rchild; / 被刪結(jié)點(diǎn)的右子樹作為r的右子樹 r-rchild=p-rchild; / 被刪結(jié)點(diǎn)的左子樹根代替被刪結(jié)點(diǎn) if (q=NULL) t=p-lchild; else if (q-lchild=p) q-lchild=p-lchild; else q-rchild=p-lchild; 8/21/202222二叉排序樹的查找bitree *SEARCH(bitree *b, int x) if (b=NULL) return (NULL); else if (b-data = x) return (b); if (b-data x) return

12、 (SEARCH(b-lchild); else return (SEARCH(b-rchild); 8/21/202223一棵 m 階的B-樹滿足下列條件：1、每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子；2、根結(jié)點(diǎn)至少有兩個(gè)孩子（唯一例外的是只包含一個(gè)根 結(jié)點(diǎn)的B-樹）；3、除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有 m/2 個(gè) 孩子；4、有n+1個(gè)孩子的非葉結(jié)點(diǎn)恰好包含n個(gè)關(guān)鍵字 (A0 , K1 , A1 , K2 , A2 , Kn, An);5、所有葉結(jié)點(diǎn)在同一層，葉結(jié)點(diǎn)不包含任何關(guān)鍵字信息。三、B-樹8/21/202224357045112236392490560631670008040052110135

13、1422122372402793783813883933964004354714925025538/21/202225 在B-樹中包含j個(gè)關(guān)鍵字，j+1個(gè)指針的結(jié)點(diǎn)，一般表示形式為：A0 , K1 , A1 , K2 , A2 , Kj , Aj8/21/202226B-樹的運(yùn)算1、查找2、插入 132 142 212 132 137 142 212 插入137變?yōu)?/21/2022273574903924004534604713933965606316708/21/2022283、刪除0521122360080400521101351422122372402798/21/2022290521

14、352360080401101121422122372402790522360080401101351422122372402798/21/202230具有不同路徑長度的二叉樹四、赫夫曼樹 (Huffman Tree)路徑長度 (Path Length) 兩個(gè)結(jié)點(diǎn)之間的路徑長度是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。樹的路徑長度是從樹根到每一結(jié)點(diǎn)的路徑長度之和。8/21/202231帶權(quán)路徑長度 ( Weighted Path Length, WPL )樹的帶權(quán)路徑長度是樹的各葉結(jié)點(diǎn)所帶的權(quán)值與該結(jié)點(diǎn)到根的路徑長度的乘積的和。8/21/202232具有不同帶權(quán)路徑長度的二叉樹赫夫曼樹 帶權(quán)路徑長度達(dá)到最

15、小的二叉樹即為赫夫曼樹。在赫夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根最近。8/21/202233三種前綴編碼字符概率編碼1編碼2編碼3a0.120000001111b0.40001110c0.1501001110d0.080110011110e0.2510010108/21/202234adceb8/21/202235赫夫曼算法 (1) 由給定的n個(gè)權(quán)值w1, w2, , wn，構(gòu)造具有n棵二叉樹的森林F = T1, T2, , Tn，其中每一棵二叉樹Ti只有一個(gè)帶有權(quán)值wi的根結(jié)點(diǎn)，其左、右子樹均為空。 (2) 重復(fù)以下步驟, 直到F中僅剩下一棵樹為止： 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹, 做為左、

16、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。 在F中刪去這兩棵二叉樹。 把新的二叉樹加入F。8/21/202236赫夫曼樹的構(gòu)造過程8/21/202237赫夫曼編碼 主要用途是實(shí)現(xiàn)數(shù)據(jù)壓縮。 設(shè)給出一段報(bào)文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各個(gè)字符出現(xiàn)的頻度(次數(shù))是 W 2, 7, 4, 5 。 若給每個(gè)字符以等長編碼 A : 00 T : 10 C : 01 S : 11則總編碼長度為 ( 2+7+4+5 ) * 2 = 36. 若按各個(gè)字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。

17、因各字符出現(xiàn)的概率為 2/18, 7/18, 4/18, 5/18 。8/21/202238化整為 2, 7, 4, 5 ，以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值，建立赫夫曼樹。左分支賦 0，右分支賦 1，得赫夫曼編碼(變長編碼)。 A : 0 T : 10 C : 110 S : 111它的總編碼長度：7*1+5*2+( 2+4 )*3 = 35。比等長編碼的情形要短。 總編碼長度正好等于赫夫曼樹的帶權(quán)路徑長度WPL。 赫夫曼編碼是一種前綴編碼。解碼時(shí)不會(huì)混淆。赫夫曼編碼樹8/21/202239赫夫曼樹的存儲(chǔ)結(jié)構(gòu)#define n 7#define m 2*n-1typedef struct int we

18、ight; int lchild,rchild,parent; hufmtree;hufmtree treem+1;8/21/202240赫夫曼樹的構(gòu)造算法HUFFMAN(hufmtree tree) int i,j,p1,p2; int small1,small2,f; for (i=1;i=m;i+) treei.parent=0; treei.lchild=0; treei.rchild=0; treei.weight=0; for (i=1;i=n;i+) scanf(“%d”,&f); treei.weight=f; for (i=n+1;i=m;i+) p1=0; p2=0; sm

19、all1=MAXVAL; small2=MAXVAL; for (j=1;j=i-1;j+) if (treej.parent = 0) if (treej.weightsmall1) small2=small1; small1=treej.weight; p2=p1; p1=j; else if (treej.weightsmall2) small2=treej.weight; p2=j; treep1.parent=i; treep2.parent=i; treei.lchild=p1; treei.rchild=p2; treei.weight=treep1.weight+ treep2.weight; 8/21/202241赫夫曼編碼的存儲(chǔ)結(jié)構(gòu)typedef struct char bitsn+1; int start; char ch; codetype