所以我为BST实现创建了一个删除功能 . 它适用于删除叶节点的情况,以及与正确子节点相关的子树,但没有左子节点,反之亦然 .
但是,删除根节点给我带来了问题 . 我试图用它的后继替换root,然后将new root的右子设置为等于old root的右子 .
例:
50
/ \
/ \
42 63
/ \ /
/ \ 55
21 43
\ \
23 \
/ \ 47
/ \
44 48
如果我要在我的程序中删除节点50,那么55将是新根,但是63会消失,但其他一切正常 .
我是否错误地重新连接节点? (从代码中的 "Problem is Here" 评论开始)
//How I display my tree
//inprder traversal
private void inOrder(Node curr){
if(curr != null){
//traverse left
inOrder(curr.leftChild);
System.out.print("\n" + curr + "->");
//traverse right
inOrder(curr.rightChild);
}
}
public boolean deleteContact(String key){
//Start at root node
Node currentNode = root;
Node parent = root;
boolean isLeftChld = true;
//loop over left and right subtrees
//finds node to be deleted
while(!key.equals(currentNode.key)){
parent = currentNode;
if(key.compareToIgnoreCase(currentNode.key) < 0){
isLeftChld = true;
currentNode = currentNode.leftChild;
}else{
isLeftChld = false;
currentNode = currentNode.rightChild;
}
//Node never found
if(currentNode == null){
return false;
}
}
//if the node doesnt have children
//go ahead and delete
if(currentNode.leftChild == null && currentNode.rightChild == null){
if(currentNode == root){
root = null;
//Handle case of juss deleting leafs
}else if(isLeftChld){//check if it was a left or right child
//delete it
parent.leftChild = null;
}else{
parent.rightChild = null;
}
//situation of no right child
//handling node dissapearing
} else if(currentNode.rightChild == null){
if(currentNode == root){
root = currentNode.leftChild;
}else if (isLeftChld){
parent.leftChild = currentNode.leftChild;
}else{
parent.rightChild = currentNode.leftChild;
}
//situation of no left child
}else if(currentNode.leftChild == null){
if(currentNode == root){
root = currentNode.rightChild;
}else if (isLeftChld){
parent.leftChild = currentNode.rightChild;
}else{
parent.rightChild = currentNode.leftChild;
}
**Problem is Here**
//situation of two children being involved
//figure out which node will replace which
} else {
//Node temp = currentNode.rightChild;
Node successor = minValue(currentNode.rightChild);
if(currentNode == root){
root = successor;
}else if(isLeftChld){
parent.leftChild = successor;
}else{
parent.rightChild = successor;
}
root.leftChild = currentNode.leftChild;
}
return true;
}
//Function to return min value for a root node
//Used for delete function - finds succesor
private Node minValue(Node root)
{
Node minv = root;
while (root.leftChild != null)
{
minv = root.leftChild;
root = root.leftChild;
}
return minv;
}
1 回答
您还需要分配正确的孩子 .
缺少以下行: