# -*- coding=utf-8 -*-


class Node(object):
 """節(jié)點類"""

 def __init__(self, element=-1, l_child=None, r_child=None):
  self.element = element
  self.l_child = l_child
  self.r_child = r_child


class Tree(object):
 """樹類"""

 def __init__(self):
  self.root = Node()
  self.queue = []

 def add_node(self, element):
  """為樹添加節(jié)點"""

  node = Node(element)
  # 如果樹是空的，則對根節(jié)點賦值
  if self.root.element == -1:
   self.root = node
   self.queue.append(self.root)
  else:
   tree_node = self.queue[0]
   # 此結點沒有左子樹，則創(chuàng)建左子樹節(jié)點
   if tree_node.l_child is None:
    tree_node.l_child = node
    self.queue.append(tree_node.l_child)
   else:
    tree_node.r_child = node
    self.queue.append(tree_node.r_child)
    # 如果該結點存在右子樹，將此節(jié)點丟棄
    self.queue.pop(0)

 def front_recursion(self, root):
  """利用遞歸實現(xiàn)樹的前序遍歷"""

  if root is None:
   return

  print root.element,
  self.front_recursion(root.l_child)
  self.front_recursion(root.r_child)

 def middle_recursion(self, root):
  """利用遞歸實現(xiàn)樹的中序遍歷"""

  if root is None:
   return

  self.middle_recursion(root.l_child)
  print root.element,
  self.middle_recursion(root.r_child)

 def back_recursion(self, root):
  """利用遞歸實現(xiàn)樹的后序遍歷"""

  if root is None:
   return

  self.back_recursion(root.l_child)
  self.back_recursion(root.r_child)
  print root.element,

 @staticmethod
 def front_stack(root):
  """利用堆棧實現(xiàn)樹的前序遍歷"""

  if root is None:
   return

  stack = []
  node = root
  while node or stack:
   # 從根節(jié)點開始，一直找它的左子樹
   while node:
    print node.element,
    stack.append(node)
    node = node.l_child
   # while結束表示當前節(jié)點node為空，即前一個節(jié)點沒有左子樹了
   node = stack.pop()
   # 開始查看它的右子樹
   node = node.r_child

 @staticmethod
 def middle_stack(root):
  """利用堆棧實現(xiàn)樹的中序遍歷"""

  if root is None:
   return

  stack = []
  node = root
  while node or stack:
   # 從根節(jié)點開始，一直找它的左子樹
   while node:
    stack.append(node)
    node = node.l_child
   # while結束表示當前節(jié)點node為空，即前一個節(jié)點沒有左子樹了
   node = stack.pop()
   print node.element,
   # 開始查看它的右子樹
   node = node.r_child

 @staticmethod
 def back_stack(root):
  """利用堆棧實現(xiàn)樹的后序遍歷"""

  if root is None:
   return

  stack1 = []
  stack2 = []
  node = root
  stack1.append(node)
  # 這個while循環(huán)的功能是找出后序遍歷的逆序，存在stack2里面
  while stack1:
   node = stack1.pop()
   if node.l_child:
    stack1.append(node.l_child)
   if node.r_child:
    stack1.append(node.r_child)
   stack2.append(node)
  # 將stack2中的元素出棧，即為后序遍歷次序
  while stack2:
   print stack2.pop().element,

 @staticmethod
 def level_queue(root):
  """利用隊列實現(xiàn)樹的層次遍歷"""

  if root is None:
   return

  queue = []
  node = root
  queue.append(node)
  while queue:
   node = queue.pop(0)
   print node.element,
   if node.l_child is not None:
    queue.append(node.l_child)
   if node.r_child is not None:
    queue.append(node.r_child)


if __name__ == '__main__':
 """主函數(shù)"""

 # 生成十個數(shù)據(jù)作為樹節(jié)點
 elements = range(10)
 tree = Tree()
 for elem in elements:
  tree.add_node(elem)

 print '隊列實現(xiàn)層次遍歷:'
 tree.level_queue(tree.root)

 print '\n\n遞歸實現(xiàn)前序遍歷:'
 tree.front_recursion(tree.root)
 print '\n遞歸實現(xiàn)中序遍歷:'
 tree.middle_recursion(tree.root)
 print '\n遞歸實現(xiàn)后序遍歷:'
 tree.back_recursion(tree.root)

 print '\n\n堆棧實現(xiàn)前序遍歷:'
 tree.front_stack(tree.root)
 print '\n堆棧實現(xiàn)中序遍歷:'
 tree.middle_stack(tree.root)
 print '\n堆棧實現(xiàn)后序遍歷:'
 tree.back_stack(tree.root)