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

zhaohongjian000

yulihua49 发表于 2012-04-19 15:46
正常查找是递归的，记不住上下文。

你不会加两个变量记住啊。


反应过来了，非递归查找呗。

yulihua49

zhaohongjian000 发表于 2012-04-19 15:48
你不会加两个变量记住啊。

在栈里，每个变量都在不同的层，全局变量不能用，要求线程安全。
查找程序，那个rc就在栈里，每层都是单独的，没有共享变量。

1. T_Tree * BB_Tree_Find(T_Tree *sp,void *content_key,int len,
   
2.                 int (*Cmp_rec)(void *s1,void *s2,int len))
   
3. {
   
4. int rc;
   
5. //rc=sp-key
   
6.         return !sp?sp:!(rc=Tree_Cmp(sp->Content,content_key,len,Cmp_rec))?sp:
   
7.                 (rc>0)?BB_Tree_Find(sp->Left,content_key,len,Cmp_rec):
   
8.                 BB_Tree_Find(sp->Right,content_key,len,Cmp_rec);
   
9. }

复制代码

zhaohongjian000

yulihua49 发表于 2012-04-19 15:52
在栈里，每个变量都在不同的层，全局变量不能用，要求线程安全。

刚才呆了，非递归查找呗，也就多写点代码。

yulihua49

zhaohongjian000 发表于 2012-04-19 15:54
刚才呆了，非递归查找呗，也就多写点代码。

麻烦了。
上边的代码只能查找相等的，在查找过程中不一定能够碰上比他大还是比他小的节点。

而且他的父节点可能是大的或小的之一，另一个可能离得很远。

zhaohongjian000

yulihua49 发表于 2012-04-19 15:56
麻烦了。

这样也嫌麻烦，你是想要啥样的算法呀。。。

还是递归，用来记录的变量在最外层函数中分配在栈上。

yulihua49

zhaohongjian000 发表于 2012-04-19 16:00
这样也嫌麻烦，你是想要啥样的算法呀。。。

还是递归，用来记录的变量在最外层函数中分配在栈上。

作为地址带下去？
你能写一个试试看？我等着，多谢。
查找大于或小于之一即可。

我做的是通用软件，不是简单的数字哦！
Content是应用定义的数据，由回调函数提供应用的比较器使用，比较结果只有>0(节点〉key），=0，〈0，没有具体值。
所以那个变量存的啥东西，不知道。

在做一个内存的数据库。现在都64位时代了，内存放数百万的数据供多线程共享使用完全是可行的。
动态的AVL树，增删改查。。。。。。

zhaohongjian000

yulihua49 发表于 2012-04-19 16:07
作为地址带下去？
你能写一个试试看？我等着，多谢。
查找大于或小于之一即可。

1. 
   
2. T_Tree * BB_Tree_Find_Less_Max(T_Tree *sp,void *content_key,int len,
   
3.                 int (*Cmp_rec)(void *s1,void *s2,int len))
   
4. {
   
5.     T_Tree *lessMax = NULL;
   
6.     BB_Tree_Find_Less_Max_(sp, content_key, len, &lessMax);
   
7.     return lessMax;
   
8. }
   
9. T_Tree * BB_Tree_Find_Less_Max_(T_Tree *sp,void *content_key,int len,
   
10.                 int (*Cmp_rec)(void *s1,void *s2,int len), T_Tree **lessMax)
    
11. {
    
12. if(/*key的值更大*/)
    
13.     *lessMax = sp;
    
14. else if(/*key的值和当前节点相等*/)
    
15.     ;//返回左子树的最大节点
    
16. //以下略
    
17. }
    

复制代码

yulihua49

zhaohongjian000 发表于 2012-04-19 16:18

多谢，我读读看，再说。

你这个需要遍历，当数百万的记录，效率？

大概，一个节点，它值相邻的节点或是在查找的路径上，或是在左右儿子。

zhaohongjian000

yulihua49 发表于 2012-04-19 16:20
多谢，我读读看，再说。

你这个需要遍历，当数百万的记录，效率？

不需要啊，以下略的代码把你那个return那行贴过去就行了。这不就是二叉树的递归查找吗。

yulihua49

zhaohongjian000 发表于 2012-04-19 16:26
不需要啊，以下略的代码把你那个return那行贴过去就行了。这不就是二叉树的递归查找吗。

当是左右儿子的情况根本就找不到。
例如在15节点的满平衡树，12号节点的左右临近值，11号和13号都是12号的孙子。更深的后代也可能。
就是说仅仅找到相等节点时不够的，至少要遍历后代到底。
如果根本没有相等的值呢？