这是我为遍历区间树而编写的函数。我注意到它无法访问某些节点。假设代码非常清晰,我想知道哪里出错了。
public boolean searchTree(Node node,int x)
{
while(node!=null&&!node.getInterval().containsPoint(x))
{
if(node.getNodeLeft()!=null&&(node.getNodeLeft().getMax()>=x))
{
node=node.getNodeLeft();
}
else
{
node=node.getNodeRight();
}
}
return node!=null;
}
最佳答案
树中的任何节点都以一个点为中心,比如 p。 左子树包含 p 左边的所有区间,右子树包含 p 右边的所有区间。节点本身包含与 p 重叠的所有区间。
现在,如果您的 x < p,则左子树可能存在包含 x 的区间,但也可能存在来自节点本身的区间,其中包含 x(和 p)。唯一的保证是右子树不会包含包含 x 的区间。
因此您在节点本身中遗漏了这些间隔。
我不知道什么是区间树,所以我的理解来自这里http://en.wikipedia.org/wiki/Interval_tree
关于algorithm - 区间树遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10347243/