二叉排序树（BST）
也称为二叉查找树。二叉排序树或者为空树，或者为非空树，当为非空树时，满足（递归定义）：
若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字；若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字；左子树、右子树本身也分别是一棵二叉排序树。
组织内存索引
二叉排序树是适用于内存储器的一种重要树形索引（常用红黑树、伸展树等以维持平衡）外存常用B/B+数
中序遍历序列：1、2、3、4、5、7、8、10、16（依次递增）
左子树结点值
<
<
<根结点值
<
<
<右子树结点值
二叉排序树中序遍历序列是一个递增有序序列
查找
二叉树非空时，查找根结点，若相等则查找成功；若不等，则当小于根结点值时，查找左子树；当大于根结点值时，查找右子树；当查找到叶子结点仍没找到相应的值，则查找失败。
BSTNode *BST_Search(BiTree T, ElemType key, BSNode *&p){ // 指针引用
p=NULL;
while(T!=NULL && key!=T->data){
p=T;
if(key<T->data)
T=T->lchild;
else
T=T->rchild;
}
return T;
}
插入
若二叉排序树为空，则直接插入结点；若二叉排序树非空，当值小于根结点时，插入左子树；当值大于根结点时，插入右子树；当值等于根节点时，不进行插入。
int BST_Insert(BiTree &T, KeyType k){
if(T==NULL){
T=(BiTree) malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;
}
else if(k==T->key)
return 0;
else if(k<T->key)
return BST_Insert(T->lchild,k);
else
return BST_Insert(T->rchild,k);
}
构造
读入一个元素并建立结点，若二叉树为空将其作为根结点；若二叉排序树非空，当值小于根结点时，插入左子树；当值大于根结点时，插入右子树；当值等于根结点时，不进行插入。
void Create_BST(BiTree &T, KeyType str[], int n){
T=NULL;
int i=0;
while(i<n){
BST_Insert(T,str[i]);
++i;
}
}
构造二叉排序树时，即使插入的值相同，但如果插入顺序不同，则构造完成的二叉排序树也不同
删除
若被删除的结点
z
z
z是叶子结点，则直接删除；若被删除的结点
z
z
z有一棵子树，则让
z
z
z的子树成为
z
z
z父结点的子树，代替
z
z
z结点；若被删除的结点
z
z
z有两棵子树，则让
z
z
z的中序序列直接后继代替
z
z
z，并删去直接后继结点。
中序遍历序列永远是递增的
问题
在二叉排序树中删除并插入某个结点，得到的二叉排序树是否与原来相同？
查找效率
平均查找长度（ASL）取决于树的高度：
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)
最坏的情况：
O
(
n
)
O(n)
O(n)，即构造序列有序的情况
A
S
L
=
(
1
+
2
⋅
2
+
3
)
/
4
=
2
ASL=(1+2 \cdot 2+3)/4=2
ASL=(1+2⋅2+3)/4=2
1
1
1：表示只经历了一个根结点
2
⋅
2
2\cdot 2
2⋅2：表示有两个结点（1、4）经历了2个结点
3
3
3：表示只有一个结点（3）经历了3个结点
4
4
4：结点总数
