數(shù)據(jù)結(jié)構(gòu)4樹與二叉樹(編輯修改稿)
2025-06-20 11:45 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 7 5 2 4 (1) WPL=7*2+5*2+2*2+4*2=36 d c a b 2 4 7 5 (2) WPL= 4* 2+7*3+5*3+2*1=46 a b c d 7 5 2 4 (3) WPL=7*1+5*2+2*3+4*3=35 例：將百分制成績(jī)轉(zhuǎn)換成 5級(jí)分制成績(jī) if ( a60 ) b = ―bad‖ 。 else if ( a70 ) b = ―pass‖ 。 else if ( a80 ) b = ―general‖ 。 else if ( a90 ) b = ―good‖ 。 else b = ―excellent‖ 分?jǐn)?shù) 比例 059 6069 7079 8089 90100 a80 a70 a60 a90 不及格 及格 中等 良好 優(yōu)秀 Y Y Y Y N N N N 設(shè)有 10000個(gè)記錄 需 31500次比較 需 22021次比較 定理： ?設(shè) T為帶權(quán) w1≤ w2 ≤ …… ≤ wn 的最優(yōu)樹 則 a ) 帶權(quán) w1,w2的葉子 Vw1,Vw2是兄弟 b ) 以 Vw1,Vw2為兒子的分枝點(diǎn)，其通路長(zhǎng)度最長(zhǎng)。 ?設(shè) T為帶權(quán) w1≤ w2 ≤ …… ≤ wn 的最優(yōu)樹，若將以帶權(quán) w1,w2 的樹葉為兒子的分枝點(diǎn)改為帶權(quán) w1+w2的樹葉，得到新樹 T‘， 則 T‘也是最優(yōu)樹。 Huffman樹的 構(gòu)造 1. 根據(jù)給定的 n個(gè)權(quán)值 {w1,w2,……wn} 構(gòu) 成 n棵二叉樹的集合 F={T1,T2,……Tn} ，其中每棵二叉樹 Ti中 只有一個(gè)帶權(quán)為 Wi的 結(jié)點(diǎn)，其左右子樹均為空。 2. 在 F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹， 且 置新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。 3. 在 F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中 4. 重復(fù) 3上述兩步， 直到 F只含一棵樹為止，這棵樹即 為 哈夫曼樹。 例 a 7 b 5 c 2 d 4 a 7 b 5 c 2 d 4 6 a 7 b 5 c 2 d 4 6 11 a 7 b 5 c 2 d 4 6 11 18 例 w={5, 29, 7, 8, 14, 23, 3, 11} 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 8 8 7 15 14 29 23 3 5 8 11 11 3 5 8 19 14 29 23 8 7 15 11 3 5 8 19 29 23 14 8 7 15 29 29 14 8 7 15 29 11 3 5 8 19 23 42 11 3 5 8 19 23 42
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1