'''
非完全二叉树的构建和四种遍历
'''

class Node(object):
    '''
    定义节点
    '''
    def __init__(self,data=None,lchild=None,rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild
        
class BitTree(object):
    '''
    定义非完全二叉树
    '''
    
    def __init__(self,node=None):
        self.root = node
        
    def addNode(self,node=None):
        if not (self.root and self.root.data):
            self.root = node
        my_queque=[self.root]
        while my_queque:
            cur_node = my_queque.pop(0)
            if cur_node == None:
                continue
            elif not cur_node.lchild :
                cur_node.lchild = node
                return 
            elif not cur_node.rchild :
                cur_node.rchild = node
                return
            else:
                my_queque.append(cur_node.lchild)
                my_queque.append(cur_node.rchild)
                
    #先跟遍历（递归）
    def preOrder(self,root):
        if root == None:
            return
        print (root.data)
        self.preOrder(root.lchild)
        self.preOrder(root.rchild)
    #先根遍历（非递归）
    def preOrder(self,root):
        if not root:
            return
        stack = [root]
        ans = []
        while stack:
            cur = stack.pop()
            ans.append(cur.val)
            #注意先添加右孩子，再添加左节点
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return ans
        
    #中跟遍历（递归）
    def inOrder(self,root):
        if root == None:
            return
        self.inOrder(root.lchild)
        print (root.data)
        self.inOrder(root.rchild)

    #中跟遍历（非递归）
     def inOrder(self,root):
      '''
        中根遍历时，用指针cur去遍历当前节点的左孩子，如果存在，则将其入栈，继续遍历；
        如果不存在，则cur指向栈顶节点，，访问栈顶节点的值，然后遍历当前节点的右孩子
      '''
        if not root:
            return
        stack = []
        ans = []
        cur = root
        while cur or stack:
            if cur :
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                ans.append(cur.val)
                cur = cur.right
        return ans
        
    #后跟遍历（递归）
    def postOrder(self,root):
        if root == None:
            return
        self.postOrder(root.lchild)
        self.postOrder(root.rchild)
        print (root.data)

    #后跟遍历（非递归）
    def postOrder(self,root):
        if not root:
            return 
        stack1=[root]
        stack2=[]
        ans=[]
        while stack1:
            cur=stack1.pop()
            if cur.left:
                stack1.append(cur.left)
            if cur.right:
                stack2.append(cur.right)
        
        while stack2:
            cur = stack2.pop()
            ans.append(cur.val)
        return ans

    #层次遍历
    def levelOrder(self,root):
        if root==None:
            return
        my_queque=[root]
        while my_queque:
            cur_node = my_queque.pop(0)
            print (cur_node.data)
            if cur_node.lchild:
                my_queque.append(cur_node.lchild) 
            if cur_node.rchild:
                my_queque.append(cur_node.rchild) 
        



        
a=Node("A")
b_tree = BitTree(a)
node_list=["B","E","C",None,"G","F"]
for n in node_list:
    nn = Node(n)
    b_tree.addNode(nn)
print("----先根--------：")
b_tree.preOrder(b_tree.root)
print("----中根--------：")
b_tree.inOrder(b_tree.root)
print("----后根--------：")
b_tree.postOrder(b_tree.root)
print("----层次--------：")
b_tree.levelOrder(b_tree.root)