常用二叉树

常用二叉树包括：二叉搜索树、堆、哈夫曼树、平衡二叉搜索树等
1、二叉搜索树（binary searching tree）又称二叉查找树，具有下列特性：
（1）左子树若非空，则左子树上所有节点的关键字均小于根节点的关键字；
（2）右子树若非空，则右子树上所有节点的关键字均大于根节点的关键字；
（3）左、右子树本身又是一个二叉搜索树；
时间复杂度为O(log2 n)，最差的时候是O（n),在二叉搜索树上查找比在集合或线性表上进行顺序查找的时间复杂度O(n)要好得多，二叉搜索树查找算法的空间复 杂度为O(1)。
二叉搜索树的删除结点的操作过程：
（1）删除叶子结点
此种删除操作很简单，只要将其双亲结点链接到它的指针去掉（即置为空）即可。
（2）删除单支结点
此种删除操作比较简单，因为该节点只有左子树或右子树一支，也就是说，其后继只有左孩子或右孩子一个。删除该结点是，只要将唯一的一个后继指针链接到它所在的链接位置即可。
（3)删除双支结点（关键是找他的前驱节点）
这种删除比较复杂，因为待删除的结点有两个后继指针，需要妥善处理。删除这种结点的常用方法是：首先把她的中序前驱结点（即中序序列中处于它前面的一个结点，该结点是其左子树中最右下的一个结点）的值赋给该结点的值域，然后再删除它的中序前驱结点，因它的中序前驱结点的右指针必为空，所以只要把中序前驱结点的左指针链接到中序前驱结点所在的位置即可。
2、堆（heap）
堆分为大根堆和小根堆。小根堆的特征：
（1）若树根节点存在左孩子，则根节点的值小于等于左孩子结点的值；
（2）若树根结点存在右孩子，则根节点的值也小于等于右孩子结点的值；
（3）以左孩子、右孩子为根的子树右个是一个堆；
大根堆的特征只是把条件改为“大于等于”即可。
堆是满足一定条件的完全二叉树（除最后一层以外全部满，最后一层从左到右排列，可以不满）。因为堆是完全二叉树所以适宜用顺序存储的方式。
向堆中插入一个元素：首先将该元素写入到堆尾，即堆中最后一个元素的后面，然后经调整为一个新堆。由于在原有对上插入一个新元素后，可能使以该元素的双亲结点为根的子树不为堆，从而使得整个树不为堆，所以必须调整使之成为一个堆。调整的方法很简单，若新元素小雨双亲结点的值，就让他们互换位置；新元素换到双亲位置后，使得以该位置为根的子树成为堆，但新元素可能还小于此位置的双亲结点的值，从而使上一层的双亲结点为根的子树不为堆还需按照上述方法继续调整，这样传递上去，直到以新位置的双亲结点为根的子树仍为一个堆或者调整到堆顶为止，从而得到整个完全二叉树。
在堆中删除一个元素就是删除堆顶的元素，留下的堆顶位置有堆尾元素填补，这样可以保持顺序存储的结构特点有不需要移动其他任何元素。具体操作是：将堆尾元素换到堆顶时，可能造成不为堆的情况，需要调整。将堆顶元素与他的两个子结点中的最小值比较，若大于他们中的最小值则与其对换，直到调整后的位置为根的子树成为一个堆或者调整到叶子结点为止。
堆中插入、删除等操作的时间复杂度是O(log2 n),最多为整个树的深度减一。
因为堆是完全二叉树，所以可以用递归的方法将其输出其时间复杂度为O(n)，空间复杂度O（log 2 n）;
3、哈夫曼树Huffman Tree（最优二叉树）
树的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权值的乘机和。
哈夫曼树是n个带全叶子结点构成的所有二叉树中带权路径长度（WPL）最小的二叉树。（权值越大的节点离树根越近的二叉树是最优二叉树）。
构造哈夫曼树的叙述：
（1）根据与n个权值对应的n个节点构成具有n棵二叉树的森林F={t1,t2,...tn}，每棵二叉树都只有一个权值的根节点，其左右子树均为空。
（2)在森林F中选出两颗根节点的权值最小的树作为一颗新的树的左右子树，且置新树的根节点的权值为其左右子树上根节点的权值之和。
（3)从F中删除构成新树的两棵树，并加入新的树到F中。
（4）重复（2）、（3）步每次减少一棵树，直到F中只含有一棵树为止，即得到所求的哈夫曼树。（过程中产生的新的树的权值如果跟旧的树的权值一样，则旧的树先参加消除，我的理解是这样可以减少编码长度，树的深度会减少）
在每一颗哈夫曼树中只存在双支结点和叶子结点，若叶子结点为n个，则双支结点必为n-1；
在编码中，采用等长编码时，传送电文的总长度会很大，若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可以缩短传送电文的总长度。不等长编码需要避免译码的二义性或多义性，需要使用无前缀编码，即只有当一个结点是另一个节点的双亲是，该结点的字符编码才会是另一个结点的字符比编码的前缀。
4、平衡二叉树（balanced binary tree）
该树是对二叉搜索树的改进。定义：若一颗二叉树中每个节点的左右子树的高度至多相差1，则称该树为平衡树。 每个节点的平衡因子只能是0,1，-1。
具有n个结点的平衡树高度在任何情况下绝不会比具有相同节点数的理想平衡树高出45%，因此，在平衡树上进行查找运算虽然比理想平衡树要慢一些，但通常比任意生成的二叉排序树快得多，时间复杂度的数量级任然是O(log2 n)；
当向平衡树中插入一个结点后破坏了其平衡性，则首先找出唯一一个最小不平衡子树，然后再调整整个子树中有关结点之间的连接关系，使之成为新的平衡子树。
最小不平衡子树是离插入节点最近、且平衡因子绝对值大于1的结点做根的子树