当我调用deleteNode方法时,我的二叉搜索树程序似乎没有删除任何内容。 BST构建得很完美,只是删除了不起作用的节点部分。我从我的 main 中这样调用它:
System.out.println("Please enter a number you would like to delete from the tree");
temp = reader.nextLine();
try {
int numTemp = Integer.parseInt(temp);
TreeNode treeTemp = bst.deleteNode(numTemp, bst.getRoot());
bst.setRoot(treeTemp);
}
catch(Throwable e){
System.err.println(e);
}
bst.printInBST(bst.getRoot());
在我的 BinarySearchTree 类中,我实现了如下的 deleteNode 方法:
public TreeNode deleteNode(int x, TreeNode temp){
if(temp != null){
if(x > (int)((Integer)temp.getValue())){
temp.setLeft(deleteNode(new Integer(x), temp.getLeft()));
}
else if(x < (int)((Integer)temp.getValue())){
temp.setRight(deleteNode(new Integer(x), temp.getRight()));
}
else if(temp.getLeft() != null & temp.getRight() != null){
TreeNode temp2 = new TreeNode(temp.getRight().getValue());
while(temp2.getLeft() != null){
temp2 = temp2.getLeft();
}
temp = temp2;
temp.setRight(remove(temp.getRight()));
}
}
return temp;
}
public TreeNode remove(TreeNode temp){
if(temp.getLeft() != null){
temp.setLeft(remove(temp.getLeft()));
return temp;
}
else {
return temp.getRight();
}
}
最佳答案
我认为你没有处理
情况1:删除节点是叶子节点
情况2:删除节点只有1个子节点
<小时/>else if 部分应该是这样的。
else if( temp.getLeft() != null && temp.getRight() != null ) // Two children
{
temp.setValue( findMin( temp.getRight() ).getValue());
temp.setRight ( deleteNode( temp.getValue(), temp.getRight() );
}
else
temp = ( temp.getLeft() != null ) ? temp.getLeft() : temp.getRight();
return temp;
<小时/>
findMin方法是查找要删除的节点的中序后继。
private TreeNode findMin( TreeNode t )
{
if( t == null )
return null;
else if( t.getLeft() == null )
return t;
return findMin( t.getLeft() );
}
<小时/>
我希望这能回答您的问题。
关于java - 从二叉搜索树中删除节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7698662/