二叉排序树
二叉排序树(BST, binary sort tree)的定义：
- 若它的左子树不为空，则左子树上所有关键字的值均小于根关键字的值
- 若它的右子树不为空，则右子树上所以关键字的值均大于根关键字的值
- 左右子树又各是一颗二叉排序树.
说明：由二叉排序树的定义可以知道，如果输出二叉排序树的中序遍历序列，则这个序列是递增有序的。
二叉排序树的存储结构：
二叉排序树通常采用二叉链表进行存储，其结点类型定义与一般的二叉树类似。
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种情况。
- p结点为叶子结点，可直接删除
- p结点只有左子树没有右子树，或是只有右子树没有左子树。此时只需要将p删除，将原本的指针指向其仅有的左子树或者右子树即可。
- 假设p结点既有左子树又有右子树。此时可以将这种情况转化为1）或者2）中的情况，做法为：先沿着p的左子树根结点的右指针一直往右走，直到来到其右子树的最右边一个结点r（也可以沿着p的右子树根结点的左指针一直往左走，直到来到其左子树的最左边的一个结点）。然后将p中的关键字用r中的关键字代替。最后判断，如果r是叶子结点，则按照1）中的方法删除r；如果r是非叶子结点，则按照2）中的方法删除r（此时的r不可能是有两个子树的结点）。
