1

这是一个家庭作业。我需要递归遍历一个二叉搜索树，找出一个节点的数据值是否在一个范围内（包括），并按升序打印出来。

我的思考过程是：要按升序打印数据值，我需要在搜索树上按顺序遍历。为了有效地遍历，如果一个节点的左孩子小于下限值，并且该节点的数据小于下限值，程序应该停止向左遍历。同理，如果一个节点的右孩子大于上限值，并且该节点的数据大于上限值，程序应该停止向右遍历。

所以这是我的实现，但有错误：

public void rangeSearch(int lower, int upper) {
    if (lower > upper)
        throw new IllegalArgumentException("lower > upper");

    if (root != null)
        rangeSearchTree(root, lower, upper);
}

private static void rangeSearchTree(Node root, int lower, int upper) {
    Node leftChild = root.left;
    Node rightChild = root.right;
    if (leftChild != null && root.key > lower) {
        root = leftChild;
        rangeSearchTree(root, lower, upper);
    } 
    if (root.key >= lower && root.key <= upper) {
        System.out.print(root.key + " ");
    } 
    if (rightChild != null && root.key < upper) {
        root = rightChild;
        rangeSearchTree(root, lower, upper);
    }
}

树的结构如下：

      7
     / \
    5   9
   / \ / 
  2  6 8
   \
    4

当我输入6下限值和9上限值时，我得到6 8 8. 正确答案应该是6 7 8 9。有什么建议么？

4

2 回答 2

1 
if (leftChild != null && root.key > lower) {
    root = leftChild;  <---- Gotcha!
    rangeSearchTree(root, lower, upper);
} 
if (root.key >= lower && root.key <= upper) {

您正在更改root代码中间的 。root您在第二个中评估的if不是作为参数传递的那个，而是它的左孩子......

于 2012-12-02T18:47:21.207 回答
0

如果第二个是第一个，我认为问题应该得到解决。

于 2013-02-21T22:00:30.270 回答