我如何迭代二叉树？
现在我有
private static void iterateall(BinaryTree foo) { if(foo!= null){ System.out.println(foo.node); iterateall(foo.left); iterateall(foo.right); } } 你能把它改成Iteration而不是递归吗？
你能把它改成Iteration而不是递归吗？
您可以使用显式堆栈。 伪代码：
private static void iterateall(BinaryTree foo) { Stack nodes = new Stack (); 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); } }
但这并不比递归代码优越（除了代码中缺少的基本条件）。
您正在寻找的是后继算法。
以下是它的定义方式：
- 第一条规则 ：树中的第一个节点是树中最左边的节点。
- 下一条规则 ：节点的后继者是：
- Next-R规则 ：如果它有一个右子树，则右子树中最左边的节点。
- Next-U规则 ：否则，遍历树
- 如果右转（即此节点是左子节点），则该父节点是后继节点
- 如果你左转（即这个节点是一个正确的孩子），继续上升。
- 如果你再也不能上去了，那就没有继任者了
如您所见，为此，您需要一个父节点指针。
例：
- 第一条规则 ：树中的第一个节点是树中最左边的节点：
(1) - Next-U规则 ：由于
(1)没有正确的子树，我们最多(3)。 这是一个右转，所以(3)接下来。 - Next-R规则 ：由于
(3)有一个右子树，该子树中最左边的节点是下一个：(4)。 - Next-U规则 ：由于
(4)没有正确的子树，我们最多(6)。 这是右转，接下来是(6)。 - Next-R规则 ：由于
(6)具有右子树，该子树中最左边的节点是下一个：(7)。 - Next-U规则 ：由于
(7)没有正确的子树，我们最多(6)。 这是一个左转，所以我们继续上升到(3)。 这是一个左转，所以我们继续上升到(8)。 这是右转，接下来是(8)。 - Next-R规则 ：由于
(8)具有右子树，该子树中最左边的节点是下一个：(10)。 - Next-R规则 ：由于
(10)具有右子树，该子树中最左边的节点是下一个：(13)。 - Next-U规则 ：由于
(13)没有正确的子树，我们最多(14)。 这是右转，接下来是(14)。 - Next-U规则 ：由于
(14)没有正确的子树，我们最多(10)。 这是一个左转，所以我们继续上升到(8)。 这是一个左转，所以我们想继续上升，但由于(8)没有父母，我们已经到了最后。(14)没有inheritance人。
伪代码
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代码
这是上述算法的简单实现：
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; } } } }
然后你就可以拥有这样的测试工具：
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(); } }
这打印：
1 3 4 6 7 8 10 13 14
也可以看看
- 在ideone.com上完成Java列表和输出
当然，你有两个通用算法， 深度优先搜索和广度优先搜索 。
如果遍历顺序对您来说并不重要，请先考虑广度，实现迭代更容易。 你的算法看起来应该是这样的。
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; }
与每次递归一样，您可以使用其他数据结构 – 即堆栈。 解决方案草图 ：
private static void visitall(BinaryTree foo) { Stack iterationStack = new Stack (); 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); } }
是的，您可以将其更改为迭代而不是递归，但随后会变得更加复杂，因为您需要有一些方法来记住从当前节点返回的位置。 在递归的情况下，Java调用堆栈处理它，但在迭代解决方案中，您需要构建自己的堆栈，或者可能在节点中存储返回指针。
我有一棵树（不是二进制），最终用这个非常简单的算法解决了它。 左侧和右侧使用的其他解决方案在示例中不相关或甚至未实现。
我的结构是：节点，每个父节点包含子节点列表，每个子节点包含一个指向父节点的指针。 很常见……
在一堆重构之后，我想出了使用Kotlin的以下示例。 转换为您选择的语言应该是微不足道的。
助手function
首先，节点必须提供2个简单的function。 这取决于您的Node类的实现：
leftMost – 这是第一个子节点。 如果该节点有子节点，则它是第一个子节点等。如果没有子节点，则返回此节点。
fun leftMost(): Node { if (children.isEmpty()) { return this } var n = this while (n.children.isNotEmpty()) { n = n.children[0] } return n }
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 } }
迭代
迭代从root的leftMost开始。
然后检查下一个兄弟姐妹。
- 如果NOT NULL则是兄弟的leftMostChild
- 如果是NULL，那么父，如果父是NULL，我们就完成了。
而已。
这是一个Kotlin迭代器函数。
fun iterator(): Iterator { var next: Node? = this.leftMost() return object : Iterator { override fun hasNext(): Boolean { return next != null } override fun next(): Node { val ret = next ?: throw NoSuchElementException() next = ret.nextSibling()?.leftMost() ?: ret.parent return ret } } }
这是相同的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 }