标签 java binary-tree trim
<分区>
我应该编写一个接受两个整数作为最小值和最大值的方法。然后它从树中删除任何小于最小值且大于最大值的整数。到目前为止，我的代码非常丑陋，根本不起作用。我什至不确定我是否走在正确的道路上......
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 {
}
}
}
最佳答案
在没有任何代码的情况下，关于该算法的一些一般性想法:
你需要先实现delete。二叉搜索树中的 delete 具有特定且定义明确的行为；你需要先实现它(你的教授应该已经看过了)。我会说您 80% 的工作都在这里完成。
剩下的 20% 用于实现 find 功能。您现在可以组合这两个函数并实现您的 trim 函数。
如果您解释到目前为止所做的事情，我们可能会给您一些提示并引导您朝着正确的方向前进。这里重要的是学习!
更新
是的，需要遍历树，删除符合条件的节点。就递归而言，想一想你将如何正常遍历二叉搜索树。
现在您需要添加contains 和remove。那部分是微不足道的，但棘手的部分是树在您遍历它时正在发生变化。但仔细想想，应该没有那么难。提示:当您删除 BST 中的一个节点时，您实际上并没有删除它，除非它是叶节点。您只需替换它的值。所以遍历应该不会受到影响。
关于java - 修剪二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5396171/