溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

數(shù)據(jù)結(jié)構(gòu)中赫夫曼樹

發(fā)布時(shí)間：2020-06-25 18:18:31 來源：網(wǎng)絡(luò) 閱讀：423 作者：IT_CREATE 欄目：編程語言

赫夫曼樹

以下程序在效率上有什么問題？
數(shù)據(jù)結(jié)構(gòu)中赫夫曼樹

上述代碼的流程圖：

數(shù)據(jù)結(jié)構(gòu)中赫夫曼樹

數(shù)據(jù)結(jié)構(gòu)中赫夫曼樹

如果我們把判斷流程改成下面的樣子，大家思考一下，比起上一種哪個(gè)好點(diǎn)？

數(shù)據(jù)結(jié)構(gòu)中赫夫曼樹

赫夫曼樹的定義與原理：
我們先把這兩顆二叉樹簡化成為葉子節(jié)點(diǎn)帶權(quán)的二叉樹。
注：樹節(jié)點(diǎn)間的連線相關(guān)的數(shù)叫做權(quán)。

數(shù)據(jù)結(jié)構(gòu)中赫夫曼樹
節(jié)點(diǎn)的路勁長度：
——從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的連線數(shù)。
樹的路徑長度：
——樹中每一個(gè)葉子節(jié)點(diǎn)的路徑長度之和。
節(jié)點(diǎn)帶權(quán)路徑長度：
——節(jié)點(diǎn)的路徑長度與該節(jié)點(diǎn)權(quán)值的乘積。
樹的帶權(quán)路徑長度：
——WPL（weighted Path Length）是樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和。

構(gòu)造赫夫曼樹的方法：
1、 在森林中選出根節(jié)點(diǎn)權(quán)值最小的二叉樹（小在左， 右在大）。
2、 合并兩個(gè)選出的二叉樹，增加一個(gè)新的節(jié)點(diǎn)，作為新二叉樹的根，權(quán)值為左右孩子權(quán)值的和。
3、 重復(fù)上述2步。
數(shù)據(jù)結(jié)構(gòu)中赫夫曼樹

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手