【文章內(nèi)容簡介】 3,x2=4 m1=2,m2=4 (2) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 0 7 5 2 4 6 11 0 0 0 0 0 4 5 0 0 6 5 5 6 0 0 k x1=2,x2=5 m1=5,m2=6 (3) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 1 7 5 2 4 6 11 18 0 0 0 0 4 5 6 7 6 5 5 6 7 0 k x1=1,x2=6 m1=7,m2=11 (4) ?Huffman樹應(yīng)用 ?最佳判定樹 等級 分?jǐn)?shù)段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A 70?a80 a60 C Y N B Y N D Y N E Y N A 80?a90 60?a70 E A D E C a80 a70 a60 a90 E Y N D Y N C Y N B Y N A ?Huffman編碼：數(shù)據(jù)通信用的二進制編碼 ?思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短 ?編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造 Huffman樹，然后將樹中結(jié)點引向其左孩子的分支標(biāo)“ 0”，引向其右孩子的分支標(biāo)“ 1”；每個字符的編碼即為從根到每個葉子的路徑上得到的 0、 1序列 例 要傳輸?shù)淖址? D={C,A,S,T, 。 } 字符出現(xiàn)頻率 w={2,4,2,3,3} C S 3 3 6 4 2 2 4 8 14 T 。 A 0 0 1 1 0 1 1 0 T : 00 。 : 01 A : 10 C : 110 S : 111 ?譯碼：從 Huffman樹根開始，從待譯碼電文中逐位取碼。若編碼是“ 0”，則向左走；若編碼是“ 1”，則向右走，一旦到達葉子結(jié)點，則譯出一個字符；再重新從根出發(fā)，直到電文結(jié)束 例 電文是 {CAS。CAT。SAT。AT} 其編碼 “ 11010111011101000011111000011000” 電文為“ 1101000” 譯文只能是“ CAT” C S 3 3 6 4 2 2 4 8 14 T 。 A 0 0 1 1 0 1 1 0 T : 00 。 : 01 A : 10 C : 110 S : 111 ?線索二叉樹 ?定義： ?前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為 ~ ?線索：指向前驅(qū)或后繼結(jié)點的指針稱為 ~ ?線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫 ~ ?線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫 ~ ?實現(xiàn) ?在有 n個結(jié)點的二叉鏈表中必定有 n+1個空鏈域 ?在線索二叉樹的結(jié)點中增加兩個標(biāo)志域 ?lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驅(qū) ?rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后繼 ?結(jié)點定義： typedef struct node { int data。 int lt, rt。 struct node *lc, *rc。 }JD。 lc lt data rt rc A B C D E A B D C E T 先序序列： ABCDE 先序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 A B C D E A B D C E T 中序序列： BCAED 中序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 ^ A B C D E A B D C E T 后序序列： CBEDA 后序線索二叉樹 0 0 0 0 1 1 1 1 1 1 ^ A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列： BCAED 帶頭結(jié)點的中序線索二叉樹 0 1 頭結(jié)點： lt=0, lc指向根結(jié)點 rt=1, rc指向遍歷序列中最后一個結(jié)點 遍歷序列中第一個結(jié)點的 lc域和最后 一個結(jié)點的 rc域都指向頭結(jié)點 A B D C E T 中序序列： BCAED 中序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 ^ ?算法 ?按中序線索化二叉樹 A B C D E t 0 1 pr p i PA JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t。 int i=0。 t=(JD *)malloc(sizeof(JD))。 tlt=0。 trt=1。 trc=t。 if(bt==NULL) tlc=t。 else { tlc=bt。 pr=t。 p=bt。 do{ while(p!=NULL) { s[i++]=p。 p=plc。 } if(i0) { p=s[i]。 printf(%c ,pdata)。 if(plc==NULL) { plt=1。 plc=pr。} if(prrc==NULL) { prrt=1。 prrc=p。} pr=p。 p=prc。 } }while(i0||p!=NULL)。 prrc=t。 prrt=1。 trc=pr。 } return(t)。 } A B D C E bt ^ ^ ^ ^ ^ ^ 0 0 0 0 0 0 0 0 0 0 ?算法 ?按中序線索化二叉樹 A B C D E A B D C E bt ^ ^ ^ ^ ^ ^ t 0 1 pr p i PA PB JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t。 int i=0。 t=(JD *)malloc(sizeof(JD))。 tlt=0。 trt=1。 trc=t。 if(bt==NULL) tlc=t。 else { tlc=bt。 pr=t。 p=bt。 do{ while(p!=NULL) { s[i++]=p。 p=plc。 } if(i0) { p=s[i]。 printf(%c ,pdata)。 if(plc==NULL) { plt=1。 plc=pr。} if(prrc==NULL) { prrt=1。 prrc=p。} pr=p。 p=prc。 } }while(i0||p!=NULL)。 prrc=t。 prrt=1。 trc=pr。 } return(t)。 } 0 0 0 0 0 0 0 0 0 0 ?算法 ?按中序線索化二叉樹 A B C D E A B D C E bt ^ ^ ^ ^ ^ ^ t 0 1 pr P=NULL i PA PB JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t。 int i=0。 t=(JD *)malloc(sizeof(JD))。 tlt=0。 trt=1。 trc=t。 if(bt==NULL) tlc=t。 else { tlc=bt。 pr=t。 p=bt。 do{ while(p!=NULL) { s[i++]=p。 p=plc。 } if(i0) { p=s[i]。 printf(%c ,pdata)。 if(plc==NULL) { plt=1。 plc=pr。} if(prrc==NULL) { prrt=1。 prrc=p。} pr=p。 p=prc。 } }while(i0||p!=NULL)。 prrc=t。 prrt=1。 trc=pr。 } return(t)。 } 0 0 0 0 0 0 0 0 0 0 ?算法 ?按中序線索化二叉樹 A B C D E A B D C E bt ^ ^ ^ ^ ^ ^ t 0 1 pr P i PA 輸出 :B JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t。 int i=0。 t=(JD *)malloc(sizeof(JD))。 tlt=0。 trt=1。 trc=t。 if(bt==NULL) tlc=t。 else { tlc=bt。 pr=t。 p=bt。 do{ while(p!=NULL) { s[i++]=p。 p=plc。 } if(i0) { p=s[i]。 printf(%c ,pdata)。 if(plc==NULL) { plt=1。 plc=pr。} if(prrc==NULL) { prrt=1。 prrc=p。} pr=p。 p=prc。 } }while(i0||p!=NULL