构建Huffman树的疑问
有5个叶子,其权分别为: 7, 8, 10, 16, 18.
Step1: 选权值最小的叶子构建一棵新二叉树, 其根结点的权为15;
Step2: 再权值10, 15构建一棵新二叉树, 其根结点的权为25;
此时, 我给出的二叉树原则是权值小的是左子树, 权值大的是左子树.但是与教材本例却与之相反.
我的问题是:10是step2的左子树还是右子树?
[解决办法]
Huffman树又叫最优二叉数,没有规定左右孩子哪个权值大哪个权值小.上面说的两种都可以.
[解决办法]
左子树
因为10 < 15
15为右子树
小的在左边 大的在右边
就像第一步里7 8 ，7在左 8在右
[解决办法]
王咏刚写过一个很不错的huffman数的介绍，很精彩。
