查找算法：二叉排序树

二叉排序树，又称二叉查找树，是一种对排序和查找都很有用的特殊二叉树

1. 定义
   二叉排序树或者是一棵空树，或者具有以下定义：
   1）若左子树不为空，左子树上所有结点值均小于根结点值；
   2）若右子树不为空，右子树上所有结点值均大于根结点值；
   3）左右子树也分别为二叉排序树。

递归定义。有定义可得性质：中序遍历二叉树可得到结点递增的有序序列。

2. 查找
   模仿折半查找易得非递归查找算法，以下给出递归形式

BSTree searchBST(BSTree T, KeyType key) {
  if (!T || T.data == key) return T;  // 找到则返回T，找不到则返回空
  else if (T.data < key) return SearchBST(T.right, key);
  else return SearchBST(T.left, key);
}

算法分析：
二叉排序树上的查找和折半查找相差不大。但二叉排序树可更好地维护表的有序性，无需移动记录，只需移动指针即可完成插入和删除操作。
因此，对需要经常进行插入、删除和查找运算的表，采用二叉排序树比较好。

3. 插入
   当树中不存在关键字等于key的结点时才进行插入。
   新插入的结点一定是一个新添加的叶子结点（？一定是叶子结点？），且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子节点。

void insertBST(BSTree T, ElementType e) {
  if (!T) {
    S = new BSTNode;
    S.data = e;
    S.lchild = S.rchild = NULL;
    T = S;
  }
  else if (T.data > e.data) insertBST(T.lchild, e);
  else if (T.data < e.data) insertBST(T.rchild, e);
}

4. 创建

void createBST(BSTree T) {
  T = NULL;
  cin>>e;  // 输入e
  while（e.key != ENDFLAG）{ // ENDFLAG为自定义常量，作为输入结束标志
    insertBST(T, e);
    cin>>e;
  }
}

5. 删除(待补充......)