如何构造哈夫曼树？借助口诀+两个特点

贪心算法：先挑小的叶子来构造，大的留到最后就能离根近一些

哈夫曼算法的步骤：根据n个给定的权值，构造有n个树的森林，n个树都只有1个根结点，其权值给定（森林中有几个树？给了几个权值就几个树，每个树都只有1个结点）

重复2，3步骤

直到只剩下一棵树结束

口诀：

例子：

1.构造森林全是根：一开始就用4个结点构造了4棵二叉树，构成一个森林（有几个叶子结点就有几棵树）

2.选用两小造新树：选2，4为他们两个增加一个双亲结点作为根，这个新树的根结点的权值是两个根结点权值的和，2+4=6

3.删除两小添新人：现在变成3棵树了，选5，6造一个新树，添加一个根结点，权值5+6=11

4.重复2，3剩单根：

错解：

我做错了

观察：

4个叶子结点构造新树，新树的根结点都是度为2的，它必有左右子树，因为我们选用了两小，一个做左子树，一个做右子树，所以新添加的结点都是度为2的，我们一开始的结点都是度为0的

包含n个叶子结点总共有多少个结点？2n-1

两两合并产生一个新的结点，如果有n个，一定会合并n-1次，最后才剩下一棵树，这n-1次合并就会产生n-1个结点，这n-1个结点都是度为2的结点，而度为0的结点是n个

再看一个例子：

总结：