#coding=utf-8

class Node(object):
    """節(jié)點類"""
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree(object):
    """樹類"""
    def __init__(self):
        self.root = Node()
        self.myQueue = []

    def add(self, elem):
        """為樹添加節(jié)點"""
        node = Node(elem=elem)
        if self.root.elem == -1:  # 如果樹是空的愿阐，則對根節(jié)點賦值
            self.root = node
            self.myQueue.append(self.root)
        else:
            treeNode = self.myQueue[0]  # 此結(jié)點的子樹還沒有齊竞穷。
            if treeNode.lchild == None:
                treeNode.lchild = node
                self.myQueue.append(treeNode.lchild)
            else:
                treeNode.rchild = node
                self.myQueue.append(treeNode.rchild)
                self.myQueue.pop(0)  # 如果該結(jié)點存在右子樹，將此結(jié)點丟棄。


    def front_digui(self, root):
        """
        利用遞歸實現(xiàn)樹的先序遍歷
        先序遍歷：根節(jié)點->左子樹->右子樹
        """
        if root == None:
            return
        print root.elem,
        self.front_digui(root.lchild)
        self.front_digui(root.rchild)


    def middle_digui(self, root):
        """
        利用遞歸實現(xiàn)樹的中序遍歷
        中序遍歷：左子樹->根節(jié)點->右子樹
        """
        if root == None:
            return
        self.middle_digui(root.lchild)
        print root.elem,
        self.middle_digui(root.rchild)


    def later_digui(self, root):
        """
         利用遞歸實現(xiàn)樹的后序遍歷
         后序遍歷：左子樹->右子樹->根節(jié)點
        """
        if root == None:
            return
        self.later_digui(root.lchild)
        self.later_digui(root.rchild)
        print root.elem,


    def front_stack(self, root):
        """利用堆棧實現(xiàn)樹的先序遍歷"""
        if root == None:
            return
        myStack = []
        node = root
        while node or myStack:
            while node:                     #從根節(jié)點開始，一直找它的左子樹
                print node.elem,
                myStack.append(node)
                node = node.lchild
            node = myStack.pop()            #while結(jié)束表示當前節(jié)點node為空，即前一個節(jié)點沒有左子樹了
            node = node.rchild                  #開始查看它的右子樹


    def middle_stack(self, root):
        """利用堆棧實現(xiàn)樹的中序遍歷"""
        if root == None:
            return
        myStack = []
        node = root
        while node or myStack:
            while node:                     #從根節(jié)點開始，一直找它的左子樹
                myStack.append(node)
                node = node.lchild
            node = myStack.pop()            #while結(jié)束表示當前節(jié)點node為空沟优，即前一個節(jié)點沒有左子樹了
            print node.elem,
            node = node.rchild                  #開始查看它的右子樹


    def later_stack(self, root):
        """利用堆棧實現(xiàn)樹的后序遍歷"""
        if root == None:
            return
        myStack1 = []
        myStack2 = []
        node = root
        myStack1.append(node)
        while myStack1:                   #這個while循環(huán)的功能是找出后序遍歷的逆序，存在myStack2里面
            node = myStack1.pop()
            if node.lchild:
                myStack1.append(node.lchild)
            if node.rchild:
                myStack1.append(node.rchild)
            myStack2.append(node)
        while myStack2:                         #將myStack2中的元素出棧睬辐，即為后序遍歷次序
            print myStack2.pop().elem,


    def level_queue(self, root):
        """利用隊列實現(xiàn)樹的層次遍歷"""
        if root == None:
            return
        myQueue = []
        node = root
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0)
            print node.elem,
            if node.lchild != None:
                myQueue.append(node.lchild)
            if node.rchild != None:
                myQueue.append(node.rchild)


if __name__ == '__main__':
    """主函數(shù)"""
    elems = range(10)           #生成十個數(shù)據(jù)作為樹節(jié)點
    tree = Tree()          #新建一個樹對象
    for elem in elems:                  
        tree.add(elem)           #逐個添加樹的節(jié)點

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

    print '\n\n遞歸實現(xiàn)先序遍歷:'
    tree.front_digui(tree.root)
    print '\n遞歸實現(xiàn)中序遍歷:' 
    tree.middle_digui(tree.root)
    print '\n遞歸實現(xiàn)后序遍歷:'
    tree.later_digui(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.later_stack(tree.root)