帮助我理解不使用递归的中序遍历 [英] Help me understand Inorder Traversal without using recursion

问题描述

我能够在不使用递归的情况下理解前序遍历，但是我很难理解中序遍历.我只是似乎不明白，也许是因为我还没有理解递归的内部工作.

I am able to understand preorder traversal without using recursion, but I'm having a hard time with inorder traversal. I just don't seem to get it, perhaps, because I haven't understood the inner working of recursion.

这是我迄今为止尝试过的:

This is what I've tried so far:

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 循环感觉不对.此外，一些元素被打印两次；可能我可以通过检查该节点之前是否已打印来解决这个问题，但这需要另一个变量，这又一次感觉不对.我哪里出错了?

The inner while-loop just doesn't feel right. Also, some of the elements are getting printed twice; may be I can solve this by checking if that node has been printed before, but that requires another variable, which, again, doesn't feel right. Where am I going wrong?

我没有尝试过后序遍历，但我想它是相似的，我也会在那里面临同样的概念障碍.

I haven't tried postorder traversal, but I guess it's similar and I will face the same conceptual blockage there, too.

感谢您的时间！

P.S.:Lifo 和 Node 的定义:

P.S.: Definitions of Lifo and 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

推荐答案

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

Start with the recursive algorithm (pseudocode) :

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

这是尾递归的一个明显例子，所以你可以很容易地把它变成一个while循环.

This is a clear case of tail recursion, so you can easily turn it into a while-loop.

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

剩下的是递归调用.递归调用的作用是将一个新的上下文推送到堆栈上，从头开始运行代码，然后检索上下文并继续做它正在做的事情.因此，您创建一个用于存储的堆栈和一个循环，该循环在每次迭代时确定我们是处于首次运行"情况(非空节点)还是返回"情况(空节点、非空堆栈)) 并运行适当的代码:

You're left with a recursive call. What the recursive call does is push a new context on the stack, run the code from the beginning, then retrieve the context and keep doing what it was doing. So, you create a stack for storage, and a loop that determines, on every iteration, whether we're in a "first run" situation (non-null node) or a "returning" situation (null node, non-empty stack) and runs the appropriate code:

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 链，其中包含与代码中的非终端递归一样多的案例.

The hard thing to grasp is the "return" part: you have to determine, in your loop, whether the code you're running is in the "entering the function" situation or in the "returning from a call" situation, and you will have an if/else chain with as many cases as you have non-terminal recursions in your code.

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

In this specific situation, we're using the node to keep information about the situation. Another way would be to store that in the stack itself (just like a computer does for recursion). With that technique, the code is less optimal, but easier to follow

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 

这篇关于帮助我理解不使用递归的中序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！