java 如何去除二叉树的叶子？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2635292/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I remove the leaves of a binary tree?
提问by flopex
I'm trying to remove all of the leaves. I know that leaves have no children, this is what I have so far.
我试图去除所有的叶子。我知道叶子没有孩子，这就是我迄今为止所拥有的。
public void removeLeaves(BinaryTree n){
if (n.left == null && n.right == null){
n = null;
}
if (n.left != null)
removeLeaves(n.left);
if (n.right != null)
removeLeaves(n.right);
}
回答by Heinzi
n = null;won't help you, since nis just a local variable of your function. Instead, you'd need to set n.left = null;or n.right = null;on the parent.
n = null;不会帮助你，因为n它只是你函数的一个局部变量。相反，您需要在父级上设置n.left = null;或n.right = null;。
I won't give you a complete solution, since this smells a lot like homework, but you could, for example, add a return value to your function to indicate whether the node in question is a leaf or not and take appropriate actions in the parent (after the call to removeLeaves).
我不会给你一个完整的解决方案，因为这闻起来很像家庭作业，但是你可以，例如，向你的函数添加一个返回值来指示有问题的节点是否是叶节点，并在父级（在调用 之后removeLeaves）。
回答by polygenelubricants
It's much easier if you break this down like this:
如果你这样分解它会容易得多：
public void removeLeaves(BinaryTree n){
if (n.left != null) {
if (n.left.isLeaf()) {
n.removeLeftChild();
} else {
removeLeaves(n.left);
}
}
// repeat for right child
// ...
}
isLeaf, removeLeftChildand removeRightChildshould be trivial to implement.
isLeaf，removeLeftChild并且removeRightChild应该很容易实现。
回答by Matthew Flaschen
Instead of n = null, it should be:
而不是 n = null，它应该是：
if(n.parent != null)
{
if(n.parent.left == n)
{
n.parent.left = null;
}
else if(n.parent.right == n)
{
n.parent.right == null);
}
}
回答by Petar Minchev
Since Java passes references by values n = null;simply does not work. With this line n was pointing to the leaf and now points to nothing. So you aren't actually removing it from the parent, you are just rerouting a dummy local reference. For the solution do what Matthew suggested.
由于 Java 通过值传递引用n = null;根本行不通。这条线 n 指向叶子，现在指向空。所以你实际上并没有从父级中删除它，你只是重新路由一个虚拟的本地引用。对于解决方案，请按照 Matthew 的建议进行操作。
回答by Prateek Joshi
Here's a simple javamethod to delete leaf nodesfrom binary tree
这是从二叉树中删除叶节点的简单java方法
public BinaryTreeNode removeLeafNode(BinaryTreeNode root) {
if (root == null)
return null;
else {
if (root.getLeft() == null && root.getRight() == null) { //if both left and right child are null
root = null; //delete it (by assigning null)
} else {
root.setLeft(removeLeafNode(root.getLeft())); //set new left node
root.setRight(removeLeafNode(root.getRight())); //set new right node
}
return root;
}
}
回答by Ishi
This should work-
这应该有效-
public boolean removeLeaves(Node n){
boolean isLeaf = false;
if (n.left == null && n.right == null){
return true;
//n = null;
}
if (n!=null && n.left != null){
isLeaf = removeLeaves(n.left);
if(isLeaf) n.left=null; //remove left leaf
}
if (n!=null && n.right != null){
isLeaf = removeLeaves(n.right);
if(b) n.right=null; //remove right leaf
}
return false;
}
回答by abhineet
/* @author abhineet*/
public class DeleteLeafNodes {
static class Node{
int data;
Node leftNode;
Node rightNode;
Node(int value){
this.data = value;
this.leftNode = null;
this.rightNode = null;
}
}
public static void main(String[] args) {
Node root = new Node(1);
Node lNode = new Node(2);
lNode.leftNode = new Node(4);
root.leftNode = lNode;
Node rNode = new Node(3);
rNode.rightNode = new Node(5);
root.rightNode = rNode;
printTree(root);
deleteAllLeafNodes(root, null,0);
System.out.println("After deleting leaf nodes::");
printTree(root);
}
public static void deleteAllLeafNodes(Node root, Node parent, int direction){
if(root != null && root.leftNode == null && root.rightNode == null){
if(direction == 0){
parent.leftNode = null;
}else{
parent.rightNode = null;
}
}
if(root != null && (root.leftNode != null || root.rightNode != null)){
deleteAllLeafNodes(root.leftNode, root, 0);
deleteAllLeafNodes(root.rightNode, root, 1);
}
}
public static void printTree(Node root){
if(root != null){
System.out.println(root.data);
printTree(root.leftNode);
printTree(root.rightNode);
}
}
}
