我找不到我的删除算法有什么问题。当我在 BST 的根上运行删除方法时,它将用右子树的最小值替换根,但此后不会删除该节点。
public void delete(BinaryTreeNode node, int x){
if (node==null)
return;
else if (x<node.getKey())
delete(node.getLeftChild(),x);
else if (x>node.getKey())
delete(node.getRightChild(),x);
else{
if (node.getLeftChild()==null)
node = node.getRightChild();
else if (node.getRightChild()==null)
node = node.getLeftChild();
else{
BinaryTreeNode temp = findMin(node.getRightChild());
System.out.println(temp.getKey() + " " + node.getKey());
node.setKey(temp.getKey());
System.out.println(temp.getKey() + " " + node.getKey());
delete(node.getRightChild(), node.getKey());
}
}
}
和我的 findMin() 方法:
public BinaryTreeNode findMin(BinaryTreeNode node){
if (node.getLeftChild()==null)
return node;
else
return findMin(node.getLeftChild());
}
对于包含所有整数 1-9 且根为 4 的 BST,我的 inorderPrint() 输出为
1,2,3,5,5,6,7,8,9
而不是
1,2,3,5,6,7,8,9
最佳答案
使用正确的节点更新已删除节点的父级指针。您需要清除已删除节点的任何痕迹。有一个临时节点来跟踪父节点,因此一旦找到要删除的节点,这会更容易做到。
关于java - Java中从二叉搜索树中删除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23161855/