java正在从二叉树中删除未正确表示的叶子
我一直在从头开始创建二叉树,而不是使用内置库。我正在开发一个名为“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();
}
# 1 楼答案
+1是正确的答案(到目前为止,我只找到了一个),但是您忘记了根的null场景,并且如果根本身没有子级,您还需要删除根。我是这样做的-我使用了您的代码,然后确保它适合所有场景:
这段代码确保删除所有没有子节点的节点,还消除了对isLeaf()函数的需要
# 2 楼答案
使用链接:Deleting Leaves From a Binary Tree
我已经在我的代码中找到了错误,并使用链接中给出的答案进行了更正
更正代码如下: