挑战程序设计竞赛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

*/