java - 删除二叉树中的节点

下面是我为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;
            }
        }
    }

最佳答案

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;
        }
    }