二叉樹後序遍歷的迭代過程

-1

我做了二叉樹後序遍歷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中的二叉樹後序遍歷做一個迭代過程。有人能幫忙嗎？

在此先感謝。

來源

2014-07-08 Harish

通常我認爲人們使用訪問堆棧基本上取代母語調用堆棧做反覆迭代時。我個人使用節點中的訪問標誌進行迭代遍歷。所以兩者都可以工作。 –

下面的代碼應該可以工作。基本上，您可以使用堆棧爲節點執行深度優先搜索。此外，您還有第二個堆棧，它並行存儲節點是否已被擴展。

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]

來源

2014-07-08 08:17:45 jfschaefer

感謝此代碼。但是我需要一個只使用一個堆棧的過程。 – Harish

通過在一個堆棧上放置節點對和相應的True/False值，您可以將它成爲一個堆棧，而不是像我一樣將它們放在兩個堆棧上 – jfschaefer

-1

下面是代碼

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

來源

2014-11-10 12:54:38 Ida

二叉樹後序遍歷的迭代過程

回答

相關問題