java 递归打印二叉搜索树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29735465/
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
printing binary search tree inorder recursively
提问by Chalupa
I have the code for printing a the contents of a binary search tree in-order (ascending) using recursion. I understand that the helper method calls on the recursive method with root as the beginning node value. But I don't understand how the recursive code works conceptually. Could anyone explain?
我有使用递归按顺序（升序）打印二叉搜索树内容的代码。我知道辅助方法调用递归方法，以 root 作为起始节点值。但我不明白递归代码在概念上是如何工作的。谁能解释一下？
//ascend method that prints values in the tree in ascending order
//recursive method below
public void printAscending() {
printAscending(root);
}
private void printAscending(Node node) {
if(node != null) {
printAscending(node.left);
System.out.println(node.data);
printAscending(node.right);
}
}
回答by Ashley Frieze
// public entry point, reuses the recursive function
public void printAscending() {
printAscending(root);
}
// print this node and all of its descendants
private void printAscending(Node node) {
// is there actually a node here
// or was this called from a node with no children
if(node != null) {
// print everything that's earlier than this node
printAscending(node.left);
// print this node's value
System.out.println(node.data);
// print everything that's afterthan this node
printAscending(node.right);
}
}
回答by Jay Bosamiya
Consider the following (trivial) tree:
考虑以下（平凡的）树：
1
You'd be calling the function on the one (the root) and it is obvious to see that the result is 1.
您将在一个（根）上调用该函数，很明显结果是1.
Now consider the following (slightly larger) tree:
现在考虑以下（稍大的）树：
2
1
The root is now 2and the output (manually traced by hand) gives 1 2. (spaces added for clarity)
根现在2是，输出（手动跟踪）给出1 2. （为清楚起见添加了空格）
Similar manual tracing on the following gives us 1 2 3:
以下类似的手动跟踪为我们提供了1 2 3：
2
1 3
So we can now see that for small testcases, it seems to work fine.
所以我们现在可以看到，对于小型测试用例，它似乎工作正常。
Let's try proving it for larger testcases.
让我们尝试为更大的测试用例证明它。
For any null node (i.e. if we are at a non-existant tree/subtree) we just exit.
对于任何空节点（即，如果我们在一个不存在的树/子树上），我们就退出。
For any non-null node, the printAscending(node.left)line is called first. This line MUST finish execution before anything else runs. This calls the printAscending()function using node.leftas parameter which is equivalent to just looking at the left subtree of the current node, finishing the work there and then continuing the code. We can keep going down the left until we reach a null node. At this point of time, it moves back upwards, resuming from where it had stopped off. It runs System.out.println(node.data)which gives the output of a single node and then runs printAscending(node.right). This causes it to enter the right subtree of the current node. Note that in this subtree, it runs the complete code (i.e. runs the left, center and then right parts). Once it is done running through the right subtree, it backs out of the subtree and the current node. This makes the node just above it (the parent) move on to the next part of the code.
对于任何非空节点，printAscending(node.left)首先调用该行。此行必须在其他任何运行之前完成执行。这printAscending()使用node.leftas 参数调用函数，相当于只查看当前节点的左子树，在那里完成工作，然后继续代码。我们可以继续向左走，直到到达一个空节点。此时，它又往回移动，从停下的地方恢复过来。它运行System.out.println(node.data)给出单个节点的输出，然后运行printAscending(node.right). 这导致它进入当前节点的右子树。请注意，在此子树中，它运行完整的代码（即运行左侧、中间和右侧部分）。一旦它完成通过右子树的运行，它就会退出子树和当前节点。这使得它上面的节点（父节点）移动到代码的下一部分。
If you follow a similar working, you'll see that the whole left subtree of the root is processed first, then the root is printed and then whole right subtree is processed.
如果您遵循类似的工作，您将看到首先处理根的整个左子树，然后打印根，然后处理整个右子树。
回答by Chetan Sachdeva
public void printInOrder() {
if (left != null) {
left.printInOrder();
}
System.out.println(data);
if (right != null) {
right.printInOrder();
}
}
