我有一个 RedBlack [Balanced, sorted] 二叉树,我正在搜索它以找到 [lower,upper] 范围内的所有值。
public IEnumerable<TData> Range(
BinaryTree<TData> root,
IComparer<TData> comparer,
TData lower,
TData upper)
{
var stack = new Stack<State>(16);
BinaryTree<TData> here = root;
do
{
if (here == null)
{
if (stack.Count == 0)
break;
State popped = stack.Pop();
yield return popped.Data;
here = popped.Next;
continue;
}
if (comparer.Compare(here.Data, lower) < 0)
{
here = here.Right;
}
else if (comparer.Compare(here.Data, upper) > 0)
{
here = here.Left;
}
else
{
stack.Push(new State {Next = here.Right, Data = here.Data});
here = here.Left;
}
} while (true);
}
因此,使用此代码,如果我要使用这些值构建一棵树
[0, 1, 4, 5, 6, 9],
并搜索范围内的所有元素
[3, 8]
我会得到以下结果:
[4, 5, 6].
我的问题是如何调整此算法以获取搜索的外部元素?像这样:
[1, 4, 5, 6, 9]
即值 3 在树中介于 1 和 4 之间,所以我想返回 1,类似地,值 8 介于 6 和 9 之间,我希望值 9 包含在结果中。
一个问题是我不想从根目录重新开始搜索
目前使用 NGenerics 实现
[编辑]
愿意接受一般的算法答案。