"在哈夫曼樹中，權值相同的葉結點都在同一層上" 這種說法錯誤.因為,權值相同的葉結點也可能在不同層.看這樣的一個例子,有五個葉結點,權值分別是 {1,1,1,1,1}, 也就是權值都是1.儘管葉結點的權值都是1,但是,不一定都在同一層,詳細分析過程如下:(1) 從小到大排序 1 1 1 1 1 (這是有序序列)(2) 每次提取最小的兩個結點,取結點1和另一個結點1,組成新結點N2,其權值=1+1=2, 結點1作為左分支,而另一個結點1就作為右分支.(3) 將新結點N2放入有序序列,保持從小到大排序: 1 1 1 N2(4) 重複步驟(2),提取最小的兩個結點,結點1和另一個結點1,組成新結點N2,其權值=1+1=2, 結點1作為左分支,而另一個結點1就作為右分支.(5) 將新結點N2放入有序序列,保持從小到大排序: 1 N2 N2(6) 重複步驟(2),提取最小的兩個結點,結點1與N2組成新結點N3,其權值=1+2=3, 結點1的數值較小,作為左分支,N2就作為右分支.(7) 將新結點N3放入有序序列,保持從小到大排序: N2 N3(8) 重複步驟(2),提取剩下的兩個結點,N2與N3組成新結點N5,其權值=2+3=5, 數值較小的N2作為左分支,N3就作為右分支. 最後得到"哈夫曼樹": N5 / \ N2 N3 / \ / \ 1 1 1 N2 / \ 1 1 從上圖可知,儘管葉結點的權值都是1,但是,不一定都在同一層. 有的葉結點在最後一層,而有的在倒數第二層.
"在哈夫曼樹中，權值相同的葉結點都在同一層上" 這種說法錯誤.因為,權值相同的葉結點也可能在不同層.看這樣的一個例子,有五個葉結點,權值分別是 {1,1,1,1,1}, 也就是權值都是1.儘管葉結點的權值都是1,但是,不一定都在同一層,詳細分析過程如下:(1) 從小到大排序 1 1 1 1 1 (這是有序序列)(2) 每次提取最小的兩個結點,取結點1和另一個結點1,組成新結點N2,其權值=1+1=2, 結點1作為左分支,而另一個結點1就作為右分支.(3) 將新結點N2放入有序序列,保持從小到大排序: 1 1 1 N2(4) 重複步驟(2),提取最小的兩個結點,結點1和另一個結點1,組成新結點N2,其權值=1+1=2, 結點1作為左分支,而另一個結點1就作為右分支.(5) 將新結點N2放入有序序列,保持從小到大排序: 1 N2 N2(6) 重複步驟(2),提取最小的兩個結點,結點1與N2組成新結點N3,其權值=1+2=3, 結點1的數值較小,作為左分支,N2就作為右分支.(7) 將新結點N3放入有序序列,保持從小到大排序: N2 N3(8) 重複步驟(2),提取剩下的兩個結點,N2與N3組成新結點N5,其權值=2+3=5, 數值較小的N2作為左分支,N3就作為右分支. 最後得到"哈夫曼樹": N5 / \ N2 N3 / \ / \ 1 1 1 N2 / \ 1 1 從上圖可知,儘管葉結點的權值都是1,但是,不一定都在同一層. 有的葉結點在最後一層,而有的在倒數第二層.