去除二叉树中的叶子

Question

我对为什么我的 BST 中的叶子移除方法不起作用感到困惑。如果我将 0 赋给数据，它会反映在树中，但是当我将 null 赋给节点时，它仍然可以在 BST 遍历中被引用。

public void removeLeaves(){
    removeLeaves(getRoot());
}

private void removeLeaves(IntTreeNode node) {
    if (node == null)
        return;
    else if( node.left == null && node.right == null){
        node.data = 0;  //im finding the leave nodes correctly
        node = null;    //but its not removing them
    }
    else {
        removeLeaves(node.left);
        removeLeaves(node.right);
    }
}

        overallRoot
        ____[7]____
       /           \
    [3]             [9]
   /   \           /   \
[0]     [0]     [0]     [8]
                           \
                            [0]

有人可以解释为什么这没有按预期工作吗？

Answer 1

在您的示例树中，考虑 9

 9.left => null
 9.right => address of 8

当您分配 node.data = 0; 时，节点的地址为 8 因此 0 将反映在树中。

但是当您执行 node =null 时，您只是在更改变量 node。您没有对 address of 8 进行任何操作。

我认为您希望通过 node = null 实现的是：

      address of 8 = null

这实际上是不可能的，因为你只是在改变变量 node。

假设 8 的地址是 0XABCD，所以 node = 0XABCD。当您执行 node.data=0 时，因为 node 的地址为 0XABCD，0XABCD.data 将更改为 0。但是当你做 node = null 时，你只是给变量 node 赋了一个新值，你并没有对原始地址 0XABCD.

做任何操作

你实际要做的是

  if(node.left!= null && node.left.left == null && node.left.right ==null)
     node.left =null

  if(node.right!= null && node.right.left == null && node.right.right ==null)
     node.right =null

更新

你想要做的是这样的：

  Foo foo = new Foo();
  Foo anotherFoo = foo;

  anotherFoo.value = something; // both foo.value and anotherFoo.value will be changed to "something", because of the reference.

  anotherFoo = null; 
  // here you are expecting foo also to be null which is not correct.

Answer 2

public void removeLeaves () {
    if (getRoot() != null) 
        removeLeaves (getRoot());
}

private IntTreeNode removeLeaves (IntTreeNode node) {
    if (getRoot().left == null && getRoot().right == null) {
        setRoot(null);
    } else {
        if (node.left != null) {
            if (node.left.left == null && node.left.right == null) 
                node.left = null;             
            else 
                removeLeaves(node.left);
        }
        if (node.right != null) {
            if (node.right.right == null && node.right.left == null) 
                node.right = null;      
            else 
                removeLeaves(node.right);     
        }
    }
    return node;
}

去除二叉树中的叶子

Removal of leaves in a binary tree

java

tree