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

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