二叉树不等查找的算法谁清楚？前些日子发表CSTL的大侠说说看

walleeee

回复 29# yulihua49


没有。我是临时想起，所以我标注了“留待验证”。你最好多实验一下，免得出问题。

walleeee

回复 30# zhaohongjian000


   
。。。。

yulihua49

walleeee 发表于 2012-04-19 16:56
回复 29# yulihua49

STL有没有提供map的不等查询？

walleeee

回复 33# yulihua49


你也别在这里纠结了，你二分查找吧。

其实二叉树就是二分思想的体现，前面说的那些，都是二分。你排序后二分吧。

walleeee

回复 33# yulihua49


stl好像有个sort，你完了在二分

walleeee

stl那个sort还是很快。你百万级别的数据根本就不是什么问题。

当然，对象的拷贝复制任然是一个问题。这些细节你要留心。

_Rayx

回复 4# yulihua49


    算法导论里面有比较详细的解答

yulihua49

_Rayx 发表于 2012-04-19 17:17
回复 4# yulihua49

能提供一下吗？多谢了。

yulihua49

walleeee 发表于 2012-04-19 17:06
回复 33# yulihua49

下面的函数可以解决这个问题，但效率？等于是排序了。

1. //bt为根结点的指针，返回值为bt的节点数
   
2. // context为应用提供的上下文数据，由counter使用
   
3. //counter由应用提供，判断是否符合计数条件，不符合返回0.
   
4. int BB_Tree_Count(T_Tree *  bt,void *context,
   
5.         int (*counter)(T_Tree *bt,void *context))
   
6. {
   
7.         return !bt?0:(BB_Tree_Count(bt->Left,context,counter) +
   
8.                 ((counter)?counter(bt,context):1) +
   
9.                 BB_Tree_Count(bt->Right,context,counter));
   
10. }
    

复制代码

这个函数解决了 select count(*) from tree 的问题，也是内存数据库的一个核心组件。
它正序调用counter,你的counter把结果放在context里就是了。

yulihua49

walleeee 发表于 2012-04-19 17:06
回复 33# yulihua49

不行啊，数据是动态的，随时从数据库加载新的数据或删除旧的数据。
它是ORACLE的一个表的内存CACHE。