python二叉树的遍历

觉得这个挺有趣的，记录一下

# -*- coding: utf-8 -*-
class TreeNode(object):
    def __init__(self,data=None,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
    
class BTree(object):
    def __init__(self,root=None):
        self.root = root
    
    def is_empty(self):
        if self.root is None:
            return True
        else:
            return False
    
    # 递归先序遍历
    def preOrder(self,treenode):
        if treenode is None:
            return
        print(treenode.data)
        self.preOrder(treenode.left)
        self.preOrder(treenode.right)
        
    # 非递归先序遍历
    def fOrder(self,treenode):
        stack = []
        p = treenode
        while p or len(stack) > 0:
            if p is not None:
                stack.append(p)
                print(p.data)
                p = p.left
            else:
                p = stack.pop()
                p = p.right
        
    # 递归中序遍历
    def inOrder(self,treenode):
        if treenode is None:
            return
        self.inOrder(treenode.left)
        print(treenode.data)
        self.inOrder(treenode.right)
    
    # 非递归中序遍历
    def mOrder(self,treenode):
        stack = []
        p = treenode
        while p or len(stack) > 0:
            if p is not None:
                stack.append(p)
                p = p.left
            else:
                p = stack.pop()
                print(p.data)
                p = p.right
        
    # 递归后序遍历
    def postOrder(self,treenode):
        if treenode is None:
            return
        self.postOrder(treenode.left)
        self.postOrder(treenode.right)
        print(treenode.data)
        
    # 非递归后序遍历
    def aOrder(self,treenode):
        stack = []
        result = []
        stack.append(treenode)
        #p = treenode
        while len(stack) > 0:
            node = stack.pop()
            result.insert(0,node)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        [print(i.data) for i in result]
        
    # 层次遍历
    def leavelOrder(self,treenode):
        p = treenode
        queue = []
        queue.append(p)
        while len(queue) > 0:
            p = queue[0]
            print(p.data)
            queue.remove(queue[0])
            if p.left is not None:
                queue.append(p.left)
            if p.right is not None:
                queue.append(p.right)


# 递归最大深度1976
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n*factorial(n-1)

if __name__ == '__main__':
    n3 = TreeNode(3)
    n8 = TreeNode(8)
    n9 = TreeNode(9)
    n10 = TreeNode(10)
    n11 = TreeNode(11)
    n6 = TreeNode(6,n8)
    n7 = TreeNode(7,None,n9)
    n4 = TreeNode(4,n6,n7)
    n1 = TreeNode(1,n3,n4)
    n5 = TreeNode(5,n10,n11)
    n2 = TreeNode(2,None,n5)
    root = TreeNode('root',n1,n2)
    bt = BTree(root)
    print('递归--先序-遍历......')
    bt.preOrder(bt.root)
    print('非递归--先序-遍历......')
    bt.fOrder(bt.root)
    print('递归--中序-遍历......')
    bt.inOrder(bt.root)
    print('非递归--中序-遍历......')
    bt.mOrder(bt.root)
    print('递归--后序-遍历......')
    bt.postOrder(bt.root)
    print('非递归--后序-遍历......')
    bt.aOrder(bt.root)
    print('层次遍历......')

    bt.leavelOrder(bt.root)

运行结果与算出来的一致