我能否在没有递归和堆栈的情况下进行二叉树的中序遍历？

Question

有没有人能给我一个不使用递归和栈的中序遍历二叉树的解决方案？

- Gautham

---

如果你能做到，那就不会是二叉树。 - vittore

这不是作业吗？在你的情况下，计数器算作堆栈吗？ - Gabriel Ščerbák

@Jim Lewis 我不知道这个，谢谢。http://en.wikipedia.org/wiki/Threaded_binary_tree - stacker

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

- mbeckish

---

我很确定这个会在树的深度大于2时出现问题。 - Daniel Spiewak

你比我先完成了。但请注意，这仅在字段node.parent存在时才有效，也就是说，节点知道其父节点。这是二叉树定义中允许的，但不是必需的。 - Beta

如果你有node.parent，你就不需要node.isRoot。另外，我认为你可以不用node.isLeftChild。 - Beta

@mbeckish 真是不可思议，特别是如果这是你脑海中的即兴表现。 - Bazooka

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. 单线程树

如果您的树节点没有父引用/指针，则可以进行所谓的Morris遍历，它会暂时改变树的结构，使没有右子节点的节点的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()])

- trincot

Answer 3

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

- Igor Milyakov

Answer 4

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

答案是否定的。（根据经典定义）

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

编辑： 或者如已经展示的线索化二叉树，

- stacker

Answer 5

可以的。为了做到这一点，您需要一个父指针以便上升树。

- 1337c0d3r

Answer 6

正如这里已经有人提到的，它是可能的，但没有父指针是不行的。父指针基本上允许您遍历“路径”，因此可以打印出节点。 但是为什么递归可以在没有父指针的情况下工作呢？如果您理解递归，它大致是这样的（想象一下递归堆栈）：

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

所以当递归结束时，您已经按相反的顺序打印了二叉树的选择侧。

- RecursionSnake

---

OP明确要求不涉及递归的内容。 - DarthCadeus