修剪二叉搜索树

Question

我应该编写一个方法，将两个整数作为最小值和最大值。然后，它从树中删除所有小于最小值且大于最大值的整数。到目前为止我的代码非常丑陋并且根本不起作用。我什至不确定我是否走在正确的道路上......

private SearchTree<Integer> trim(SearchTreeNode<Integer> e, int min, int max){
    if (e != null){
        if (e.left.data.compareTo(min) <= 0){
            remove((E) e.left);
        } else {

        }
    }
}

Answer 1

关于没有任何代码的算法的一些一般想法：

您需要首先实现delete。二叉搜索树中的delete具有特定且定义良好的行为；你需要首先实现这一点（你的教授应该已经讨论过它）。我想说你80%的工作都是在这里完成的。

剩下的20%用于实现find功能。您现在可以组合这两个函数并实现 trim 函数。

如果您解释一下到目前为止您所做的事情，我们也许可以给您一些提示并引导您走向正确的方向。这里最重要的是学习！

UPDATE

是的，需要遍历树并删除符合条件的节点。就递归而言，想想通常如何遍历二叉搜索树。

现在您需要添加 contains 和 remove。这部分是微不足道的，但棘手的部分是，当你遍历树时，树正在发生变化。但如果你想一想，应该没那么难。提示：当您删除 BST 中的节点时，您实际上并没有删除它，除非它是叶节点。您只需替换它的值即可。所以遍历应该不会受到影响。

Answer 2

您的问题的伪代码是。

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

     if(max >= e.data && e.right !=null && e.right.data > max){
       e.right=null;
     }else{
       trim(e.right, min,max);
     }
     return e;
   }
}

Answer 3

也许你可以实现迭代器接口，遍历构成 BST 的元素，将满足约束的元素放入新的 BST 中
然后你让原来的 BST 等于新的 BST。

问候。