任何人都可以给我一个在不使用递归和不使用堆栈的情况下按顺序遍历二叉树的解决方案吗？
第二次编辑：我认为这是正确的。除了通常的node.left_child 和node.right_child 之外，还需要node.isRoot、node.isLeftChild 和node.parent。
state = "from_parent"
current_node = root
while (!done)
switch (state)
case "from_parent":
if current_node.left_child.exists
current_node = current_node.left_child
state = "from_parent"
else
state = "return_from_left_child"
case "return_from_left_child"
if current_node.right_child.exists
current_node = current_node.right_child
state = "from_parent"
else
state = "return_from_right_child"
case "return_from_right_child"
if current_node.isRoot
done = true
else
if current_node.isLeftChild
state = "return_from_left_child"
else
state = "return_from_right_child"
current_node = current_node.parent
如果你的树节点有父引用/指针，那么在遍历过程中跟踪你来自哪个节点，这样你就可以决定下一步去哪里。
在Python中：
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
self.parent = None
if self.left:
self.left.parent = self
if self.right:
self.right.parent = self
def inorder(self):
cur = self
pre = None
nex = None
while cur:
if cur.right and pre == cur.right:
nex = cur.parent
elif not cur.left or pre == cur.left:
yield cur.value # visit!
nex = cur.right or cur.parent
else:
nex = cur.left
pre = cur
cur = nex
root = Node(1,
Node(2, Node(4), Node(5)),
Node(3)
)
print([value for value in root.inorder()]) # [4, 2, 5, 1, 3]
如果您的树节点没有父引用/指针，那么您可以进行所谓的莫里斯遍历，这会暂时改变树，使没有右子节点的节点的
right在Python中：
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(self):
cur = self
while cur:
if cur.left:
pre = cur.left
while pre.right:
if pre.right is cur:
# We detect our mutation. So we finished
# the left subtree traversal.
pre.right = None
break
pre = pre.right
else: # prev.right is None
# Mutate this node, so it links to curr
pre.right = cur
cur = cur.left
continue
yield cur.value
cur = cur.right
root = Node(1,
Node(2, Node(4), Node(5)),
Node(3)
)
print([value for value in root.inorder()])
是的，可以。为此，您需要一个父指针才能提升树。
从tree_first()开始，继续使用tree_next()直到得到NULL。 完整代码：https://github.com/virtan/tree_closest
struct node {
int value;
node *left;
node *right;
node *parent;
};
node *tree_first(node *root) {
while(root && root->left)
root = root->left;
return root;
}
node *tree_next(node *p) {
if(p->right)
return tree_first(p->right);
while(p->parent) {
if(!p->parent->right || p->parent->right != p)
return p->parent;
else p = p->parent;
}
return 0;
}
组合器粉碎机Combo中使用的例程对于二叉树来说是非递归的，并且不使用堆栈和“向上”指针 - 仅使用两个分支指针。
这是按照 C 语言编写的伪代码。
当前状态是（P，E，N）。迭代从 (P,E,N) ← (NULL,Root,-) 开始，其中“N”不需要初始化。结束条件是“E == NULL”。迭代器称为“DOWN(P,E,N)”，形式为 (P,E,N) ← (E,N,-)。在叶节点上，有“FLIP(P,E,N)”，即 (P,E,N) ← (N,E,P)。根据遍历的情况，它也可以用在非叶节点上。否则，叶节点通常用 SPIN(P,E,N) 处理，即 (P,E,N) ← (-, (Head: Tail(E), Tail: P), Head(E)) 。这将返回 E 的访问计数并将其增加。在某些情况下，如果退出，您将执行 UNSPIN(P,E,N)，即 (P,E,N) ← (Head(E), (Head: Tail(E), Tail: N), -)，它还会返回访问计数并增加它。在这两种情况下，二叉树的模 3 都会增加。
在并发环境中，在使用 SPIN 或 UNSPIN 之前，必须等待节点的访问计数循环结束。因此，这也必须妥善管理。
在“Combo”的实现中，构造函数使用了子树哈希。因此，没有子树是重复的——甚至叶节点也不重复。它非常适合扩展到有理无限树，这将通过循环图实现。这就是意图。所以，理论上（如果你正确地扩大设计）你甚至可以用它来处理无限树——只要它们是有理数的。
正如这里有人已经说过的，这是可能的，但如果没有父指针则不行。父指针基本上允许您根据需要遍历“路径”，从而打印出节点。 但是为什么递归可以在没有父指针的情况下工作呢？好吧，如果你理解递归，它就会像这样（想象一下递归堆栈）：
recursion //going into
recursion
recursion
recursion
recursion //going back up
recursion
recursion
recursion
因此，当递归结束时，您就以相反的顺序打印了二叉树的所选一侧。