樹(shù)的定義和基本術(shù)語(yǔ)二叉樹(shù)binarytree二叉樹(shù)的存儲(chǔ)結(jié)-資料下載頁(yè)
2025-07-19 20:10本頁(yè)面
【正文】 成的森林。 (3) 二叉樹(shù)轉(zhuǎn)換為森林的規(guī)則 ? 如果 B為空 ，則 對(duì)應(yīng)的森林 F也為空。 ? 如果 B非空 ，則 F中第一棵樹(shù) T1的根為 root； T1的根的子樹(shù)森林 { T11, T12, …, T1m }是由 root 的左子樹(shù) LB 轉(zhuǎn)換而來(lái)， F 中除了 T1 之外 其余的樹(shù)組成的森林 { T2, T3, …, Tn } 是由 root 的右子樹(shù) RB 轉(zhuǎn)換而成的森林。 3. 樹(shù)和森林的遍歷 樹(shù)的遍歷（先根遍歷、后根遍歷、層次遍歷） （ 1）先根遍歷：先根訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù) （ 2）后根遍歷：先依次后根遍歷每棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn) 樹(shù)的先根遍歷 轉(zhuǎn)換后的二叉樹(shù)的先序遍歷 樹(shù)的后根遍歷 轉(zhuǎn)換后的二叉樹(shù)的中序遍歷 森林的遍歷 先序：對(duì)應(yīng)二叉樹(shù)的先序遍歷 后序：對(duì)應(yīng)二叉樹(shù)的后序遍歷 森林的遍歷 森林的二叉樹(shù)表示 (1) 先根次序遍歷的規(guī)則： ? 若森林 F為空 , 返回；否則 ? 訪(fǎng)問(wèn) F的第一棵樹(shù)的根結(jié)點(diǎn)； ? 先根次序遍歷第一棵樹(shù)的子樹(shù)森林； ? 先根次序遍歷其它樹(shù)組成的森林。 森林的遍歷 森林的二叉樹(shù)表示 (2) 中根次序遍歷的規(guī)則： ? 若森林 F為空，返回；否則 ? 中根次序遍歷第一棵樹(shù)的子樹(shù)森林； ? 訪(fǎng)問(wèn) F的第一棵樹(shù)的根結(jié)點(diǎn)； ? 中根次序序遍歷其它樹(shù)組成的森林。 森林的遍歷 森林的二叉樹(shù)表示 (3) 后根次序遍歷的規(guī)則： ? 若森林 F為空，返回；否則 ? 后根次序遍歷第一棵樹(shù)的子樹(shù)森林； ? 后根次序遍歷其它樹(shù)組成的森林； ? 訪(fǎng)問(wèn) F的第一棵樹(shù)的根結(jié)點(diǎn) 。 。 森林的遍歷 森林的二叉樹(shù)表示 (4) 廣度優(yōu)先遍歷 (層次序遍歷 ) ： ? 若森林 F為空，返回；否則 ? 依次遍歷各棵樹(shù)的根結(jié)點(diǎn)； ? 依次遍歷各棵樹(shù)根結(jié)點(diǎn)的所有孩子； ? 依次遍歷這些孩子結(jié)點(diǎn)的孩子結(jié)點(diǎn) 。 ?? 具有不同路徑長(zhǎng)度的二叉樹(shù) 赫夫曼樹(shù) (Huffman Tree)及其應(yīng)用 p144 路徑長(zhǎng)度 (Path Length) 兩個(gè)結(jié)點(diǎn)之間的路徑長(zhǎng)度 是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。 樹(shù)的路徑長(zhǎng)度 是各結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度之和。 n個(gè)結(jié)點(diǎn)的二叉樹(shù)的路徑長(zhǎng)度不小于下述數(shù)列前n項(xiàng)的和，即 其路徑長(zhǎng)度最小者為 ? ????niiPL12l o g帶權(quán)路徑長(zhǎng)度 ( Weighted Path Length, WPL ) 樹(shù)的帶權(quán)路徑長(zhǎng)度是樹(shù)的各 葉結(jié)點(diǎn) 所帶的權(quán)值與該結(jié)點(diǎn)到根的路徑長(zhǎng)度的乘積的和。 ????niii lwW P L1? ????niiPL12l o g??????????? 332222110具有不同帶權(quán)路徑長(zhǎng)度的擴(kuò)充二叉樹(shù) 赫夫曼樹(shù) 帶權(quán)路徑長(zhǎng)度達(dá)到最小的二叉樹(shù)即為赫夫曼樹(shù)（最優(yōu)二叉樹(shù)）。 在赫夫曼樹(shù)中，權(quán)值大的結(jié)點(diǎn)離根最近。 ? 赫夫曼樹(shù)的應(yīng)用 ?在解決某些判定問(wèn)題時(shí)，利用赫夫曼樹(shù)可以得到最佳判定算法 p145圖 ?用于通訊和數(shù)據(jù)傳送時(shí)的赫夫曼編碼 ? 任一字符的編碼都 不是 另一字符編碼的前綴，稱(chēng)為前綴編碼。 p146 赫夫曼算法 —— 如何構(gòu)造一棵赫夫曼樹(shù) (1) 由給定的 n個(gè)權(quán)值 {w0, w1, w2, …, wn1}，構(gòu)造具有 n棵二叉樹(shù)的森林 F = {T0, T1, T2, …, Tn1}，其中每一棵二叉樹(shù) Ti只有一個(gè)帶有權(quán)值 wi的根結(jié)點(diǎn)，其左、右子樹(shù)均為空。 (2) 重復(fù)以下步驟 , 直到 F中僅剩下一棵樹(shù)為止： ① 在 F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹(shù) , 做為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)。置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。 ② 在 F中刪去這兩棵二叉樹(shù)。 ③ 把新的二叉樹(shù)加入 F。 赫夫曼樹(shù)的構(gòu)造過(guò)程 赫夫曼編碼 主要用途是實(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è)字符以等長(zhǎng)編碼 A : 00 T : 10 C : 01 S : 11 則總編碼長(zhǎng)度為 ( 2+7+4+5 ) * 2 = 36. 若按各個(gè)字符出現(xiàn)的概率不同而給予不等長(zhǎng)編碼，可望減少總編碼長(zhǎng)度。 因各字符出現(xiàn)的概率為 { 2/18, 7/18, 4/18, 5/18}。 化整為 { 2, 7, 4, 5 }，以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值，建立赫夫曼樹(shù)。左分支賦 0，右分支賦 1，得赫夫曼編碼 (變長(zhǎng)編碼 )。 A : 0 T : 10 C : 110 S : 111 它的總 編碼長(zhǎng)度： 7*1+5*2+( 2+4 )*3 = 35。比等長(zhǎng)編碼的情形要短。 總編碼長(zhǎng)度正好等于 赫夫曼樹(shù)的帶權(quán)路徑長(zhǎng) 度 WPL。 赫夫曼編碼是一種 無(wú) 前綴的編碼 。解碼時(shí)不會(huì) 混淆。 赫夫曼編碼樹(shù) typedef struct { unsigned int weight。 unsigned int parent,lchild,rchild。 } HTNode, *HuffmanTree。 typedef char **HuffmanCode。 void HuffmanCoding(HuffmanTree amp。HT,HuffmanCode amp。HC,int *w, int n) { HuffmanTree p。 char *cd。 int i,s1,s2,start。 unsigned int c,f。 if (n=1) return。 // n為字符樹(shù)木， m為結(jié)點(diǎn)樹(shù)木 int m=2*n1。 HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode))。 // 0號(hào)單元未用 建立赫夫曼樹(shù)及求赫夫曼編碼的算法 (p147算法 ) for (p=HT, i=1。 i=n。 ++i,++p,++w) { pweight = *w。 pparent=0。 plchild=0。prchild=0。 } // *p = { *w,0,0,0 }。 for (。 i=m。++i,++p) { pweight = 0。 pparent=0。 plchild=0。 prchild=0。 } //*p={ 0,0,0,0 }。 for (i=n+1。 i=m。++i) // 建赫夫曼樹(shù) { Select(HT,i1,s1,s2)。 HT[s1].parent=i。 HT[s2].parent = i。 HT[i].lchild = s1。 HT[i].rchild = s2。 HT[i].weight = HT[s1].weight + HT[s2].weight。 } //從葉子到根逆向求赫夫曼編碼 HC= (HuffmanCode)malloc((n+1)*sizeof(char *))。 cd = (char*)malloc(n*sizeof(char))。 cd[n1]=39。\039。 for (i=1。i=n。++i) { start = n1。 for (c=i,f=HT[c].parent。 f!=0。 c=f,f=HT[f].parent) if (HT[f].lchild ==c) cd[start]=39。039。 else cd[start]=39。139。 HC[i]=(char *)malloc((nstart)*sizeof(char))。 strcpy(HC[i],amp。cd[start])。 printf(%s\n,HC[i])。 } free(cd)。 }
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1