二叉樹哈夫曼樹形狀唯一嗎
二叉樹哈夫曼樹形狀不唯一。
哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。從哈夫曼樹的構(gòu)造方式就知道，它的形狀不是唯一的。我們舉例說明。
比如有權(quán)值分別為1、2、2、3的四個結(jié)點要構(gòu)建哈夫曼樹。先選擇最小的1和2，為它們分配父結(jié)點a。1可以是a的左子結(jié)點也可以是右子結(jié)點，2亦然，因此從第一步，樹形狀就不唯一了。a的權(quán)值是3，那么，另一個權(quán)值為2的結(jié)點可以和a組合，也可以和另一個權(quán)值為3的結(jié)點組合，樹形狀再次多了一種可能。
綜上，二叉樹哈夫曼樹形狀不唯一。
已知權(quán)值集合，如何求其構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和，只求過程，急急急
首先需要構(gòu)造哈夫曼樹，其構(gòu)造規(guī)則是選擇兩個權(quán)值最小的結(jié)點，作為左右結(jié)點構(gòu)造成一顆樹，這顆樹的根權(quán)值為左右子樹權(quán)值大小的和，這個新的權(quán)值放入到原有的權(quán)值集合中，左右子樹權(quán)值刪除掉循環(huán)上述過程，直到只有一棵樹為止。帶權(quán)路徑長度就是權(quán)值結(jié)點所在的高度*權(quán)值大小帶權(quán)路徑長度之和就是將所有上面的所有求知結(jié)果匯總
并計算出所構(gòu)造的哈夫曼樹的帶權(quán)路徑長度
由于題目沒有給出具體的字符集和出現(xiàn)頻率，無法進行實際的構(gòu)造和計算。哈夫曼樹的帶權(quán)路徑長度是指樹中所有葉子節(jié)點的權(quán)值乘以該葉子節(jié)點到根節(jié)點的路徑長度之和。
如何實現(xiàn)哈夫曼樹
將n個權(quán)值看作有n棵二叉樹的森林，其中每棵二叉樹只有一個根節(jié)點，沒有子樹在森林中選取兩顆根節(jié)點的權(quán)值最小的二叉樹作為子樹形成一棵新二叉樹，并且新二叉樹的根節(jié)點為子樹根節(jié)點權(quán)值之和從森林中刪除這兩二叉樹新二叉樹加入森林重復(fù)2、3、4，until森林中僅剩一棵樹，即為哈夫曼樹
哈夫曼樹的根結(jié)點
根節(jié)點為最大值存在的節(jié)點，碼率最大。
14個值組成哈夫曼樹共有多少節(jié)點
14個帶權(quán)葉子組成的哈夫曼樹，共有27個結(jié)點。
根據(jù)哈夫曼樹的構(gòu)造規(guī)則，最開始這14個結(jié)點全是離散的，可看為14棵單獨的樹。不斷找到權(quán)值最小的兩棵樹，添加一個度為2的分支結(jié)點把它們組合起來，直到最后只有一棵樹。
因此對于哈夫曼樹，只有度為0的葉子和度為2的結(jié)點，且二叉樹中總是度為0的結(jié)點比度為2的結(jié)點多一個，因此14個葉子結(jié)點的哈夫曼樹有13個度為2的結(jié)點，它的總結(jié)點數(shù)是14+13=27個。
