从二叉树中删除叶子不能正确表示 [英] Removing leaves from Binary Tree not being represented properly

问题描述

我一直在从头开始创建二叉树，而不是使用内置库.我正在开发一个名为"pruneLeaves"的函数.这项工作是除去树上的所有叶子.没有孩子的节点.

I have been working on creating a Binary Tree from scratch, not using built-in libraries. I am working on a function called "pruneLeaves". The job is to remove all leaves of the tree; nodes with no children.

当我单步执行带有断点的函数时，它似乎正在除去叶子，甚至打印出它确实是在除去适当的节点.但是，当我随后在主函数中显示树时，节点仍然存在！

When I step through the function with breakpoints, it appears to be removing the leaves and even prints out that it is indeed removing the proper nodes. However, when I display the tree in my main function afterwards, the nodes are still there!

我已经尝试了好几个小时才能弄清楚这个问题，我忽略了什么?！

I have tried for hours to figure this out, what am I overlooking?!

程序输出:

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

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

And my main method, calling the function:

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

推荐答案

使用链接:我已在代码中找到错误，并使用链接中给出的答案进行了纠正.

I have found the errors in my code and corrected them using the answer given in the link.

更正代码如下:

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

这篇关于从二叉树中删除叶子不能正确表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！