用Java计算树中的节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/547622/
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
Counting nodes in a tree in Java
提问by
First of all, I swear this is not homework, it's a question I was asked in an interview. I think I made a mess of it (though I did realise the solution requires recursion). Here is the question:
首先，我发誓这不是作业，这是我在面试中被问到的问题。我想我把它弄得一团糟（尽管我确实意识到解决方案需要递归）。这是问题：
Implement the count() method which returns the number of nodes in a tree. If a node doesn't have either a left or right child, the relevant getXXChild()method will return null
实现 count() 方法，该方法返回树中的节点数。如果一个节点既没有左孩子也没有右孩子，相关的getXXChild()方法将返回null
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
// Implement me
}
}
My reason for asking the question is simply curious to see the correct solution, and thereby measure how bad mine was.
我提出这个问题的原因只是想看看正确的解决方案，从而衡量我的问题有多糟糕。
Cheers, Tony
干杯，托尼
回答by David Hanak
A trivial recursive solution:
一个简单的递归解决方案：
int count() {
Tree l = getLeftTree();
Tree r = getRightTree();
return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0);
}
A less trivial non-recursive one:
一个不太重要的非递归的：
int count() {
Stack<Tree> s = new Stack<Tree>();
s.push(this);
int cnt = 0;
while (!s.empty()) {
Tree t = s.pop();
cnt++;
Tree ch = getLeftTree();
if (ch != null) s.push(ch);
ch = getRightTree();
if (ch != null) s.push(ch);
}
return cnt;
}
The latter is probably slightly more memory-efficient, because it replaces recursion with a stack and an iteration. It's also probably faster, but its hard to tell without measurements. A key difference is that the recursive solution uses the stack, while the non-recursive solution uses the heap to store the nodes.
后者可能稍微更节省内存，因为它用堆栈和迭代代替了递归。它也可能更快，但如果没有测量就很难判断。一个关键的区别是递归解决方案使用堆栈，而非递归解决方案使用堆来存储节点。
Edit:Here's a variant of the iterative solution, which uses the stack less heavily:
编辑：这是迭代解决方案的一个变体，它较少使用堆栈：
int count() {
Tree t = this;
Stack<Tree> s = new Stack<Tree>();
int cnt = 0;
do {
cnt++;
Tree l = t.getLeftTree();
Tree r = t.getRightTree();
if (l != null) {
t = l;
if (r != null) s.push(r);
} else if (r != null) {
t = r;
} else {
t = s.empty() ? null : s.pop();
}
} while (t != null);
return cnt;
}
Whether you need a more efficient or a more elegant solution naturally depends on the size of your trees and on how often you intend to use this routine. Rembemer what Hoare said: "premature optimization is the root of all evil."
您是否需要更高效或更优雅的解决方案自然取决于您的树的大小以及您打算使用此例程的频率。Rembemer Hoare 所说：“过早的优化是万恶之源。”
回答by Outlaw Programmer
Something like this should work:
这样的事情应该工作：
int count()
{
int left = getLeftChild() == null ? 0 : getLeftChild().count();
int right = getRightChild() == null ? 0 : getRightCHild().count();
return left + right + 1;
}
回答by Jeff Kotula
This is a standard recursion problem:
这是一个标准的递归问题：
count():
cnt = 1 // this node
if (haveRight) cnt += right.count
if (haveLeft) cnt += left.count
return cnt;
Very inefficient, and a killer if the tree is very deep, but that's recursion for ya...
非常低效，如果树很深，这是一个杀手，但这对你来说是递归......
回答by Blorgbeard is out
int count() {
Tree right = getRightChild();
Tree left = getLeftChild();
int c = 1; // count yourself!
if ( right != null ) c += right.count(); // count sub trees
if ( left != null ) c += left.count(); // ..
return c;
}
回答by Steven Robbins
return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;
Or something like that.
或类似的东西。
回答by achinda99
You can count the tree by traversing it many ways. Simply preorder traversal, the code would be (based on the functions you defined):
您可以通过多种方式遍历树来计算树的数量。简单的预序遍历，代码将是（基于您定义的函数）：
int count() {
count = 1;
if (this.getLeftChild() != null)
count += this.getLeftChild().count();
if (this.getRightChild() != null)
count += this.getRightChild().count();
return count;
}
回答by mannicken
int count()
{
int retval = 1;
if(null != getRightChild()) retval+=getRightChild().count();
if(null != getLeftChild()) retval+=getLeftChild().count();
return retval;
}
God I hope I didn't make a mistake.
上帝，我希望我没有犯错。
EDIT: I did actually.
编辑：我确实做到了。
回答by OscarRyz
I like this better because it reads:
我更喜欢这个，因为它写着：
return count for left + count for rigth + 1
返回左计数 + 右计数 + 1
int count() {
return countFor( getLeftChild() ) + countFor( getRightChild() ) + 1;
}
private int countFor( Tree tree ) {
return tree == null ? 0 : tree.count();
}
A little more towards literate programming.
对文学编程多一点。
BTW, I don't like the getter/setter convention that is so commonly used on Java, I think a using leftChild()instead would be better:
顺便说一句，我不喜欢在 Java 上如此常用的 getter/setter 约定，我认为使用leftChild()会更好：
return countFor( leftChild() ) + countFor( rightChild() ) + 1;
Just like Hoshua Bloch explains here http://www.youtube.com/watch?v=aAb7hSCtvGwat min. 32:03
就像 Hoshua Bloch 在这里解释的那样http://www.youtube.com/watch?v=aAb7hSCtvGwat min. 32:03
If you get it rigth your code reads...
如果你理解正确，你的代码就会读...
BUT, I have to admit the get/set convention is now almost part of the language. :)
但是，我不得不承认 get/set 约定现在几乎是语言的一部分。:)
For many other parts, following this strategy creates self documenting code, which is something good.
对于许多其他部分，遵循此策略会创建自文档化代码，这是一件好事。
Tony: I wonder, what was your answer in the interview.
托尼：我想知道，你在采访中的回答是什么。
回答by Ben Hardy
Of course, if you want to avoid visiting every node in your tree when you count, and processing time is worth more to you than memory, you can cheat by creating your counts as you build your tree.
当然，如果您想在计数时避免访问树中的每个节点，并且处理时间对您来说比内存更有价值，那么您可以通过在构建树时创建计数来作弊。
Have an int count in each node, initialized to one, which respresents the number of nodes in the subtree rooted in that node.
When you insert a node, before returning from your recursive insert routine, increment the count at the current node.
在每个节点中有一个 int 计数，初始化为 1，表示以该节点为根的子树中的节点数。
插入节点时，在从递归插入例程返回之前，增加当前节点的计数。
i.e.
IE
public void insert(Node root, Node newNode) {
if (newNode.compareTo(root) > 1) {
if (root.right != null)
insert(root.right, newNode);
else
root.right = newNode;
} else {
if (root.left != null)
insert(root.left, newNode);
else
root.left = newNode;
}
root.count++;
}
Then getting the count from any point just involves a lookup of node.count
然后从任何点获取计数只需要查找 node.count
回答by user66322
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
return 1
+ getRightChild() == null? 0 : getRightChild().count()
+ getLeftChild() == null? 0 : getLeftChild().count();
}
}
