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

yulihua49

在二叉树里查找大于指定值的最小节点或小于指定值的最大节点。
树不含横向链（不是B+树），没有父节点指针。
谁能给出一个算法？

在网上搜了一下“二叉树不等查找”，居然只有我这一贴。
难道别人没有这个需求吗？未见到相关报道，我要是做出来了，可以申请专利吗？

需要的功能：
tree_find_EQ 这个实现了。
tree_find_GT 大于KEY中最小的一个。
tree_fine_GTEQ     >=
tree_find_LT  小于KEY中最大的一个。
tree_find_LTEQ     <=
.......

walleeee

查找二叉树

_Rayx

看得看这个二叉树满足什么条件了，如果这个树就是一个平常的，那么就只能遍历记录了。
当然上面那种如果二叉树的结构不会改变的吧，可以把树拆成结点排序，再二分查找就行了。

如果二叉树满足左儿子小于父结点，右儿子大于父结点就分情况讨论就行了。

yulihua49

_Rayx 发表于 2012-04-19 15:15
看得看这个二叉树满足什么条件了，如果这个树就是一个平常的，那么就只能遍历记录了。
当然上面那种如果二 ...

二叉树满足左儿子小于父结点，右儿子大于父结点，没有值重复的节点。有算法么？

zhaohongjian000

正常查找，把遇到的最后一个大于要查的key的节点和最后一个小于要查的key的节点记下来就是了。

yulihua49

zhaohongjian000 发表于 2012-04-19 15:41
正常查找，把遇到的最后一个大于要查的key的节点和最后一个小于要查的key的节点记下来就是了。

遍历？
希望按深度查找，实现O（log2（N））。

zhaohongjian000

yulihua49 发表于 2012-04-19 15:42
遍历？
希望按深度查找，实现O（log2N）。

就是正常的查找啊，难道这个二叉树不是有序的？

鸡丝拌面

遍历＋前驱后继。

yulihua49

zhaohongjian000 发表于 2012-04-19 15:44
就是正常的查找啊，难道这个二叉树不是有序的？

正常查找是递归的，记不住上下文。

yulihua49

鸡丝拌面 发表于 2012-04-19 15:45
遍历＋前驱后继。

没有前驱后继，不是B+树。
正常查找：

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. }
   

复制代码