# -*- coding: gb2312 -*- 
 
class Queue(object): 
 
  def __init__(self): 
    self.q = [] 
 
  def enqueue(self, item): 
    self.q.append(item) 
 
  def dequeue(self): 
    # if self.q != []: 
    if len(self.q)>0: 
       return self.q.pop(0)        
    else: 
      return None 
 
  def length(self): 
    return len(self.q) 
 
  def isempty(self): 
    return len(self.q)==0 
 
class Stack(object): 
  def __init__(self): 
    self.s = [] 
 
  def push(self, item): 
    self.s.append(item) 
 
  def pop(self): 
    if self.s !=[]: 
      item = self.s.pop(-1) 
    else: 
      item = None 
    return item 
 
  def length(self): 
    return len(self.s) 
 
  def isempty(self): 
    return self.s == [] 
 
  def top(self): 
    return self.s[-1] 
 
class TreeNode(object): 
 
  def __init__(self, data, left=None, right=None): 
    self.data = data 
    self.left = left 
    self.right = right 
    self.visited = False 
 
  def setData(self, data): 
    self.data = data 
 
  def setLeft(self, left): 
    self.left = left 
 
  def setRight(self, right): 
    self.right = right 
 
  def visit(self): 
    print self.data, 
    self.visited = True 
 
  def deVisit(self): 
    self.visited = False 
 
class BinaryTree(object): 
  def __init__(self, root): 
    self.root = root 
 
  # 前序遍歷(遞歸) 
  def freshVisit(self, node): 
    if node is not None: 
      node.deVisit() 
    if node.left: 
      self.freshVisit(node.left) 
    if node.right: 
      self.freshVisit(node.right) 
 
  # 前序遍歷(遞歸) 
  def preOrder(self, node): 
    if node is not None: 
      node.visit() 
    if node.left: 
      self.preOrder(node.left) 
    if node.right: 
      self.preOrder(node.right) 
 
  # 中序遍歷(遞歸) 
  def inOrder(self, node): 
    if node.left: 
      self.inOrder(node.left)       
    if node is not None: 
      node.visit()     
    if node.right: 
      self.inOrder(node.right) 
 
  # 后序遍歷(遞歸) 
  def postOrder(self, node): 
    if node.left: 
      self.postOrder(node.left)  
    if node.right: 
      self.postOrder(node.right) 
    if node is not None: 
      node.visit()   
 
  # 遞歸遍歷 
  def orderTraveral(self, type): 
    if type == 0: 
      self.preOrder(self.root) 
    elif type == 1:  
      self.inOrder(self.root) 
    elif type == 2: 
      self.postOrder(self.root) 
 
  # 前序遍歷(非遞歸) 
  # 用到一個(gè)棧和一個(gè)隊(duì)列 
  # 首先是根節(jié)點(diǎn)入棧，再循環(huán)出棧 
  # 出棧元素不為空，則訪問 
  # 出棧元素有左孩子節(jié)點(diǎn)則入棧，如果有右孩子節(jié)點(diǎn)則入隊(duì)列 
  # 出棧元素為空，則訪問隊(duì)列 
  # 隊(duì)列也為空則結(jié)束循環(huán),否則隊(duì)列元素出隊(duì) 
  # 訪問出隊(duì)元素，出隊(duì)元素有左孩子節(jié)點(diǎn)則入棧，出隊(duì)元素有右孩子節(jié)點(diǎn)則入隊(duì)列 
  # 循環(huán)直到最后退出 
  def preOrderByNotRecursion(self): 
    s = Stack() 
    q = Queue() 
    q.enqueue(self.root) 
 
    while not s.isempty() or not q.isempty(): 
 
      if not q.isempty(): 
        item = q.dequeue() 
        item.visit() 
        if item.left: 
          q.enqueue(item.left)           
        if item.right: 
          s.push(item.right) 
      elif not s.isempty(): 
        item = s.pop() 
        item.visit() 
        if item.left: 
          q.enqueue(item.left) 
        if item.right: 
          s.push(item.right) 
 
  # 前序遍歷(非遞歸) 
  # 用到一個(gè)棧 
  # 首先是根節(jié)點(diǎn)入棧，再循環(huán)出棧 
  # 棧頂元素不為空，則訪問, 并置已訪問標(biāo)志 
  # 如棧頂元素有左孩子節(jié)點(diǎn)則入棧 
  # 若棧頂元素已訪問，則出棧 
  # 出棧元素若有右孩子節(jié)點(diǎn)則入棧 
  # 循環(huán)直到棧無元素退出         
  def preOrderByNotRecursion2(self): 
    s = Stack() 
    s.push(self.root) 
 
    while not s.isempty(): 
      item = s.top()       
      if item.visited: 
        s.pop() 
        if item.right: 
          s.push(item.right) 
      else: 
        item.visit() 
        if item.left: 
          s.push(item.left) 
 
 
  # 中序遍歷(非遞歸) 
  # 用到一個(gè)棧 
  # 先將根節(jié)點(diǎn)入棧，循環(huán)出棧 
  # 如果出棧元素有左孩子節(jié)點(diǎn)并且左孩子節(jié)點(diǎn)沒有訪問過則入棧 
  # 反之，則出棧并且訪問；如果出棧元素有右孩子節(jié)點(diǎn)則入棧 
  # 重復(fù)以上循環(huán)直到棧為空 
  def inOrderByNotRecursion(self): 
    s = Stack() 
    s.push(self.root) 
 
    while not s.isempty(): 
      item = s.top() 
      while(item.left and not item.left.visited): 
        s.push(item.left) 
        item = item.left 
      else: 
        item = s.pop() 
        item.visit() 
        if item.right: 
          s.push(item.right) 
 
 
  # 后序遍歷(非遞歸) 
  # 用到一個(gè)棧 
  # 先將根節(jié)點(diǎn)入棧，循環(huán)出棧 
  # 如果出棧元素有左孩子節(jié)點(diǎn)并且左孩子節(jié)點(diǎn)沒有訪問過則入棧 
  # 反之，如果棧頂元素如果有右孩子節(jié)點(diǎn)并且右孩子節(jié)點(diǎn)沒有訪問過，則入棧 
  # 否則，出棧并訪問 
  # 重復(fù)以上循環(huán)直到棧為空 
  def postOrderByNotRecursion(self): 
    s = Stack() 
    s.push(self.root) 
 
    while not s.isempty(): 
      item = s.top() 
      while(item.left and not item.left.visited): 
        s.push(item.left) 
        item = item.left 
      else: 
        if item.right and not item.right.visited: 
          s.push(item.right) 
        else: 
          item = s.pop() 
          item.visit() 
 
 
  # 層次遍歷(非遞歸) 
  # 用到一個(gè)隊(duì)列 
  # 先將根節(jié)點(diǎn)入隊(duì)列 
  # 從隊(duì)列取出一個(gè)元素，訪問 
  # 如有左孩子節(jié)點(diǎn)則入隊(duì)，如有右孩子節(jié)點(diǎn)則入隊(duì) 
  # 重復(fù)以上操作直到隊(duì)列入空 
  def layerOrder(self): 
    q = Queue() 
    q.enqueue(self.root) 
 
    while not q.isempty(): 
      item = q.dequeue() 
      item.visit() 
      if item.left: 
        q.enqueue(item.left) 
      if item.right: 
        q.enqueue(item.right) 
 
