从二叉树中删除叶子不能正确表示 [英] 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屋!