基本数据结构介绍

二叉查找树：
性质：设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点，则key[x]>=key[y]。如果y是x的右子树中的一个结点，则key[x]<=key[y]。
中序遍历算法 可以按顺序输出树中的所有关键字。
因为一棵子树输出时，根的关键字介于左子树和右子树的关键字之间，前序遍历中根的关键字在其左右子树中的关键字之前输出。后序遍历中根的关键字在其左右子树中的关键字之后输出。
{
  access(leftnode);
  access(node);
  access(rightnode);
}
最大关键字与最小关键字，根椐二叉树的性质，最小关键字是子树中沿着left指针查找，最左边的一个叶子节点。最大关键字是子树中沿着right指针查找，最右边的一个叶子节点。

根的前趋和后继：
前趋应该是小于当前根节点关键字中最大的值，后继应该是大于当前根节点关键字中最小的值。
根据二叉树的特点，当前根节点的左子树中的关键字都小于根节点关键字，右子树中的关键字都大于根节点关键字（假设关键字各不相同）。再根据最大关键字和最小关键字的特点，那么当前节点的前趋是左子树中沿right指针查找的最右边的叶子节点，后继是右子树中沿left指针查找最左边的叶子节点。

执行的基本操作时间与树的高度成正比。

插入：
比较节点左右子节点关键字，决定查找方向，直到查找节点为NULL时，这时NULL值的位置就为要插入的节点位置。

y <- NULL 用于保留当前非空节点位置
x <- root[T]
while x!=NULL
   do y <- x
        if key[z] < key[x]
        then x <- left[x]
        else x <- right[x]

p[z] <- y
if y = NULL
   then root[T] <- z
   else if key[z] < key[y]
        then left[y] <- z
        else right[y] <- z

这种插入方式会出现一个极端的情况，假设插入的关键字是有顺序的，这时会出现一棵每个节点最多有一个子节点，且都为左或是右节点的链表。

删除
分为三种情况：
1、待删除的节点（z）无子节点，直接删除就可以了
2、待删除的节点有一个子节点，只需要将其父节点和其子节点相连就可以了。
3、待删除的节点有两个节点，这时使用该节点的后继(y)代替该节点（后继节点(y)的连接应该先被删除否则其(y)父节点还会引用它，然后将关键字代替待删节点(z)的关键字，待删除的节点(z)左右节点的连接不变。）在删除后继(y)时，肯定为1，2中的一种情况。因此不会需要递归删除（如果二叉查找树中的某个结点有两个子女，则其后断没有左子女，其前趋没有右子女）。