java - Java中从二叉搜索树中删除

Question

我找不到我的删除算法有什么问题。当我在 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

Answer 1

使用正确的节点更新已删除节点的父级指针。您需要清除已删除节点的任何痕迹。有一个临时节点来跟踪父节点，因此一旦找到要删除的节点，这会更容易做到。