哈夫曼树个人理解:

想要搞懂

如何将几个数值（也叫权值）

构造成一颗哈夫曼树？

=>只需要记住：在构造哈夫曼树的每一步中，

都是

挑选其中最小的两个权值！

（特别注意，在每次开始挑选的过程中，其中备挑选的权值里面，上一次已经完成合并的树的根节点的值，也要参与到当前此前此次备挑选的权值中=>这是很多初次接触哈夫曼树的学生都会忽视的地方）

即:

(更加简洁的表达)

1.以权值作为根节点构建n棵二叉树,组成森林

2.以森林中选出2个根节点最小的树合并,作为一棵新树的左右子树,且新树的根节点为其左右子树根节点之和

3.从森林中删除刚才选取的2棵树,并将新树加入森林

4.重复2,3步骤,知道森林只剩一棵树为止,该树即为赫夫曼树

当出现两个相同的权值该如何继续合并?

当出现已合并树的根节点的值与为合并树的权值一样时,优先将未合并的值合并

=>即A(已合并),A(未合并),C(C

当然,如果出现备选只有A(已合并),A(未合并)=>直接将两者合并即可

AAC非常少见,更多情况下是AA

（注：AAC，AA这种说法,仅仅是为了举例子）

再集中思考一下:

为什么会出现AAC,与AA这两种情况?

①当在某一次结合中,出现C

②当在某一次结合中,出现A(已合并)=A(未合并)<其他任何一颗”权值”时,自然就把A(已合并)与A(未合并)结合起来了

下面用绘图的方式来举几个例子：

例子1:

例子2:

例子3: