二叉排序树

左边子树均小于本节点，右子树均小于本节点，用中序遍历可以从小到大排序

查找

二叉树非空时，查找根节点若相等这查找成功，若不等，则小于根节点查找左子树，大于根节点查找右子树，当查找到叶节点人没有查找到相应的值，则查找失败。

插入

若二叉排序树为空，则直接插入节点
若二叉排序树非空，当值小于根节点时，插入左子树，当值大于根节点时，插入右子树，当值等于根节点时不进行插入

构造

读入一个元素并建立节点，若二叉树为空将其作为根节点，若二叉树非空，当值小于根节点时，擦汗如左子树，当值大于根节点时，插入右子树，当值等于根节点时不进行插入。

删除

若删除的节点时叶子节点直接删除，

若被删除的节点只有一棵子树，则让其子树成为其父节点的子树

若被删除的节点有两个子树，则让其的中序序列直接后继替代z，并且删去直接后继节点

删除后插入

删除后插入得到的二叉排序树可能时不相同的

查找效率

查找长度：平均查找长度取决于树的高度，

平衡二叉树

任意节点的平衡因子绝对不超过1
平衡因子：左子树高度-右子树高度

计算高度为h的节点数

N0和N1开始推导就可以求出任意高度节点的数量

平衡二叉树的判断

插入

右单旋转

左单旋转

先左后右双旋转

先右后左双旋转

哈夫曼树

路径长度：路径上所经历边的个数
结点的权：结点被赋予数值
树的带权路径长度：所有叶节点的带权路径长度之和
哈夫曼树：带权路径最小的二叉树

构造

把权值最小的两个根节点作为孩子结点来合成新的树

性质

哈夫曼树的应用

构造前缀编码，通过固定长度来编码浪费空间，而可变长长度编码会出现错误，所以需要利用哈夫曼树构造出前缀编码

构造前缀编码

我们把字母出现的次数，定义为字母的权值，每个字母定义为一个结点，通过构造哈夫曼树的方法来讲所有的结点组成一棵树，从根节点开始遍历，左孩子路径为0，右孩子路径为1，每个叶节点的路径序列就是前缀编码。