很多时候会去忘记，你真正在乎的，是什么、、、
set 就是用BST来维护集合的一个容器，书上根本没讲、、、、
定义：二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树。（4）中序遍历二叉排序树，所得的中序序列是一个递增的有序序列。
BST的平均时间复杂度为O（log2n），最坏的情况下，会增加至O（n），在刚开始接触BST的时候，我一直觉得是O（n）了 =。= ，那么问题来了，（挖掘机技术到底哪家强）
怎么去优化呢？我觉得会在以后的二叉平衡树（最坏时间复杂度为 log2n ）之类的巴拉巴拉的会讲到、、
建树：（这里仅说明整数序列的建树）对于关键字序列不同，生成的二叉排序树可能不同！(见附 1) 过程：将要插入的与根节点比较，小则归到左子树中，大则归到右子树中，该过程也不难理解的吧，这样经过递归之后，可以建成一个有序的树。代码如下
typedef struct node
{
int key;
struct node *l, *r;
}bst_node;
bool insert(bst_node * &p, int k) // 这里的引用传递到现在才弄懂，也是醉了、、
{
if(p == NULL) // 若原树为空，则将新插入的元素作为根节点
{
p = (bst_node *)malloc(sizeof(bst_node));
p -> key = k;
p -> l = p -> r = NULL;
return true;
}
else if(k == p -> key)
{
return false;
}
else if(k < p -> key)
return insert(p -> l, k);
else
return insert(p -> r, k);
}
bst_node * creat(int a[], int n)
{
int i = 0;
bst_node *bt = NULL;
while(i < n)
{
insert(bt, a[i]);
i ++;
}
return bt;
}
查找：查找的过程，其实更像是二分查找，对于关键字序列不同的树，平均查找长度也不同，时间复杂度为O（log2n）.
bst_node * search(bst_node *bt , int k)
{
if(bt == NULL || bt -> key == k)
return bt;
if(k < bt -> key)
return search(bt -> l, k);
else
return search(bt -> r, k);
}
删除：个人感觉删除这里还是比较难理解的，不仅仅是指针的移动，删除之前必须进行查找，要考虑多种情况（见附 2），个人感觉海狮模拟一遍比较好，书上的模拟占了好大的一部分、、、
1、需要删除的节点没有左儿子，那么就把右儿子提上去。
2、需要删除的节点的左儿子没有右儿子，那么就把左儿子提上去。
3、以上两种都不满足，就把左儿子子孙中最大的节点提到需要删除的节点上。
下面摘自书上，感觉写的有点麻烦啊、、、
int delete(bst_node * &bt, int k)
{
if(bt == NULL)
return 0;
else
{
if(k < bt -> key)
return delete(bt -> l, k);
else if(k > bt -> key)
return delete(bt -> r, k);
else
{
delete_(bt);
return 1;
}
}
}
void delete_(bst_node * &p)
{
bst_node * q;
if(p -> r == NULL)
{
q = p;
p = p -> l;
free(q);
}
else if(p -> l == NULL)
{
q = p;
p = p -> r;
free(q);
}
else
delete1(p, p -> l);
}
void delete1(bst_node *p, bst_node * &r)
{
bst_node * q;
if(r -> r == NULL)
delete1(p, r -> r);
else
{
p -> key = r -> key;
q = r;
r = r -> l;
free(q);
}
}
附 ：
1、 两个序列分别为｛5， 2， 1， 6， 7， 4， 8， 3， 9｝，｛1， 2， 3， 4 ，5 ， 6， 7， 8， 9｝
如下图：
2、 不同点的删除方法。
如下图：
