帮助我理解Inorder Traversal而不使用递归

Question

我能够理解preorder遍历而不使用递归,但我很难进行inorder遍历.我也许似乎没有得到它,因为我还没有理解递归的内在工作.

这是我到目前为止所尝试的:

def traverseInorder(node):
    lifo = Lifo()
    lifo.push(node)
    while True:
        if node is None:
            break
        if node.left is not None:
            lifo.push(node.left)
            node = node.left
            continue
        prev = node
        while True:
            if node is None:
                break
            print node.value
            prev = node
            node = lifo.pop()
        node = prev
        if node.right is not None:
            lifo.push(node.right)
            node = node.right
        else:
            break

内部的while循环感觉不对劲.此外,一些元素被打印两次; 也许我可以通过检查之前是否打印过该节点来解决这个问题,但这需要另一个变量,这也是感觉不对.我哪里错了？

我没有尝试过postorder遍历,但我猜它类似,我也将面临同样的概念障碍.

谢谢你的时间!

PS:Lifo和的定义Node:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Lifo:
    def __init__(self):
        self.lifo = ()
    def push(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        if len(self.lifo) == 0:
            return None
        ret, self.lifo = self.lifo
        return ret

Answer 1

从递归算法(伪代码)开始:

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

这是尾递归的一个明显例子,因此您可以轻松地将其转换为while循环.

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

你留下了一个递归的电话.递归调用的作用是在堆栈上推送新的上下文,从头开始运行代码,然后检索上下文并继续执行它正在执行的操作.因此,您为存储创建了一个堆栈,并在每次迭代时确定我们是处于"第一次运行"状态(非空节点)还是"返回"情况(空节点,非空堆栈) )并运行适当的代码:

traverse(node):
  stack = []
  while !empty(stack) || node != None do:
    if node != None do: // this is a normal call, recurse
      push(stack,node)
      node = node.left
    else // we are now returning: pop and print the current node
      node = pop(stack)
      print node.value
      node = node.right
    endif
  endwhile

难以理解的是"返回"部分:您必须在循环中确定您正在运行的代码是处于"进入功能"状态还是"从呼叫中返回"状态,并且您将if/else在您的代码中具有与非终端递归一样多的情况下的链.

在这种特定情况下,我们使用节点来保存有关情况的信息.另一种方法是将它存储在堆栈本身(就像计算机用于递归).使用该技术,代码不太理想,但更容易理解

traverse(node):
  // entry:
  if node == NULL do return
  traverse(node.left)
  // after-left-traversal:
  print node.value
  traverse(node.right)

traverse(node):
   stack = [node,'entry']
   while !empty(stack) do:
     [node,state] = pop(stack)
     switch state: 
       case 'entry': 
         if node == None do: break; // return
         push(stack,[node,'after-left-traversal']) // store return address
         push(stack,[node.left,'entry']) // recursive call
         break;
       case 'after-left-traversal': 
         print node.value;
         // tail call : no return address
         push(stack,[node.right,'entry']) // recursive call
      end
    endwhile 

Answer 2

这是一个简单的有序非递归c ++代码..

void inorder (node *n)
{
    stack s;

    while(n){
        s.push(n);
        n=n->left;
    }

    while(!s.empty()){
        node *t=s.pop();
        cout<<t->data;
        t=t->right;

        while(t){
            s.push(t);
            t = t->left;
        }
    }
}