java - 删除二叉树中的节点

Question

下面是我针对deleteItem位于叶节点的情况编写的代码。即使我将找到的叶节点等同于“null”，那么当我打印树的中序遍历顺序时，该元素也不会被删除并出现在屏幕上。我错过了什么？

public void deleteNode(T deleteItem)
    {
        TreeNode<T> node = root;
        if(root == null)
        {
            System.out.print("Binary Tree does not exist");
            System.exit(0);
        }
        while((node.data != deleteItem) && (node.leftNode != null || node.rightNode != null))
        {
            if(deleteItem.compareTo(node.data)<0)
                node = node.leftNode;
            else
                node = node.rightNode;
        }
        //System.out.printf("deleting item is: %s\n", node.data);
        if(node.data != deleteItem)
        {   
            System.out.println("\ndeleteItem not found in the tree");
            System.exit(0);
        }
        else
        {
            if(node.leftNode == null && node.rightNode == null)
            {
                node = null;
            }
        }
    }

Answer 1

Java 是 "Pass-by-value" ,所以TreeNode<T> tmp = root这里的意思是分配 tmp的引用root这意味着您对同一个实例有两个不同的引用。据此，当你说node = null时您将本地引用设置为 null这意味着该节点的父节点仍然引用它。因此，要从树中删除叶节点，您需要跟踪其父节点，然后删除对节点的引用(删除树中的引用而不是本地副本)，如下所示:

public void deleteNode(T deleteItem) {
        TreeNode<T> node = root;
        TreeNode<T> parent = null; // parent of the deleted node.
        if(root == null) {
            System.out.print("Binary Tree does not exist");
            System.exit(0);
        }
        while((node.data != deleteItem) && 
              (node.leftNode != null || node.rightNode != null)) {
            parent = node; // keep track of the parent of the deleted node
            if(deleteItem.compareTo(node.data) < 0)
                node = node.leftNode;
            else
                node = node.rightNode;
        }
        if(node.data != deleteItem) {   
            System.out.println("\ndeleteItem not found in the tree");
            System.exit(0);
        }
        else {
            if(parent.leftNode == node)
                parent.leftNode = null;
            else
                parent.rightNode = null;
        }
    }