哈夫曼樹唯一嗎
來源:百花花卉谷 閱讀:2.02W 次
哈夫曼樹不是唯一。因爲沒有限定左右子樹,並且有權值重複時,可能樹的高度都不唯一,唯一的只是帶權路徑長度之和最小。哈夫曼樹(Huffman)樹又稱最優二叉樹,是指對於一組帶有確定權值的葉子結點所構造的具有帶權路徑長度最短的二叉樹。
從樹中一個結點到另一個結點之間的分支構成了兩結點之間的路徑,路徑上的分支個數稱爲路徑長度。二叉樹的路徑長度是指由根結點到所有葉子結點的路徑長度之和。如果二叉樹中的葉子結點都有一定的權值,則可將這一概念。
設二叉樹具有n個帶權值的葉子結點,則從根結點到每一個葉子結點的路徑長度與該葉子結點權值的乘積之和稱爲二叉樹路徑長度,記做:WPL=W1L1+W2L2+WnLn等等;其中:n爲二叉樹中葉子結點的個數;Wk爲第k個葉子的權值;Lk爲第k個葉子結點的路徑長度。
熱門內容
大家都在看
最近更新