#      A 
#    B      C 
#  D    E  F    G 
#H 
if __name__ == '__main__': 
 
  nE = TreeNode('E'); 
  nF = TreeNode('F'); 
  nG = TreeNode('G'); 
  nH = TreeNode('H'); 
  nD = TreeNode('D', nH); 
  nB = TreeNode('B', nD, nE); 
  nC = TreeNode('C', nF, nG); 
  nA = TreeNode('A', nB, nC); 
  bTree = BinaryTree(nA); 
 
  # 前序遞歸遍歷 
  print '----------前序遍歷(遞歸)-----------' 
  bTree.orderTraveral(0) 
  print '\n----------中序遍歷(遞歸)-----------' 
  bTree.orderTraveral(1) 
  print '\n----------后序遍歷(遞歸)-----------' 
  bTree.orderTraveral(2) 
 
  print '\n\n----------前序遍歷(非遞歸)-----------' 
  print '----------方法一-----------' 
  bTree.freshVisit(bTree.root) 
  bTree.preOrderByNotRecursion() 
  print '\n----------方法二-----------' 
  bTree.freshVisit(bTree.root)   
  bTree.preOrderByNotRecursion2() 
  print '\n\n----------中序遍歷(非遞歸)-----------' 
  bTree.freshVisit(bTree.root) 
  bTree.inOrderByNotRecursion() 
  print '\n\n----------后序遍歷(非遞歸)-----------' 
  bTree.freshVisit(bTree.root) 
  bTree.postOrderByNotRecursion() 
 
  print '\n\n----------層次遍歷(非遞歸)-----------' 
  bTree.freshVisit(bTree.root) 
  bTree.layerOrder()