java - 二叉搜索树不删除节点

Question

我创建了一个二叉搜索树，并尝试在添加特定节点后删除它们。我可以成功删除大约5个节点，但是当我尝试删除ID为109的节点时，它只是忽略它并且什么也没有发生。我尝试了很多方法都无法删除它。

myBinaryTree.deleteNode(myBinaryTree.root, 109);

这是我的二叉树中的delete方法。

public Node deleteNode(Node root, int ID){

    if (root == null)  return root;
    if (ID < root.ID)
        root.leftChild = deleteNode(root.leftChild, ID);
    else if (ID > root.ID)
        root.rightChild = deleteNode(root.rightChild, ID);

    else
    {
        if (root.leftChild == null)
            return root.rightChild;
        else if (root.rightChild == null)
            return root.leftChild;

        root.ID = minValue(root.rightChild);
        root.rightChild = deleteNode(root.rightChild, root.ID);
    }

    return root;
}


int minValue(Node root)
{
    int minv = root.ID;
    while (root.leftChild != null)
    {
        minv = root.leftChild.ID;
        root = root.leftChild;
    }
    return minv;
}

还有我的节点:

public class Node {
    int ID;
    Dancer.Gender gender;
    int height;

    Node leftChild;
    Node rightChild;

    Node(int ID, Dancer.Gender gender, int height) {

        this.ID = ID;
        this.gender = gender;
        this.height = ID;

    }

    public int getID() {
        return ID;
    }

    public void setID(int ID) {
        this.ID = ID;
    }

}

ID 按预期工作，这意味着方法 deleteNode 获取了正确的 ID，只是不会删除它。

这是我试图从中删除的树的图片:

如果需要有关如何添加节点等的更多信息，我也可以提供。这太奇怪了，直到我尝试删除 ID = 109 的节点时，一切都运行良好。

Answer 1

你的代码看起来不错。

顺便问一下，你是如何验证该节点没有被删除的？我刚刚检查了你的代码并打印了中序遍历。而且效果很好。

// This is java code.
void inorder(Node root){
    if (root ==null)return;
    inorder(root.leftChild);
    System.out.print(root.ID + "  ");
    inorder(root.rightChild);
}

// verify deletion by printing inorder traversal before and after
public static void main(String[] args) {
    // creating the tree
    Node root = new Node(60);
    root.leftChild = new Node(40);
    root.rightChild = new Node(109);
    root.leftChild.leftChild = new Node(20);
    root.leftChild.rightChild = new Node(49);

    inorder(root); // Printing before deleting
    System.out.println();
    myBinaryTree.root = deleteNode(myBinaryTree.root, 109); // delete the node and collect the new reference of the root.
    inorder(root); // Printing after tree
    System.out.println();
}