Python 은 이 진 트 리 의 구축 과 옮 겨 다 니 기 를 실현 합 니 다.

class Node:
    def __init__(self,data):
        self.data=data
        self.lchild=None
        self.rchild=None

class Tree:
    def __init__(self):
        self.queue=[]#          
        self.flag=0#     flag  1
        self.root=None

    #  
    def createTree(self,list):
        while True:
            #list     ，      
            if len(list)==0:
                return
            #flag 0，       
            if self.flag==0:
                self.root=Node(list[0])
                #       
                self.queue.append(self.root)
                #     ，flag  1
                self.flag=1
                #  list         
                list.pop(0)
            else:
                '''
                treeNode:         (            )
                  treeNode     ，   treeNode      ，
                            。
                '''
                treeNode=self.queue[0]
                if treeNode.lchild==None:
                    treeNode.lchild=Node(list[0])
                    self.queue.append(treeNode.lchild)
                    list.pop(0)
                else:
                    treeNode.rchild = Node(list[0])
                    self.queue.append(treeNode.rchild)
                    list.pop(0)
                    self.queue.pop(0)

    #         
    def front_digui(self,root):
        if root==None:
            return
        else:
            print root.data,
            self.front_digui(root.lchild)
            self.front_digui(root.rchild)
    #         
    def middle_digui(self,root):
        if root==None:
            return
        else:
            self.middle_digui(root.lchild)
            print root.data,
            self.middle_digui(root.rchild)
    #         
    def behind_digui(self,root):
        if root==None:
            return
        else:
            self.behind_digui(root.lchild)
            self.behind_digui(root.rchild)
            print root.data,

    #         
    def front_queueAndStack(self,root):
        if root==None:
            return
        #     ,    
        stack=[]
        node=root
        while stack or node:
            #            
            while node:
                print node.data,
                #          
                stack.append(node)
                node=node.lchild
            #          ,     ,        ，
            node=stack.pop()
            node=node.rchild
    #         
    def middle_queueAndStack(self,root):
        if root==None:
            return
        #      ,    
        stack = []
        node = root
        while stack or node:
            #         ,    
            while node:
                stack.append(node)
                node=node.lchild
            node=stack.pop()#         ，     ，     
            print node.data,
            node=node.rchild
    #         
    def behind_queueAndStack(self,root):
        if root==None:
            return
        #      ,    
        stack_1 = []
        stack_2 = []
        node = root
        stack_1.append(node)
        while stack_1:
            #     1.      1(      ,      1,    1)
            node=stack_1.pop()
            if node.lchild:
                stack_1.append(node.lchild)
            if node.rchild:
                stack_1.append(node.rchild)
            #     2
            stack_2.append(node)
        while stack_2:
            print stack_2.pop().data,
    #         
    def level_queueAndStack(self,root):
        if root==None:
            return
        stack_1=[]
        stack_2=[]
        stack_1.append(root)
        stack_2.append(root)
        while stack_1:
            node=stack_1.pop(0)
            if node.lchild:
                stack_1.append(node.lchild)
                stack_2.append(node.lchild)
            if node.rchild:
                stack_1.append(node.rchild)
                stack_2.append(node.rchild)
        while stack_2:
            print stack_2.pop(0).data,

if __name__ == '__main__':
    list=[0,1,2,3,4,5,6,7,8,9,]
    tree=Tree()
    tree.createTree(list)
    tree.front_digui(tree.root)
    print '
'
    tree.middle_digui(tree.root)
    print '
'
    tree.behind_digui(tree.root)
    print '
'
    tree.front_queueAndStack(tree.root)
    print '
'
    tree.middle_queueAndStack(tree.root)
    print '
'
    tree.behind_queueAndStack(tree.root)
    print '
'
    tree.level_queueAndStack(tree.root)