__author__ = "WSX"

 class Node:

     def __init__(self, val = None, left = None, right = None):

         self.val = val

         self.left = left

         self.right = right

 class tree:

     def __init__(self, L):

         self.val = L

     def bulid(self,root, i):    #将列表转化建立二叉树

         if i < len(self.val):

             root = Node(val = self.val[i])

             root.left = self.bulid(root.left, 2*i+1)

             root.right = self.bulid(root.right, 2*i+2)

             return root

         return root

     def preTraverse(self, tree_):

         root = tree_

         if root:

             print(root.val)

             self.preTraverse(root.left)

             self.preTraverse(root.right)

     def midTraverse(self, tree_):

         root = tree_

         if root:

             self.preTraverse(root.left)

             print(root.val)

             self.preTraverse(root.right)

     def postTraverse(self, tree_):

         root = tree_

         if root:

             self.preTraverse(root.left)

             self.preTraverse(root.right)

             print(root.val)

     def cengci(self, tree_):

         root = tree_

         queue = [root]  #借助队列

         while root and len(queue)!= 0:

             print(queue[0].val)  #visit

             if queue[0].left:

                 queue.append(queue[0].left)

             if queue[0].right:

                 queue.append(queue[0].right)

             queue.pop(0)

 T = tree(['','','',"","",""])

 root = T.bulid(Node(), 0)

 print("preTraverse"); T.preTraverse(root)

 print("postTraverse");T.postTraverse(root)

 print("midTraverse");T.midTraverse(root)

 print("cengci");T.cengci(root)

 __author__ = "WSX"

 def pre(root):

     if not root:

         return None

     stack = [root]

     res = []

     while stack:

         res.append(root.val)

         if root.right:

             stack.append(root.right)

         if root.left:

             stack.append(root.left)

         root = stack.pop()

     return res

 def inOrderTraverse(node):

     stack = []

     pos = node

     while pos is not None or len(stack) > 0:

         if pos is not None:

             stack.append(pos)

             pos = pos.left

         else:

             pos = stack.pop()

             print(pos.val)

             pos = pos.right

 def postOrderTraverse(node):

     stack = [node]

     stack2 = []

     while len(stack) > 0:

         node = stack.pop()

         stack2.append(node)

         if node.left is not None:

             stack.append(node.left)

         if node.right is not None:

             stack.append(node.right)

     while len(stack2) > 0:

         print(stack2.pop().val)