树的知识点整理
AVL树是具有平衡条件的二叉查找树，必须保持树的深度是O(logN)。最简单的是要求左右具有相同的高度。
哈夫曼树是一种带权路径长度（WPL）最短的二叉树，也称为最优二叉树。将字符作为叶子节点，每个叶子结点有一个权值，权值越小，叶子结点所在的层树就越大，叶子结点的带权路径长度的计算规则是：深度*权值；二叉树的带权路径长度为所有叶子结点的带权路径长度之和。
构建哈夫曼树的方法：
一般可以按下面步骤构建：
1，将所有左，右子树都为空的作为根节点。
2，在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。
3，从森林中删除这两棵树，同时把新树加入到森林中。
4，重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。
哈夫曼编码：不等长编码，字符出现的频率作为权值，权值越大，编码长度越小。