二叉树后序遍历的迭代过程

Question

我做了二叉树后序遍历python的递归过程。这是代码。

from collections import namedtuple 
from sys import stdout 

Node = namedtuple('Node', 'data, left, right') 
tree = Node(1, 
      Node(2, 
       Node(4, 
         Node(7, None, None), 
         None), 
       Node(5, None, None)), 
      Node(3, 
       Node(6, 
         Node(8, None, None), 
         Node(9, None, None)), 
       None)) 


def printwithspace(i): 
    stdout.write("%i " % i) 


def postorder(node, visitor = printwithspace): 

    if node: 
     print "%d-->L"%node.data 
     postorder(node.left, visitor) 
     print "%d-->R"%node.data 
     postorder(node.right, visitor) 
     print "Root--%d"%node.data 

    else: 
     print "Null" 

stdout.write('\n postorder: ') 
postorder(tree) 

stdout.write('\n') 

现在，我想对PYTHON中的二叉树后序遍历做一个迭代过程。有人能帮忙吗？

在此先感谢。

Answer 1

下面的代码应该可以工作。基本上，您可以使用堆栈为节点执行深度优先搜索。 此外，您还有第二个堆栈，它并行存储节点是否已被扩展。

def postorder_iteratively(node): 
    stack = [node] 
    expanded = [False] 
    while stack: 
     while stack and not stack[-1]:   #remove "non-existent" nodes from the top 
      stack = stack[:-1] 
      expanded = expanded[:-1] 
     if stack and not expanded[-1]:   #expand node 
      stack += [stack[-1].right, stack[-1].left] 
      expanded[-1] = True 
      expanded += [False, False] 
     elif stack and expanded[-1]:   #if node has been expanded already, print it 
      print stack[-1].data 
      stack = stack[:-1] 
      expanded = expanded[:-1] 

Answer 2

下面是代码

def postorder_traverse(root): 
    result = [] 
    list = [] #simply use list to mimic stack 
    visited_node = None 
    cur_node = root 

    while len(list) > 0 or cur_node is not None: 
     if cur_node is not None: 
      #remember the middle node by "pushing" it to the stack 
      list.append(cur_node) 
      cur_node = cur_node.left 
     else: 
      middle_node = list[len(list)-1] 
      #visit the middle node only if the right node is none 
      #or the right node is already visited 
      if middle_node.right is None or visited_node == middle_node.right: 
       #visit the middle node 
       result.append(middle_node.data) 
       visited_node = list.pop(len(list)-1) 
      else: 
       #else, move to right 
       cur_node = middle_node.right 
    return result