我可以在没有递归和堆栈的情况下对二叉树进行中序遍历吗？

Question

谁能给我一个在不使用递归和不使用堆栈的情况下按顺序遍历二叉树的解决方案？

Answer 1

第二次编辑：我认为这是正确的。除了通常的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

Answer 2

1.双线程树

如果你的树节点有父引用/指针，那么在遍历过程中跟踪你来自哪个节点，这样你就可以决定下一步去哪里。

在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]

2.单线程树

如果你的树节点没有父引用/指针，那么你可以进行所谓的莫里斯遍历，这会暂时改变树，使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()])

Answer 3

由于遍历 二叉树 需要某种状态（在访问后继节点后返回的节点），这可能由递归隐含的堆栈提供（或由数组显式提供）。

答案是否定的，你不能。 （根据经典定义）

以迭代方式最接近二叉树遍历的可能是使用 堆

编辑：
或者如已经显示的 线程二叉树 ，

Answer 4

是的，你可以。为此，您需要一个父指针才能提升树。

Answer 5

从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;
}

Answer 6

组合器处理程序 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”的实现中，构造函数使用子树散列。因此，没有子树是重复的——甚至叶节点也不重复。它非常适合扩展到有理无限树，这将通过循环图实现。这就是意图。因此，从理论上讲（如果您正确扩展设计）您甚至可以使用它来处理无限树 - 前提是它们是有理数的。

Answer 7

正如这里有人已经说过的，这是可能的，但如果没有父指针则不行。父指针基本上允许您根据需要遍历“路径”，从而打印出节点。
但是为什么递归可以在没有父指针的情况下工作呢？好吧，如果您理解递归，它会是这样的（想象一下递归堆栈）：

  recursion //going into
   recursion
    recursion
     recursion 
     recursion //going back up
    recursion
   recursion
  recursion

因此，当递归结束时，您就以相反的顺序打印了二叉树的所选一侧。