挑战程序设计竞赛11.3
今天读了二叉搜索树的实现以及set和map的简单用法。
二叉搜索树实际上就是一颗二叉树，但它有一个特点，就是每个节点左二子的值小于它的值，右儿子的值大于它的值。
由于是一个树形结构，他能高效的进行插入，删除，查找。每次操作时间复杂度都在logn以内。
C++的stl里面有用二叉搜索树实现的set容器，可以很方便地直接调用。
还有map容器。下面是这两个容器的简单用法。
set的基本用法
#include
#include
#include
//set是一个有序的无重复的容器
//还有可以重复的multiset
using namespace std;
int main()
{
set se;
se.insert(3);
se.insert(5);
se.insert(1);
set::iterator ite;
for(ite=se.begin();ite!=se.end();ite++){
printf("%d ",*ite);
}
printf("\n");
ite=se.find(3);
if(ite==se.end()){
printf("查找3失败\n");
}else{
printf("查找3成功\n");
}
se.erase(1);
for(ite=se.begin();ite!=se.end();ite++){
printf("%d ",*ite);
}
return 0;
}
/*测试结果
1 3 5
查找3成功
3 5
*/
map的基本用法
#include
#include
#include
#include
using namespace std;
int main()
{
map m;
m.insert(make_pair(10,"tom"));
m.insert(make_pair(30,"dom"));
m[20]="amy";
map::iterator it;
it=m.find(30);
if(it!=m.end()){
printf("查找30成功\n");
}else{
printf("查找失败\n");
}
for(it=m.begin();it!=m.end();it++){
printf("%d %s\n",it->first,it->second);
}
printf("\n");
m.erase(30);
for(it=m.begin();it!=m.end();it++){
printf("%d %s\n",it->first,it->second);
}
return 0;
}
/*测试结果
查找30成功
10 tom
20 amy
30 dom
10 tom
20 amy
*/
