java - 从二叉树中删除未正确表示的叶子

Question

我一直致力于从头开始创建二叉树，而不是使用内置库。我正在开发一个名为“pruneLeaves”的函数。任务是除去树上的所有叶子；没有子节点的节点。

当我使用断点单步执行该函数时，它似乎正在删除叶子，甚至打印出它确实正在删除正确的节点。但是，当我之后在主函数中显示树时，节点仍然在那里!

我已经尝试了几个小时来解决这个问题，我忽略了什么？!

程序输出:

Num nodes = 9
Pruning.
12
Leaf removed
9
Leaf removed
4
Leaf removed
Tree after pruning..
3 4 5 6 7 8 9 11 12 

<小时/>

    // Recursive helper. Accepts BinaryNode as a parameter
private BinaryNode pruneLeaves(BinaryNode t) {

    // If we have no left child AND no right child, we are a leaf
    if ((t.left == null) && (t.right == null)) {

        //Print the element being removed.
        System.out.println (t.element);

        //Remove the element
        t = remove(t.element, t);

        if(t == null)
            System.out.println("Leaf removed");
    }
    // Else we have at least one child
    else {

        if (t.right != null) {
            pruneLeaves(t.right);
        }

        if (t.left != null) {
            pruneLeaves(t.left);
        }
    }
  //Return our leafless tree
  return t;
}

// Main recursive method, call the helper method by passing the root of the 
// tree, which calls it.
public void pruneLeaves () {
    pruneLeaves(this.getRoot());
}

BinaryNode getRoot () {
    return this.root;
}

/**
 * Internal method to remove from a subtree.
 * @param x the item to remove.
 * @param t the node that roots the tree.
 * @return the new root.
 */
private BinaryNode remove( int x, BinaryNode t )  {
success = false;
    if( t == null )
        return t;   // Item not found; do nothing

    if( x < t.element )
        t.left = remove( x, t.left );

    else if( x > t.element )
        t.right = remove( x, t.right );

    else {
        success = true;

        if( t.left != null && t.right != null )  { // Two children
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }

        else
        t = ( t.left != null ) ? t.left : t.right;
    }
    return t;
}

我的主要方法，调用函数:

    public static void main( String [ ] args )   {
    BST t = new BST( );

    t.insert(7);
    t.insert(6);
    t.insert(5);
    t.insert(3);
    t.insert(4);
    t.insert(8);
    t.insert(11);
    t.insert(9);
    t.insert(12);

    System.out.println();
    System.out.println ("Num nodes = " + t.countNodes());
    System.out.println ("Pruning.");

    // Remove leaves of the tree
    t.pruneLeaves();
    t.infix();
    System.out.println();
}

Answer 1

使用链接:Deleting Leaves From a Binary Tree

我发现了代码中的错误，并使用链接中给出的答案更正了它们。

正确代码如下:

private BinaryNode pruneLeaves (BinaryNode p) {

    // There is a left child
    if (p.left != null)
        if (isLeaf(p.left)) //Is that child a leaf?
            p.left = null;             
        else
            pruneLeaves(p.left);      // If it is not, recursive call

    // Is there a right child
    if (p.right != null)
        if (isLeaf(p.right))
            p.right = null;            
        else
            pruneLeaves(p.right);     // Recursive call
    return p;
}

// Main recursive call, passes the root of calling tree to the helper method
public void pruneLeaves () {
    pruneLeaves (this.getRoot());
}

// Returns true if child is a leaf
boolean isLeaf (BinaryNode t) {
    if (t.left == null && t.right == null) {
        return true;
    }
    return false;
}