哈夫曼树的构造(哈夫曼树左边一定比右边小吗)

不一定。

哈夫曼树是一种带权路径最小的最优二叉树，它要解决的是权重最大的叶子结点到根结点路径最短，而不是像二叉排序树一样每个结点左右子树的数值大小有严格区分。因此哈夫曼树的左子树权值不一定比右边小。

比如一堆权值为1、3、4、6、7的叶子结点要构建成哈夫曼树，先找出最小的两个结点1、3，并为它们添加父结点a1，只要保证1、3是最小的结点就行，至于它们谁是a1的左子树还是右子树不重要。同理，此时a1的权值是4，与4结点的权值相同，为它们添加父结点a2时也无所谓谁左谁右。