我可以在没有递归和堆栈的情况下对二叉树进行中序遍历吗? [英] Can I do inorder traversal of a binary tree without recursion and stack?

问题描述

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

Can anyone give me a solution for traversing a binary tree in inorder without recursion and without using a stack?

推荐答案

第二次我认为这是正确的.除了通常的 node.left_child 和 node.right_child 之外，还需要 node.isRoot、node.isLeftChild 和 node.parent.

Second edit: I think this is right. Requires node.isRoot, node.isLeftChild, and node.parent, in addition to the usual node.left_child and node.right_child.

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

这篇关于我可以在没有递归和堆栈的情况下对二叉树进行中序遍历吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！