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

zhaohongjian000

yulihua49 发表于 2012-04-19 16:29
当是左右儿子的情况根本就找不到。

额，光考虑key查不到的情况了。

如果key查到了，那就返回左子树的最大节点/右子树的最小节点（这两个操作应该有现成函数吧）。如果又觉得麻烦，那我没办法了。

yulihua49

zhaohongjian000 发表于 2012-04-19 16:33
额，光考虑key查不到的情况了。

如果key查到了，那就返回左子树的最大节点/右子树的最小节点（这两个 ...

你能帮我动这个脑筋很好，办法一定会有的，而且不会太复杂。

walleeee

我不知道你还是看什么。我二楼不就说了，二叉查找树，也叫二叉排序树。

根据你的描述，就是找一个值的小于他的最大的值和大于他的最小的值，二叉排序树不就是左儿子小于他，右儿子大于他这种的递归定义么
比如1,3,7,8,5这个序列
建树
1

1
   3

1
   3
       7

1
   3
      7
         8

1
   3
      7
   5     8

找7，直接就是（5，8）
，比如再加几个，6，4
1
   3
      7
   5     8
      6

1
   3
      7
   5     8
4    6
找5，直接就是（4，6）

我对你的问题理解就是这样。如果你觉得二叉查找树对于大量随机效率比较低，那你可以走平衡二叉查找树，比如avl，这些。

walleeee

回复 20# yulihua49


既然有没有在树中这个情况，那又是另外一说了

zhaohongjian000

yulihua49 发表于 2012-04-19 16:36
你能帮我动这个脑筋很好，办法一定会有的，而且不会太复杂。

办法还是那个，17层编辑过了。

zhaohongjian000

yulihua49 发表于 2012-04-19 16:29
当是左右儿子的情况根本就找不到。
例如在15节点的满平衡树，12号节点的左右临近值，11号和13号都是12号 ...

如果查找过程没找到，那么一定是遍历到底的，遇到的最后一个小于key的节点就是小于key的最大节点。

如果找到了key就简单多了，自然就是左子树的最大节点。

yulihua49

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

if(/*key的值更大*/)

    *lessMax = sp;

if(node < key && node>lessMax) lessMax=node;

有点靠谱了。
沿着一个路径插到底。

walleeee

不知道这么行不行，没验证。

右递归，知道转折，比如
1
   3
      7
   5     8
      6
找4。递归到第一次左转，就是3，7之间，这时记录3，作为小于他的最大值。然后左递归，直到不能继续，就到了5，记录作为大于他的最小，于是就是（3，5）。这是对的。同样，你可以开始就左递归，但是一旦转折就立马右递归，这是第一个记录就成了大于他的最小值，第二次记录是小于他的最大值。
当然，还有一个情况就是前面说的，碰到正好匹配了，这个时候就是左右儿子。

留待验证

yulihua49

walleeee 发表于 2012-04-19 16:51
不知道这么行不行，没验证。

右递归，知道转折，比如

想法很好，不过你们见到有文献介绍这个算法的吗？我是比较孤陋寡闻，如果有给我个连接？
我见过的所有资料都有等值查找，没有不等式查找。
一般的需求，只要大于或小于之一即可，还有就是区间，可以由单个的大于或小于组合而成。

zhaohongjian000

walleeee 发表于 2012-04-19 16:51
不知道这么行不行，没验证。

右递归，知道转折，比如

是这样的，我就是一直在向LZ解释这个...

但匹配的时候不是左右儿子，而是左子树的最大节点（最右节点）和右子树的最小节点（最左节点）。

话说，我好像重复了好多遍这句话了......