第五章樹和二叉樹-免費閱讀
【正文】 i=m。 } } 2022/8/17 45 赫夫曼解碼算法 DECODE(codetype code[],hufmtree tree[]) { int i,j,c,p,b。 c=i。 char ch。 p2=j。 small2=MAXVAL。i++) { scanf(“%d”,amp。 for (i=1。 赫 夫曼編碼是一種 前綴編碼 。 設給出一段報文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各個字符出現的頻度(次數 )是 W＝ { 2, 7, 4, 5 }。 ????nkkk lwW P L12022/8/17 33 具有不同帶權路徑長度的二叉樹 赫夫曼樹 帶權路徑長度達到最小的二叉樹即為赫夫曼樹。 else { if (bdata == x) return (b)。 else qrchild=prchild。amp。 slchild=NULL。 // 將 s插入到左子樹中 else if ( sdata bdata ) INSERT(brchild, s)。(sltag==1)) slchild＝ q。 qltag＝ 1。 } } 2022/8/17 9 若 *p 的左子樹為空，則 plchild 為左線 索，直接指向 *p 的中序前驅結點。 // 中序向前遍歷一個結點 INTHREAD(prchild, pre)。 plchild＝ pre。 一、線索二叉樹 2022/8/17 3 線索二叉樹結點的描述 typedef int datatype。 typedef struct node { int ltag,rtag。 } else pltag＝ 0。 } } 2022/8/17 6 若 *p 的右子樹為空，則 prchild 為右線 索，直接指向 *p 的中序后繼結點。 若 *p 的左子樹非空，則從 *p 的左孩子出發(fā) ，沿右指針鏈往下查找，直到找到一個沒有右 孩子的結點為止。 qlchild＝ p。 } 2022/8/17 13 二叉排序樹又稱為二叉查找樹，其定義為： 二叉排序樹或者是一棵空樹，或者是具有如下性質的二叉樹： 若它的左子樹非空，則左子樹上所有結點的值 均小于根結點； 若它的右左子樹非空，則右子樹上所有結點的 值均大于根結點； 左、右子樹本身又各是一棵二叉樹。 // 將 s插入到右子樹中 } 2022/8/17 17 二叉排序樹的生成 void CREAT(bitree *b) { int x。 srchild=NULL。 pdata!=x) { if (x pdata) { q=p。 } 2022/8/17 22 else // 被刪結點有左子樹 { // 查找被刪結點的左子樹中的最右結點，即剛好小于 x的結點 r=plchild。 if (bdata x) return (SEARCH(blchild))。在赫夫曼樹中，權值大的結點離根最近。 若給每個字符以等長編碼 A : 00 T : 10 C : 01 S : 11 則總編碼長度為 ( 2+7+4+5 ) * 2 = 36. 若按各個字符出現的概率不同而給予不等長編碼，可望減少總編碼長度。解碼時不會 混淆。i=m。f)。 for (j=1。 } tree[p1].parent=i。 } codetype。 p=tree[i
環(huán)評公示相關推薦
鄂ICP備17016276號-1