从二叉树中删除叶子没有正确表示

我一直致力于从头开始创建二叉树，而不是使用内置库。 我正在开发一个名为“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.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(); } 

Answer 1

使用链接： 从二叉树中删除叶子

我在代码中发现了错误，并使用链接中给出的答案进行了纠正。

正确的代码如下：

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

Answer 2

+1是正确的答案（目前为止我只发现了一个），但你忘记了root的空方案，并且如果root本身没有子节点，也要删除root。 这是我如何做到的 – 我使用了你的代码然后确保它适合所有场景：

 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（）函数。