pythonツリー遍歴

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon May 13 15:48:30 2019

@author: lg
"""

class Node():
    #   
    def __init__(self,data = -1):
        self.data = data
        self.left = None
        self.right = None
class Tree():
    #  
    def __init__(self):
        self.root = Node()
 
    def add(self,data):
        #       
        node  = Node(data)
        if self.root.data == -1:        #     ，       
            self.root = node
        else:
            myQueue = []
            treeNode = self.root
            myQueue.append(treeNode)
            while myQueue:              #            
                treeNode = myQueue.pop(0)
                if not treeNode.left:
                    treeNode.left = node
                    return
                elif not treeNode.right:
                    treeNode.right = node
                    return
                else:
                    myQueue.append(treeNode.left)
                    myQueue.append(treeNode.right)
 
    def pre_order_recursion(self,root):     #        
        if not root:
            return
        print( root.data,)
        self.pre_order_recursion(root.left)
        self.pre_order_recursion(root.right)
 
    def pre_order_stack(self,root):         #        （   ）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:
            while node:       #      ，         
                print (node.data,)
                myStack.append(node)
                node = node.left
            node = myStack.pop()    #while        node  ，            
            node = node.right       #         
 
    def in_order_recursion(self,root):      #        
        if not root:
            return
        self.in_order_recursion(root.left)
        print( root.data,)
        self.in_order_recursion(root.right)
 
    def in_order_stack(self,root):        #        （   ）
        if not root:
            return
        myStack = []
        node = root
        while myStack or node:     #      ，         
            while node:
                myStack.append(node)
                node = node.left
            node = myStack.pop()
            print(node.data,)
            node = node.right
 
 
    def post_order_recursion(self,root):     #        
        if not root:
            return
        self.post_order_recursion(root.left)
        self.post_order_recursion(root.right)
        print( root.data,)
        
    def post_order_stack(self, root):  #         （   ）
        #       ，      ，      ，                  ，             OK 。
        if not root:
            return
        myStack1 = []
        myStack2 = []
        node = root
        while myStack1 or node:
            while node:
                myStack2.append(node)
                myStack1.append(node)
                node = node.right
            node = myStack1.pop()
            node = node.left
        while myStack2:
            print( myStack2.pop().data,)
 
    def level_order_queue(self,root):       #        （   ）
        if not root :
            return
        myQueue = []
        node = root
        myQueue.append(node)
        while myQueue:
            node = myQueue.pop(0)
            print( node.data,)
            if node.left:
                myQueue.append(node.left)
            if node.right:
                myQueue.append(node.right)
                
if __name__ == '__main__':
    #   
    datas = [2,3,4,5,6,7,8,9]
    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_recursion(tree.root)
 
    print ("
        ：")
    tree.in_order_stack(tree.root)
 
    print ('

        ：')
    tree.post_order_recursion(tree.root)
 
    print('
        ：')
    tree.post_order_stack(tree.root)
 
    print('

        ：')
    tree.level_order_queue(tree.root)