从未正确表示的二叉树中移除叶子
Removing leaves from Binary Tree not being represented properly
我一直致力于从头开始创建二叉树,而不是使用 built-in 库。我正在研究一个名为 "pruneLeaves" 的函数。工作是移除树上的所有叶子;没有 children.
的节点
当我使用断点单步执行函数时,它似乎在移除叶子,甚至打印出它确实在移除正确的节点。但是,当我之后在主函数中显示树时,节点仍然存在!
我已经尝试了几个小时来解决这个问题,我忽略了什么?!
程序输出:
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();
}
使用link:Deleting Leaves From a Binary Tree
我发现了我的代码中的错误并使用 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;
}
+1 是正确的答案(到目前为止我只找到了一个),但是您忘记了根的空方案,并且如果根本身没有子项也删除根。以下是我的做法 - 我使用了您的代码,然后确保它适合所有场景:
public void removeLeaves () {
if (root != null) {
removeLeaves (root);
} else {
return;
}
}
private Node removeLeaves (Node node) {
if (root.left == null && root.right == null) {
root = null;
} else {
if (node.left != null) {
if (node.left.left == null && node.left.right == null) {
node.left = null;
} else {
removeLeaves(node.left);
}
}
if (node.right != null) {
if (node.right.left == null && node.right.right == null) {
node.right = null;
} else {
removeLeaves(node.right);
}
}
}
return node;
}
此代码确保删除所有没有子节点的节点,并且还消除了对 isLeaf() 函数的需要。
我一直致力于从头开始创建二叉树,而不是使用 built-in 库。我正在研究一个名为 "pruneLeaves" 的函数。工作是移除树上的所有叶子;没有 children.
的节点当我使用断点单步执行函数时,它似乎在移除叶子,甚至打印出它确实在移除正确的节点。但是,当我之后在主函数中显示树时,节点仍然存在!
我已经尝试了几个小时来解决这个问题,我忽略了什么?!
程序输出:
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();
}
使用link:Deleting Leaves From a Binary Tree
我发现了我的代码中的错误并使用 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;
}
+1 是正确的答案(到目前为止我只找到了一个),但是您忘记了根的空方案,并且如果根本身没有子项也删除根。以下是我的做法 - 我使用了您的代码,然后确保它适合所有场景:
public void removeLeaves () {
if (root != null) {
removeLeaves (root);
} else {
return;
}
}
private Node removeLeaves (Node node) {
if (root.left == null && root.right == null) {
root = null;
} else {
if (node.left != null) {
if (node.left.left == null && node.left.right == null) {
node.left = null;
} else {
removeLeaves(node.left);
}
}
if (node.right != null) {
if (node.right.left == null && node.right.right == null) {
node.right = null;
} else {
removeLeaves(node.right);
}
}
}
return node;
}
此代码确保删除所有没有子节点的节点,并且还消除了对 isLeaf() 函数的需要。