二叉排序树

二叉排序树(BST, binary sort tree)的定义：

1. 若它的左子树不为空，则左子树上所有关键字的值均小于根关键字的值
2. 若它的右子树不为空，则右子树上所以关键字的值均大于根关键字的值
3. 左右子树又各是一颗二叉排序树.

说明：由二叉排序树的定义可以知道，如果输出二叉排序树的中序遍历序列，则这个序列是递增有序的。

二叉排序树的存储结构：
二叉排序树通常采用二叉链表进行存储，其结点类型定义与一般的二叉树类似。

typedef struct TreeNode {
  int key;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode;

二叉排序树的算法

1.查找关键字：

BTNode *BSTSearch(BTNode *bt, int key) {
  if (bt == NULL)
    return NULL;
  else  {
    if (bt->key == key)
      return bt;
    else if (key < bt->key)
      return BSTSearch(bt->lchild, key);
    else
      return BSTSearch(bt->rchild, key);
  }
}

2.插入关键字：

二叉排序树是一个查找表，插入一个关键字首先要找到插入位置。对于一个不存在于二叉排序树中的关键字，其查找不成功的位置即为该关键字的插入位置。

int BSTInsert(BTNode *&bt, int key)//因为插入，bt要改变，所以要用引用型指针
{
  if (bt == NULL)  {
    bt = (BTNode *)malloc(sizeof(BTNode));
    bt->lchild = bt->rchild = NULL;
    bt->key = key;
    return 1;
  }
  else {
    if (bt->key == key)
      return 0;
    else if (bt->key < key)
      return BSTInsert(bt->lchild, key);
    else 
      return BSTInsert(bt->rchild, key);
  }
}

说明：在二叉排序树中插入的关键字均存储在新创建的叶子上，由于找到的插入位置总是在空指针域上，因此在空指针域上连接的一个新结点必为叶子结点。

3.二叉排序树的构造算法：

二叉排序树的构造只需要建立一棵空树，然后将关键字逐个插入到空树中即可构造一棵二叉排序树。

void CreateBST(BTNode *&bt, int key[ ], int n) {
  int i;
  bt = NULL;
  for (i = 0; i < n; ++i)
    BSTInsert(bt, key[i]);
}

4.删除关键字的操作：

假设二叉排序树上被删除结点为p，f为其双亲结点，则删除结点p的过程分为以下3种情况。

1. p结点为叶子结点，可直接删除
2. p结点只有左子树没有右子树，或是只有右子树没有左子树。此时只需要将p删除，将原本的指针指向其仅有的左子树或者右子树即可。
3. 假设p结点既有左子树又有右子树。此时可以将这种情况转化为1）或者2）中的情况，做法为：先沿着p的左子树根结点的右指针一直往右走，直到来到其右子树的最右边一个结点r（也可以沿着p的右子树根结点的左指针一直往左走，直到来到其左子树的最左边的一个结点）。然后将p中的关键字用r中的关键字代替。最后判断，如果r是叶子结点，则按照1）中的方法删除r；如果r是非叶子结点，则按照2）中的方法删除r（此时的r不可能是有两个子树的结点）。