帮助我了解不使用递归的有序遍历

小编典典

帮助我了解不使用递归的有序遍历

algorithm

我无需使用递归就可以理解预习遍历，但是我很难进行有序遍历。也许我似乎不明白，也许是因为我不了解递归的内部工作原理。

到目前为止，这是我尝试过的：

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

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

谢谢你的时间！

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

阅读 201

2020-07-28

共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

2020-07-28