0

这是我的代码应该做的： 在此处输入图像描述

问题要求我创建方法接受最小和最大整数作为参数，并从树中删除不在该范围内的任何元素，包括在内。

我最初写的代码是

public void trim (int min, int max) {
    overallRoot = trim (overallRoot, min, max);
}

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root != null) {
        if(root.data < min && root.data > max) {
            root = null;
        }else {
            root.left = trim(root.left, min, max);
            root.right = trim (root.right, min, max);
        }
    } 
    return root;
}

我做了一些搜索，因为我的代码没有重建树，我找到了这段代码：

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    root.left = trim(root.left, min, max);
    root.right = trim (root.right, min, max);
    if(root.data < max && root.data> min) {
        return root;
    }else if (root.data < min) {
        return root.right;
    }else if (node.data > max) {
        return root.left;
    }
}

该代码无法编译，因为它缺少 return 语句，因此，当我将其更改为 else 时，它​​仅在某些情况下有效。我有点理解上面的代码，但写的不是很直观，但话又说回来......递归不是很直观。正如我的教授所说，“信仰的飞跃”。任何帮助将不胜感激:) 努力在我的决赛中表现出色

4

4 回答 4

2

您的代码的问题是，即使根节点在区间之外，它的子节点也不必在，但无论如何您都删除了整个子树。

您找到的代码通过首先修剪子树然后查看根节点来解决此问题。如果它在 的左边min，根节点和它的左子树都必须被删除，而右子树（已经被修剪）是剩下的。类似地，如果根在 的右边max，那么右子树也是，而（已经修剪过的）左子树就是需要保留的。这将访问整个树，因此效率不高。

一个直接的改进只会访问我们打算使用的子树：

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    if(root.data < max && root.data> min) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        return root;
    }else if (root.data < min) {
        return trim (root.right, min, max);
    }else if (node.data > max) {
        return trim(root.left, min, max);
    }
}

但是，这仍然不是最优的，因为它会重新访问 [min, max] 中的所有节点。

可能最好的方法是分两步进行修剪：首先修剪所有节点 < min，然后修剪所有节点 > max：

IntTreeNode trimLeft(IntTreeNode root, int min) {
    if (root == null {
        return null;
    } else if (root.data < min) {
        return trimLeft(root.right, min);
    } else {
        root.left = trimLeft(root.left, min);
        return root;
    }
}

这种方法的优点是我们只访问到min和路径上的节点max。如果搜索树是平衡的，这将是 O(log n)。

无论您选择哪种方法，您都应该正确定义在边缘情况下会发生什么，root.data == min并且root.data == max（您的原始代码和您发现的代码都做错了）。

于 2013-06-10T06:26:10.363 回答
1

您需要确保您的代码涵盖递归的所有情况。

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    root.left = trim(root.left, min, max);
    root.right = trim (root.right, min, max);
    if(root.data < max && root.data> min) {
        return root;
    }else if (root.data < min) {
        return root.right;
    }else if (node.data > max) {
        return root.left;
    }
}

所以让我们列出它正在检查的内容：

  • 根为空
  • 最小值 < 当前值 < 最大值
  • 当前值 < 最小值
  • 最大值 < 当前值

它不包括current value == min和current value == max案例！你说它应该检查包含范围。这意味着min < current value < max应该是min ≤ current value ≤ max，对吧？我认为这会解决它。

但是，就像你说的，代码不是很可读。我会稍微改变一下：

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    // Base case: leaves' children are null
    if (root == null)
        return root;
    // Case: current value too small - use trimmed right subtree
    if (root.data < min)
        return trim(root.right, min, max);
    // Case: current value too large - use trimmed left subtree
    else if (node.data > max)
        return trim(root.left, min, max);
    // Case: current value in range - trim both subtrees
    else if (min <= root.data && root.data <= max) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        return root;
    }
    // Make sure we've covered all the cases
    // (this should be unreachable if our cases are complete)
    throw new RuntimeException("Unhandled case in trim!");
}

这会更有效率，因为您不会调用trim最终修剪掉的子树。在最后一种情况下，我确实通过重复调用来复制了一点代码trim，有些人可能会对此提出异议，但我个人认为这很好。

（注意：我实际上并没有测试过任何这段代码，所以它可能有语法错误，甚至无法编译，但它应该让您了解它应该如何工作。）

回应您的评论：

代码现在应该运行，因为我throw在方法的末尾添加了一个子句。

您的代码条款与第二版中if (root != null)的情况基本相同。if (root == null) return root;

if (root.data < max && root.data > min)正在检查该值是否在min 到 max Exclusive 范围内。

因此，如果当前节点的值不在 min 和 max 之间，则您将丢弃整个子树。您需要修复代码以仅丢弃正确的子树，并进行包容性检查。

另一方面，我认为if (min <= root.data && root.data <= max)它比您所拥有的更具可读性，因为它看起来更像您在更传统的数学定义中写出的内容：min ≤ root.data ≤ max. 在我看来，保持不等式符号朝向同一个方向很好。

于 2013-06-10T06:05:58.923 回答
1

这是适用于所有情况的代码，对于最终在谷歌搜索这个问题的人来说哈哈：

public void trim (int min, int max) {
    overallRoot = trim (overallRoot, min, max);
}

private IntTreeNode trim (IntTreeNode root, int min, int max) {
    if (root == null) {
        return root;
    }
    if(root.data <= max && root.data>= min) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        return root;
    }else if (root.data < min) {
        return trim (root.right, min, max);
    }else if (root.data > max) {
        return trim(root.left, min, max);
    }else{
        return root;
    }
}
于 2013-06-10T06:49:35.467 回答
0 
public void trim(int min, int max) {
    overallRoot = trim(overallRoot, min, max);
}

private IntTreeNode trim(IntTreeNode root, int min, int max) {
    if (root != null) {
        root.left = trim(root.left, min, max);
        root.right = trim (root.right, min, max);
        if (root.data < min) {
            return root.right;
        } else if (root.data > max) {
            return root.left;
        }
    }
    return root;
}

很直观。由于二叉树的构建方式是左边的值总是小于或等于根中的值，而右边的值总是更大，如果 root.data 小于最小值，则返回右边分支（始终大于 root.data），如果 root.data 大于给定的最大值，则返回左分支（始终小于或等于）。使用递归修剪整棵树（二叉树由左右两侧组成）：trim(root.left, min, max) trim(root.right, min max)。并返回 root 以替换overallRoot，它给出的树只具有给定的最小值和最大值（包括）内的值。

更全面的结构：

public void trim(int min, int max) {
    overallRoot = trim(overallRoot, min, max);
}

private IntTreeNode trim(IntTreeNode root, int min, int max) {
    if (root != null) {
        if (root.data < min) {
            root = trim(root.right, min, max);
        } else if (root.data > max) {
            root = trim(root.left, min, max);
        } else {
            root.left  = trim(root.left,  min, max);
            root.right = trim(root.right, min, max);
        }
    }
    return root;
}
于 2016-03-01T08:24:15.900 回答