如何用Java编写惰性删除二叉树的findMinimum
如何用Java编写惰性删除二叉树的findMinimum
提问于 2018-02-21 06:25:45
我正在用Java编写一个二进制搜索树的类，它使用惰性删除(它不是从树中删除节点，而是将"deleted“标志设置为true)。
我的问题是，我如何为这样的树实现findMin函数？通常的方法是直接转到最左边的叶子，因为那条引线可能会被“删除”。
例如，像这样的树，您可以删除20、5和17
25
*20 30
*17 89
*5当您调用findMin()时，应该返回25。
我的实现如下所示：
public int findMin() {
return doFindMin(root);
}
private int doFindMin(TreeNode node) {
if (node == null) {
return -1;
} else if (node.getLeftChild() != null) {
return doFindMin(node.getLeftChild());
} else if (!node.isDeleted()) {
return node.getKey();
} else if (node.getRightChild() != null){
return doFindMin(node.getRightChild());
} else return -1;
}当我在上面描述的情况下调用函数时，它返回-1。如果我不删除17，它会正确地返回17作为最小值。
在这方面的任何帮助都将非常感谢。谢谢。
编辑: 17在树中的位置不正确，原始帖子已更新以解决此问题。
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-02-21 07:18:47
按顺序记录未标记为已删除的节点。第一个未删除的元素是，一旦找到第一个元素，minimum.You可能会中断遍历。您可以执行如下操作：
void inOrderForMinimum( TreeNode node, int[] min ) {
if ( node != null && min[0] == -1 ) {
inOrderForMinimum( node.getLeftChild(), min );
if ( !node.isDeleted() ) {
min[0] = node.value;
}
inOrderForMinimum( node.getRightChild(), min );
}
}如下所示：
private int findMinimum( TreeNode root ) {
int[] min = new int[]{-1};
inOrderForMinimum( root, min );
return min[0];
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48895238
复制相关文章
相似问题
腾讯云开发者
