이 진 트 리 의 앞 순서, 중간 순서, 뒤 순서 와 층 차 를 옮 겨 다 니 는 비 재 귀적 실현

class Node(object):
    def __init__(self, data=-1, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild
    
class Tree(object):
    def __init__(self):
        self.root = Node()
        self.treeQueue = []
        
    def add(self, data): #           
        node = Node(data) 
        if self.root.data == -1:  #    
            self.root = node
            self.treeQueue.append(self.root)
        else:               #     ，        
            treeNode = self.treeQueue[0]   #            
            if treeNode.lchild == None:   #      
                treeNode.lchild = node
                self.treeQueue.append(node)
            elif treeNode.rchild == None: #      
                treeNode.rchild = node
                self.treeQueue.append(node)
                self.treeQueue.pop(0)     #             
                
    def pre_order_recursion(self, root):  #     
        if not root:
            return 
        print(str(root.data) + " ", end='')
        self.pre_order_recursion(root.lchild)
        self.pre_order_recursion(root.rchild)
        
    def pre_order_stack(self, root):     #   ：     
        if not root:
            return 
        stack = [] # pop()               （        ）
        node = root  #       
        while node or stack: #         ，   stack     
            while node:   #              
                print(str(node.data) + " ", end='')
                stack.append(node) #  
                node = node.lchild
            node = stack.pop()  #           ，          ，      
            node = node.rchild
            
    def in_order_stack(self, root):       
        if not root:
            return
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.lchild
            #        ，         
            node = stack.pop()
            print(str(node.data) + " ", end='') #             
            node = node.rchild
            
    def post_order_stack(self, root):  
        #        。    ： -> ->  ，     -> -> （    ）
        #       -> -> 
        if not root:
            return
        stack = []
        post_stack = []
        node = root
        while stack or node:
            while node:
                stack.append(node)
                post_stack.append(node)
                node = node.rchild
            node = stack.pop()
            node = node.lchild
        while post_stack:
            print(str(post_stack.pop().data) + " ", end='')
    #      ： O(n):          
    #      ： O(2N):   stack
    
    def level_order_queue(self, root): #     :     ，        
        if not root:
            return
        queue = []
        node = root
        queue.append(node)
        while queue:
            node = queue.pop(0)
            print(str(node.data) + " ", end='')
            if node.lchild:
                queue.append(node.lchild)
            if node.rchild:
                queue.append(node.rchild)
        

if __name__ == '__main__':
    """   """
    datas = [i for i in range(10)]        #     ，    
    tree = Tree()   
    for data in datas:                  
        tree.add(data)           #        
    print('        ：')
    tree.pre_order_recursion(tree.root)
    print("
")
    tree.pre_order_stack(tree.root)
    print('
         ：')
    tree.in_order_stack(tree.root)
    print('
         ：')
    tree.post_order_stack(tree.root)
    print('
        ：')
    tree.level_order_queue(tree.root)