哈夫曼樹(shù)是否唯一

哈夫曼樹(shù)不唯一，因?yàn)闆](méi)有限定左右子樹(shù)，并且有權(quán)值重復(fù)時(shí)，可能樹(shù)的高度都不唯一，唯一的只是帶權(quán)路徑長(zhǎng)度之和最小。哈夫曼樹(shù)(Huffman)樹(shù)又稱最優(yōu)二叉樹(shù)，是指對(duì)于一組帶有確定權(quán)值的葉子結(jié)點(diǎn)所構(gòu)造的具有帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成了兩結(jié)點(diǎn)之間的路徑，路徑上的分支個(gè)數(shù)稱為路徑長(zhǎng)度。二叉樹(shù)的路徑長(zhǎng)度是指由根結(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹(shù)中的葉子結(jié)點(diǎn)都有一定的權(quán)值，則可將這一概念。設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，則從根結(jié)點(diǎn)到每一個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與該葉子結(jié)點(diǎn)權(quán)值的乘積之和稱為二叉樹(shù)路徑長(zhǎng)度，記做：WPL=W1L1+W2L2+WnLn等等；其中：n為二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)；Wk為第k個(gè)葉子的權(quán)值；Lk為第k個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。

推薦度：

點(diǎn)擊下載本文 文檔為doc格式

導(dǎo)讀哈夫曼樹(shù)不唯一，因?yàn)闆](méi)有限定左右子樹(shù)，并且有權(quán)值重復(fù)時(shí)，可能樹(shù)的高度都不唯一，唯一的只是帶權(quán)路徑長(zhǎng)度之和最小。哈夫曼樹(shù)(Huffman)樹(shù)又稱最優(yōu)二叉樹(shù)，是指對(duì)于一組帶有確定權(quán)值的葉子結(jié)點(diǎn)所構(gòu)造的具有帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成了兩結(jié)點(diǎn)之間的路徑，路徑上的分支個(gè)數(shù)稱為路徑長(zhǎng)度。二叉樹(shù)的路徑長(zhǎng)度是指由根結(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹(shù)中的葉子結(jié)點(diǎn)都有一定的權(quán)值，則可將這一概念。設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，則從根結(jié)點(diǎn)到每一個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與該葉子結(jié)點(diǎn)權(quán)值的乘積之和稱為二叉樹(shù)路徑長(zhǎng)度，記做：WPL=W1L1+W2L2+WnLn等等；其中：n為二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)；Wk為第k個(gè)葉子的權(quán)值；Lk為第k個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。

哈夫曼樹(shù)不唯一，因?yàn)闆](méi)有限定左右子樹(shù)，并且有權(quán)值重復(fù)時(shí)，可能樹(shù)的高度都不唯一，唯一的只是帶權(quán)路徑長(zhǎng)度之和最小。

哈夫曼樹(shù)(Huffman)樹(shù)又稱最優(yōu)二叉樹(shù)，是指對(duì)于一組帶有確定權(quán)值的葉子結(jié)點(diǎn)所構(gòu)造的具有帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成了兩結(jié)點(diǎn)之間的路徑，路徑上的分支個(gè)數(shù)稱為路徑長(zhǎng)度。二叉樹(shù)的路徑長(zhǎng)度是指由根結(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹(shù)中的葉子結(jié)點(diǎn)都有一定的權(quán)值，則可將這一概念。

設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，則從根結(jié)點(diǎn)到每一個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與該葉子結(jié)點(diǎn)權(quán)值的乘積之和稱為二叉樹(shù)路徑長(zhǎng)度，記做：WPL=W1L1+W2L2+WnLn等等；其中：n為二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)；Wk為第k個(gè)葉子的權(quán)值；Lk為第k個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。