哈夫曼樹左邊一定比右邊小嗎？

不一定。

哈夫曼樹是一種帶權路徑最小的最優(yōu)二叉樹，它要解決的是權重最大的葉子結(jié)點到根結(jié)點路徑最短，而不是像二叉排序樹一樣每個結(jié)點左右子樹的數(shù)值大小有嚴格區(qū)分。因此哈夫曼樹的左子樹權值不一定比右邊小。

比如一堆權值為1、3、4、6、7的葉子結(jié)點要構(gòu)建成哈夫曼樹，先找出最小的兩個結(jié)點1、3，并為它們添加父結(jié)點a1，只要保證1、3是最小的結(jié)點就行，至于它們誰是a1的左子樹還是右子樹不重要。同理，此時a1的權值是4，與4結(jié)點的權值相同，為它們添加父結(jié)點a2時也無所謂誰左誰右。