一、树表的查找
1.//代码效果参考：http://www.lyjsj.net.cn/wz/art_23975.html
概念当表的插入、删除操作比较频繁时，为维护表的有序性，需要移动表中很多记录。需要适用动态查找表—几种特殊的树
表结构在查找过程中动态生成，对于给定key，若表中存在，则成功返回；否则，插入关键字等于key的记录。
有：二叉排序树、平衡二叉树、红黑树、B-树、B+树、建树
2.二叉排序树
也称二叉搜索树、二叉查找树，
1.定义：
二叉排序树或是空树，或是满足以下性质的二叉树：
1.若其左子树非空，则左子树上所有结点的值均小于根结点的值
2.若右子树非空，则右子树上所有结点的值均大于等于根结点的值
3.其左右子树本身又各是一颗二叉排序树
其中左子树上所有结点的值都小于根结点的值，右子树上所有结点的值都大于等于根结点的值。
每个子节点也都遵循整个定义
对二叉排序树进行中序遍历可以得到一个按关键字从小到大的有序表
2.查找算法：
类似于二分法。
typedef struct //代码效果参考：http://www.lyjsj.net.cn/wx/art_23973.html
{ // 定义二叉树结点结构KeyType key // 关键字项
lnfoType otherinfo // 其他数据域
}ElemType
// 定义二叉树结构
typedef struct BSTNode {
ElemType data; // 数据域
struct BSTNode lchild， rchild // 左右孩子指针
}BSTNode, *BSTree
BSTree T
//查找算法-递归
BSTree SearchBST(BSTree T,KeyType key) {
if((!T) || key == T->data.key) return T
else if(key data.key）)
return SearchBST(T->lchid，key) // 继续在左子数中查找
else return SearchBST(T -> rchild, key) // 继续在右子树中继续查找
}
思路：
1.若二叉排序树为空，则查找失败，返回空指针。
2.若非空，将给定值key与根结点的关键字进行比较，类似于二分查找法。
3.插入
思路：
1.若二叉树排序树为空，则插入结点作为根结点插入到空树中
2.若不为空，继续在其左、右子树上查找。
若树中已有，就不再插入.
若树中没有，查找直到某个叶子结点的左子树或右子树为空为止，则插入结点应为叶子结点的左孩子或右孩子
通过插入算法可以生成一个二叉排序树。一个无序序列可通过构造二叉排序树变成一个有序序列。，构造树的过程就是对无序序列//代码效果参考：http://www.lyjsj.net.cn/wx/art_23971.html
进行排序的过程。插入的结点均为叶子结点，无需移动其他结点，相当于在有序序列上插入记录二无需移动其他记录。4.删除
删除只能和删除结点，不能删除以结点为根的子树，且还要保证删除后所得二叉树仍满足二叉排序树的性质不变。
1.被删除的结点是叶子结点：直接删去该结点。
2.被删除的结点只有右子树或者只有左子树，用其右子树或者左子树替换
3.被删除的结点既有左子树又有右子树，找到删除结点的左子树中的最大值，将其替换删除结点（或者找右子树上最小的结点）
2.平衡二叉树（AVL树）
一颗平衡二叉树或者是空树，或者是具有下列性质的二叉排列树：
左子树与右子树的高度之差的绝对值小于等于1
左子树和右子树也是平衡二叉排列树。
给每一个结点附加一个数字，给出该结点左子树与右子树的高度差。整个数组称为结点的平衡因子(BF)
平衡因子 = 结点左子树 - 结点右子树的高度
根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能说-1，0，1
每一个结点的左右指数相减，都是0或者-1.
对于一颗有n个结点的AVL树，其高度保持在O（log2n）数量级，ASL也保持在O（log2n）量级。
当我们在平衡二叉树排序树上插入一个结点时，可能会破坏平衡二叉树使其失衡。需要重新调整。
1.平衡二叉树的失衡处理
平衡二叉树的四种失衡类型：
调整方案：
调整原则：降低树的高度，保存二叉排序树性质。
理解：将某个子树中 结点的值处于中间位置提升至根结点。几种失衡类型就是根据插入值的大小来决定的）
2.平衡二叉树的构建
每插入一个结点都进一次平衡调整。
