【正文】 序樹算法 二叉排序樹結(jié)點結(jié)構(gòu)： struct tree { char info； struct tree *left ， * right ； } 算法描述 : ? 輸入結(jié)點非空循環(huán) , 若是第 1個結(jié)點 ,令指針ROOT指向該結(jié)點。 rinfo = info 。 struct tree *create_btree(),*search_btree(),*root=0。 else create_btrr(root,root,*s)。 while ( key) { printf(“Enter a key to find:”)。 printf(“press to continue\n”)。 if ( r = = 0) { printf(“Out of memory\n”)。 rinfo=info。 rleft = 0。 } /* create_btree(root,r,info) */ struct tree *search_btree(root,key) struct tree *root。 } while(rootinfo!=key) { if(keyrootinfo) root=rootleft。 } } /* while(rootinfo!=key) */ 查詢二叉排序樹程序 if (root !=0) printf(“Successful search\n key=%c\n”,rootinfo)。 { int i。il。 } 程序輸入 輸入： 輸出： h ? b d ? d p ? e r ? h b ? p e ? r ? 舉例 對數(shù)列 {10， 18， 3， 4， 9， 13， 25}， 生成二叉排序樹 。 旋轉(zhuǎn)分： LL、 RR、 LR和 RL 四種 。先逆時針 ,再順時針旋轉(zhuǎn) ） 操作 。 ? 插入 24,樹仍為平衡 。 ? 樹的帶權(quán)路徑長度定義為： WPL = ∑ wklk k = 1 n 其中： n 是樹中葉結(jié)點的個數(shù) wi 是第 i個結(jié)點的權(quán)值 li 是第 i個結(jié)點的路徑長度 Huffman樹舉例 ? 以下有三棵樹： （ a） （ b） （ c） a b c d a b c d a c b d 7 7 7 5 5 5 2 2 2 4 4 4 WPLa =7x2+5x2+2x2+4x2 = 36 WPLb =7x3+5x3+2x1+4x2 = 46 WPLc = 7x1+5x2+2x3+4x3 = 35 √ ? 事實證明按哈夫曼樹構(gòu)造二叉樹，可得到很好的特性，應(yīng)用于實際問題，可提高處理效率。 – 2）在 T中選取兩個權(quán)值最小的結(jié)點作為左右子樹，構(gòu)成一個新的二叉樹，其根結(jié)點的權(quán)值取左右子樹權(quán)值之和； – 3）在 T中刪除這兩棵樹，將新構(gòu)成的樹加入到 T中； – 4）重復(fù) 2）、 3）步的操作，直到 T中只含一棵樹為止，該樹就是 Huffman樹。 a 0 b 0 1 c d 0 1 1 編碼： A（ 0） B（ 01） C（ 011） D（ 111） 方法約定： 1）左分支為‘ 0’ 2）右分支為‘ 1’ 3）由葉到根路徑上字符組成的二進制串就是該葉結(jié)點的編碼。例如， 4個結(jié)點的Huffman樹，共有 7個結(jié)點。 0 0 0 0 0 0 0 1 1 1 1 1 1 1 5 3 7 8 14 29 11 23 42 58 100 Huffman編碼為： A 5 0110 B 29 01 C 7 0111 D 8 1111 E 14 011 F 23 00 G 3 1110 H 11 010 Huffman編碼的譯碼 ? 從 Huffman編碼樹上不難看出，代碼全部在葉結(jié)點上，根據(jù) Huffman編碼，就能求出相應(yīng)的字符。 ? 例如，根據(jù)“ 1111”，就能求出對應(yīng)的字符是“ 8”。 ? 譯碼是根據(jù)從根到葉的 Huffman編碼求相應(yīng)的字符。 ? 求 Huffman編碼： 從葉到根的編碼。以給定權(quán)值的結(jié)點構(gòu)造 Huffman樹，按二進制前綴編碼的方式構(gòu)成的編碼為 Huffman編碼。T= { a b c d } c d T3 2 4 6 b T3 T2 6 5 11 b T2 6 5 11 c d 2 4 18 a T2 7 11 T1 6 18 a 7 T1 b T3 T2 5 11 18 a 7 T1 b 5 11 c d 2 6 4 （ d） T={ T1 } （ c） T= { a T2 } （ b） T= { a b T3 } （ a） T= { a b c d } 代入 T2 代入T3 示例 Huffman編碼 ? 編碼：用二進制數(shù)的不同組合來表示字符的方法。 將百分制轉(zhuǎn)換成五分制 ? 判定樹比較： a60? a70? a80? a90? 不及格 及格 中等 良好 優(yōu)秀 Y Y Y Y N N N N a80? a70? a90? a60? 不及格 優(yōu)秀 良好 中等 中等 及格 不及格 Y Y Y N N N N Y (A) (B) ? 若輸入 1萬個數(shù)據(jù)，按 A的判定過程進行操作，約需比較 萬次，而按 B比較 ,則僅需 。 ? 插入 90,樹仍平衡 。先順時針 ,再逆時針旋轉(zhuǎn) ）操作 。 程序?qū)崿F(xiàn)為： b = a?.lc a?.lc = b?.rc b?.rc = a a?.bf = 0 b?.bf = 0 b為子樹的新根 A B C LL B C A 示例 示意為： RR平衡化處理 由于在 A的右子樹的右子樹上插入結(jié)點 ， 使 A點失去平衡 ， 需進行一次RR旋轉(zhuǎn) （ 逆時針旋轉(zhuǎn) ）操作 。因此 ， 在動態(tài)生成二叉排序樹的過程中 ， 要進行平衡化處理 。 printf(“%c\n”,rinfo)。 print_tree(rleft,l+1)。 } /* *search_btree(root,key) */ 查詢二叉排序樹程序（續(xù)） 打印二叉排序樹程序 print_btree(r,l) struct tree *r。 if(root==0) { printf(“Search Failure\n”)。 { if (!root) { printf(“Emptu btree\n”)。 } /* if = = 0 接下頁 */ 生成二叉排序樹程序 （續(xù)） if (info rinfo) create_btree(r,rleft,info)。 else rootright=r。 } rleft= 0。 char info。c)。 主程序 (續(xù)） print_btree(root,0)。 gets(s)。 struct tree *left,*right。 二叉排序樹生成算法 建立二叉樹Create_btree()查詢結(jié)點Search_btree()打印二叉樹Print_btree()主程序 主程序框圖 開始 初始化 輸入結(jié)點數(shù)據(jù) ！ ROOT root=create_btee（） create_btree() 結(jié)束 ? N Y 打印該樹 查找指定結(jié)點 Print_btree() Search_btree() 生成二叉排序樹程序框圖 Create_btre