关于二叉树总结的一些公式：

满二叉树节点数,k代表树的高度N个节点可以组成多少个不同的二叉树：其实就是卡特兰数公式N个节点的完全二叉树高度是 logn + 1 或者 log 2n（以2为底）完全二叉树的叶节点a，总节点数是b，他们的关系是满k叉树,深度为h的数（根节点深度为0）的节点个数

哈夫曼树：哈夫曼树（Huffman Tree）是在叶⼦结点和权重确定的情况下，带权路径⻓度最⼩的⼆叉树，也被称为最优⼆叉树。

构造哈夫曼树方法：

1.先把所有的数据节点，从⼩到⼤依次排列，成为⼀个有序列表

2.取出前⾯两个节点，让这两个节点的权重数据相加得到⼀个和，令这个和为根节点，这个两个节点的⼩的为其左孩⼦，⼤的为其右孩⼦

3.令这个和节点替换掉前⾯的两个节点，并重新排序，⽣成⼀个有序列表

4.不断重复第⼆步，第三步。直到所有的节点都被⽤完，得到⼀个排序结果，此时⽣成的⼆叉树，就是哈夫曼树。

举例：

4个点，a、b、c、d，权值分别为7、5、2、4。构造一棵哈夫曼树

构树过程：因为4个点，所以合并3次（n个点，合并n-1次）

第⼀步：选根权值最⼩的两棵树2（c）和4（d）合并，新树的根节点为6，如图(b)；

第⼆步：选根权值最⼩的两棵树5（b）和6合并，新树的根节点为11，如图(c)；

第三步：选根权值最⼩的两棵树7（a）和11合并，新树的根节点为18，如图(c)；

带权路径计算方法：所有节点的权重*路径长度之和

哈夫曼编码：先根据哈夫曼树最小带权路径构造方法，构造一颗哈夫曼树，然后从哈夫曼树根节点开始，对左⼦树分配码“0”，右⼦树分配码“1”，⼀直到达叶⼦节点为⽌，然后从树根沿每条路径到达叶⼦结点的代码排列起来，便得到了哈夫曼编码。（也有可能左边分配1，右边分配2，所以哈夫曼编码不确定除非明确表明那边子树标记为0和1，但是长度一定是确定的）

例如上图构造好哈夫曼树以后，ACDEM的哈夫曼编码分别为：

E：000

M：001

C:01

A:10

D:11

哈夫曼树和哈夫曼编码采用的都是贪心策略，让带权路径最小或者编码最短。