一、二叉搜索树的结构
二叉搜索树是能够高效的进行下列操作的数据结构。
1、插入一个数值
2、查询是否包含某个数值
3、删除某个数值
根据实现的不同，还可以实现其他各种各样的操作，是一种实用性很高的数据结构。二叉搜索树如何储存数值参 见下图、
二叉搜索树的例子
所有的节点，都满足左子树上的所有节点都比自己的小，而右子树上的所有节点都比自己大这一条件。
二叉搜索树能够高效的管理数的集合。例如，可以通过如下方法在上图的二叉搜索树中查询是否存在10.
1、根节点的数值是7，比10小，所以往右儿子节点走。
2、走到的节点的数值是15，比10大，所以往左儿子节点走。
3、走到的节点是10，因此10在集合中。
接下来，如何往数中插入新的数值呢？
如果我们按照查找数值的方法试图查找这个数值的节点，就可以知道其对应的节点所在位置，之后在那个位置插入新的节点即可。例如，我们需要插入数值6。和查找的方法类似，从根节点出发，通过“左—》右”两步，就可以知道6应该是5的右儿子，因此在5的右儿子的位置插入6的节点即可。
最后是删除数值。数值的删除比起之前提到的操作稍微麻烦一些。例如，我们要删除数值15。如果删除了15所在的节点，那么他的两个儿子10和17就悬空了。于是，把11提到15所在的位置就可以解决问题。
一般来说，需要根据下面几种情况分别进行处理。
1、需要删除的节点没有左儿子，那么就把右儿子提上去。
2、需要删除的节点的左儿子没有右儿子，那么就把左儿子提上去。
3、以上两种情况都不满足的话，就把左儿子的子孙中最大的节点提到需要删除的节点上。
二、二叉搜索树的复杂度
不论哪一种操作，所花得时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要O(log n) 的时间
三、二叉搜索树的实现
node *root = NULL;
root = =insert(root, 1);
find(root, 1);
//表示节点的结构体
struct node {
int val;
node *lch, *rch;
};
//插入数值x
node *insert(node *p, int x) {
if (p == NULL) {
node *q = new node ;
q-val = x;
q->lch = q->rch = NULL;
return q;
}
else {
if (x < p->val) p->lch = insert(p->lch, x);
else p->rch = insert(p->rch, x);
return p;
}
}
//查找数值x
bool find(node *p, int x) {
if (p == NULL) return false;
else if (x == p->val) return true;
else if (x < p->val) return find(p->lch, x);
else return find(p->rch, x);
}
//删除数值x
node *remove(node *p, int x) {
if (p == NULL) return NULL;
else if (x < p->val) p->lch = remove(p->lch, x);
else if (x > p->val) p->rch = remove(p->rch, x);
else if (p->lch == NULL) {
node *q = p->rch;
delete p;
return q;
}
else if (p->lch->rch == NULL) {
node *q = p->lch;
q->rch = p->rch;
delete p;
return q;
}
else {
node *q;
for (q = p->rch; q->rch->rch != NULL; q = q->rch);
node *r = q->rch;
q->rch = r->lch;
r->lch = p->lch;
r->rch = p->rch;
delete p;
return r;
}
return p;
}
下面使用set实现、
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
//插入元素
s.insert(1);
s.insert(3);
s.insert(5);
//查找元素
set<int> :: iterator ite;
ite = s.find(1);
if (ite == s.end()) puts("not found");
else puts("found");
ite = s.find(2);
if (ite == s.end()) puts("not found");
else puts("found");
//删除元素
s.erase(3);
//其他查找元素的方法
if (s.count(3) != 0) cout << "found" << endl;
else cout << "not found" << endl;
//遍历所有元素
for (ite = s.begin(); ite != s.end(); ite ++ ) {
cout << *ite << endl;
}
return 0;
}下面用map实现
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
using namespace std;
int main() {
//声明（int为键，const char*为值）
map <int, const char*> m;
//插入元素
m.insert(make_pair(1, "ONE"));
m.insert(make_pair(10, "TEN"));
m[100] = "HUNDRED"; //其他写法
//查找元素
map <int, const char*> :: iterator ite;
ite = m.find(1);
cout << ite->second<< endl;
ite = m.find(2);
if (ite == m.end()) cout << "not found" << endl;
else cout << ite->second<< endl;
cout << m[10] << endl; //其他写法
//删除元素
m.erase(10);
//遍历一遍所有元素
for (ite = m.begin(); ite != m.end(); ite ++ ) cout << ite->first << " " << ite->second << endl;
return 0;
}