我一直致力于从头开始创建二叉树,而不是使用内置库。我正在开发一个名为“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();
}
最佳答案
使用链接: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;
}
关于java - 从二叉树中删除未正确表示的叶子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28313390/