堆

堆：经过排序的完全二叉树，其中任一非叶子节点的值均不大于（或不小于）其左孩子和右孩子结点的值。

最大堆和最小堆是二叉堆的两种形式。

最大堆：根节点的键值是所有堆结点键值中最大者。

最小堆：根节点的键值是所有堆结点键值中最小者。

最大-最小堆：集结了他俩的优点。是最大层和最小层交替出现的二叉树，即最大层节点的儿子属于最小层，最小层节点的儿子属于最大层。以最大（小）层节点为根节点的子树保有最大（小）堆性质：根节点的键值为该子树结点键值中最大（小）项。

=======================================================

二叉排序树

（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；

（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；

（3）左、右子树也分别为二叉排序树；

=======================================================

平衡二叉树（AVL树）

 

它是一颗空树 或

它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树

常用算法：红黑树，AVL，Treap。

最小二叉平衡树的节点公式：F(n) = F(n-1)+F(n-2)+1

1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量

=======================================================

哈夫曼树

它是带权路径长度最小的二叉树。

哈夫曼树的构造：

有n个权值，则构造出哈夫曼树有n个叶子节点。

（1）将1……n看成是n棵树的集合；

（2）集合中选出两个根节点的权值最小的树合并，作为一颗新树的左右子树，且新树的根节点权值为其左右子树节点权值之和；

（3）从集合中删除选取的两棵树，并将新树加入集合

（4）重复2，3步骤，直到集合中只剩一颗树为止