Java 如何迭代二叉树？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2942517/
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 iterate over Binary Tree?
提问by unj2
Right now I have
现在我有
private static void iterateall(BinaryTree foo) {
if(foo!= null){
System.out.println(foo.node);
iterateall(foo.left);
iterateall(foo.right);
}
}
Can you change it to Iteration instead of a recursion?
你能把它改成迭代而不是递归吗？
采纳答案by Konrad Rudolph
Can you change it to Iteration instead of a recursion?
你能把它改成迭代而不是递归吗？
You can, using an explicit stack. Pseudocode:
您可以使用显式堆栈。伪代码：
private static void iterateall(BinaryTree foo) {
Stack<BinaryTree> nodes = new Stack<BinaryTree>();
nodes.push(foo);
while (!nodes.isEmpty()) {
BinaryTree node = nodes.pop();
if (node == null)
continue;
System.out.println(node.node);
nodes.push(node.right);
nodes.push(node.left);
}
}
But this isn't really superior to the recursive code (except for the missing base condition in your code).
但这并不比递归代码更好（除了代码中缺少的基本条件）。
回答by Thomas Padron-McCarthy
Yes, you can change it to iteration instead of a recursion, but then it gets much more complicated, since you need to have some way to remember where to go backfrom the current node. In the recursive case, the Java call stack handles that, but in an iterative solution you need to build your own stack, or perhaps store back pointers in the nodes.
是的，你可以把它改成迭代而不是递归的，但后来它变得更加复杂，因为你需要有一些方法来记住哪里去回从当前节点。在递归情况下，Java 调用堆栈会处理它，但在迭代解决方案中，您需要构建自己的堆栈，或者可能在节点中存储返回指针。
回答by Grzegorz Oledzki
As with every recursion, you can use additional data structure - i.e. the stack. A sketch of the solution:
与每次递归一样，您可以使用额外的数据结构 - 即堆栈。解决方案的草图：
private static void visitall(BinaryTree foo) {
Stack<BinaryTree> iterationStack = new Stack<BinaryTree>();
iterationStack.push(foo);
while (!iterationStack.isEmpty()) {
BinaryTree current = iterationStack.pop();
System.out.println(current.node);
current.push(current.right); // NOTE! The right one comes first
current.push(current.left);
}
}
回答by polygenelubricants
What you're looking for is a successor algorithm.
您正在寻找的是后继算法。
Here's how it can be defined:
以下是它的定义方式：
- First rule: The first node in the tree is the leftmost node in the tree.
- Next rule: The successor of a node is:
- Next-R rule: If it has a right subtree, the leftmost node in the right subtree.
- Next-U rule: Otherwise, traverse up the tree
- If you make a right turn (i.e. this node was a left child), then that parent node is the successor
- If you make a left turn (i.e. this node was a right child), continue going up.
- If you can't go up anymore, then there's no successor
- 第一条规则：树中的第一个节点是树中最左边的节点。
- 下一条规则：节点的后继是：
- Next-R 规则：如果有右子树，则为右子树中最左边的节点。
- Next-U 规则：否则，向上遍历树
- 如果你右转（即这个节点是一个左孩子），那么这个父节点就是后继节点
- 如果你左转（即这个节点是一个右孩子），继续往上走。
- 上不去就没有接班人
As you can see, for this to work, you need a parent node pointer.
如您所见，要使其正常工作，您需要一个父节点指针。
Example:
例子：
- First rule: The first node in the tree is the leftmost node in the tree:
(1) - Next-U rule: Since
(1)has no right subtree, we go up to(3). This is a right turn, so(3)is next. - Next-R rule: Since
(3)has a right subtree, the leftmost node in that subtree is next:(4). - Next-U rule: Since
(4)has no right subtree, we go up to(6). This is a right turn, so next is(6). - Next-R rule: Since
(6)has a right subtree, the leftmost node in that subtree is next:(7). - Next-U rule: Since
(7)has no right subtree, we go up to(6). This is a left turn, so we continue going up to(3). This is a left turn, so we continue going up to(8). This is a right turn, so next is(8). - Next-R rule: Since
(8)has a right subtree, the leftmost node in that subtree is next:(10). - Next-R rule: Since
(10)has a right subtree, the leftmost node in that subtree is next:(13). - Next-U rule: Since
(13)has no right subtree, we go up to(14). This is a right turn, so next is(14). - Next-U rule: Since
(14)has no right subtree, we go up to(10). This is a left turn, so we continue going up to(8). This is a left turn, so we want to continue going up, but since(8)has no parent, we've reached the end.(14)has no successor.
- 第一条规则：树中的第一个节点是树中最左边的节点：
(1) - Next-U 规则：由于
(1)没有右子树，我们上到(3)。这是一个右转，(3)接下来也是。 - Next-R 规则：由于
(3)有一个右子树，该子树中最左边的节点是 next:(4)。 - Next-U 规则：由于
(4)没有右子树，我们上到(6)。这是一个右转，所以接下来是(6)。 - Next-R 规则：由于
(6)有一个右子树，该子树中最左边的节点是 next:(7)。 - Next-U 规则：由于
(7)没有右子树，我们上到(6)。这是一个左转，所以我们继续往上走(3)。这是一个左转，所以我们继续向上走(8)。这是一个右转，所以接下来是(8)。 - Next-R 规则：由于
(8)有一个右子树，该子树中最左边的节点是 next:(10)。 - Next-R 规则：由于
(10)有一个右子树，该子树中最左边的节点是 next:(13)。 - Next-U 规则：由于
(13)没有右子树，我们上到(14)。这是一个右转，所以接下来是(14)。 - Next-U 规则：由于
(14)没有右子树，我们上到(10)。这是一个左转，所以我们继续向上走(8)。这是一个左转，所以我们想继续往上走，但由于(8)没有父母，我们已经走到了尽头。(14)没有继任者。
Pseudocode
伪代码
Node getLeftMost(Node n)
WHILE (n.leftChild != NULL)
n = n.leftChild
RETURN n
Node getFirst(Tree t)
IF (t.root == NULL) RETURN NULL
ELSE
RETURN getLeftMost(t.root);
Node getNext(Node n)
IF (n.rightChild != NULL)
RETURN getLeftMost(n.rightChild)
ELSE
WHILE (n.parent != NULL AND n == n.parent.rightChild)
n = n.parent;
RETURN n.parent;
PROCEDURE iterateOver(Tree t)
Node n = getFirst(t);
WHILE n != NULL
visit(n)
n = getNext(n)
Java code
Java代码
Here's a simple implementation of the above algorithm:
下面是上述算法的简单实现：
public class SuccessorIteration {
static class Node {
final Node left;
final Node right;
final int key;
Node parent;
Node(int key, Node left, Node right) {
this.key = key;
this.left = left;
this.right = right;
if (left != null) left.parent = this;
if (right != null) right.parent = this;
}
Node getLeftMost() {
Node n = this;
while (n.left != null) {
n = n.left;
}
return n;
}
Node getNext() {
if (right != null) {
return right.getLeftMost();
} else {
Node n = this;
while (n.parent != null && n == n.parent.right) {
n = n.parent;
}
return n.parent;
}
}
}
}
Then you can have a test harness like this:
然后你可以有一个这样的测试工具：
static Node C(int key, Node left, Node right) {
return new Node(key, left, right);
}
static Node X(int key) { return C(key, null, null); }
static Node L(int key, Node left) { return C(key, left, null); }
static Node R(int key, Node right) { return C(key, null, right); }
public static void main(String[] args) {
Node n =
C(8,
C(3,
X(1),
C(6,
X(4),
X(7)
)
),
R(10,
L(14,
X(13)
)
)
);
Node current = n.getLeftMost();
while (current != null) {
System.out.print(current.key + " ");
current = current.getNext();
}
}
This prints:
这打印：
1 3 4 6 7 8 10 13 14
See also
也可以看看
回答by Ivan
Sure, you have two general algorithms, depth first searchand breadth first search.
If order of traversal is not important to you, go for breadth first, it's easier to implement for iteration. You're algorithm should look something like this.
如果遍历顺序对您来说不重要，请先考虑广度，这样更容易实现迭代。你的算法应该是这样的。
LinkedList queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()){
Object element = queue.remove();
queue.add(element.left);
queue.add(element.right);
// Do your processing with element;
}
回答by Steven Spungin
I had a tree (not binary) and eventually solved it with this very simple algorithm. The other solutions used leftand rightthat were not relevant or even implemented in the examples.
我有一棵树（不是二进制），最终用这个非常简单的算法解决了它。使用left和right的其他解决方案在示例中不相关甚至没有实现。
My structure was: nodes with each parent containing list of children, and each child containing a pointer back to the parent. Pretty common...
我的结构是：每个父节点包含子节点列表，每个子节点包含一个指向父节点的指针。很常见...
After a bunch of refactoring, I came up with the following example using Kotlin. It should be trivial to convert to your language of choice.
经过一系列重构，我想出了以下使用 Kotlin 的示例。转换为您选择的语言应该很简单。
Helper Functions
辅助函数
First, the node must provide 2 simple functions. This will vary depending on your Node class' implementation:
首先，节点必须提供2个简单的功能。这将取决于您的 Node 类的实现：
leftMost- This is the first child node. If that node has children, it's first child, etc. If no children, return this.
leftMost- 这是第一个子节点。如果该节点有子节点，则它是第一个子节点，等等。如果没有子节点，则返回this。
fun leftMost(): Node {
if (children.isEmpty()) {
return this
}
var n = this
while (n.children.isNotEmpty()) {
n = n.children[0]
}
return n
}
nextSibling- The next sibling of this node, or NULL
nextSibling- 此节点的下一个兄弟节点，或 NULL
fun nextSibling(): Node? {
if (parent == null) return null
val siblingIndex = parent.children.indexOf(this) + 1
return if (siblingIndex < parent.children.size) {
parent.children[siblingIndex]
} else {
null
}
}
The Iteration
迭代
The iteration starts with the leftMost of the root.
迭代从根的 leftMost 开始。
Then inspect the next sibling.
然后检查下一个兄弟姐妹。
- If NOT NULL the sibling's leftMostChild
- If NULL, the parent, and if the parent is NULL, we are done.
- 如果 NOT NULL 兄弟的 leftMostChild
- 如果为 NULL，则为父级，如果父级为 NULL，我们就完成了。
That's it.
就是这样。
Here is a Kotlin iterator function.
这是一个 Kotlin 迭代器函数。
fun iterator(): Iterator<Node> {
var next: Node? = this.leftMost()
return object : Iterator<Node> {
override fun hasNext(): Boolean {
return next != null
}
override fun next(): Node {
val ret = next ?: throw NoSuchElementException()
next = ret.nextSibling()?.leftMost() ?: ret.parent
return ret
}
}
}
Here is the same next() function, but without the Kotlin shorthand for dealing with NULL values, for those that are not hip to the syntax.
这是相同的 next() 函数，但没有用于处理 NULL 值的 Kotlin 速记，对于那些不符合语法的人。
fun next(): Node {
val ret = next
if (ret == null) throw NoSuchElementException()
val nextSibling = ret.nextSibling()
if (nextSibling != null) {
next = nextSibling.leftMost()
}
else {
next = ret.parent
}
return ret
}
