欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的深度优先遍历以及广度优先遍历实现

程序员文章站 2022-05-21 19:28:59
...

深度遍历分为先序遍历,中序遍历,以及后序遍历;而深度遍历的方式又分为递归深度遍历和栈深度遍历。
广度优先遍历是层序遍历:

#!/usr/bin/env python
#coding:utf-8

class TreeNode(object):
    def __init__(self):
        self.data = '#'
        self.lchild = None
        self.rchild = None

class Tree(TreeNode):
    def __init__(self):
        self.root = TreeNode()
        self.myQueue = []

    #Create a tree
    def create_tree(self,tree):
        data = raw_input('->')
        if data == '#':
            tree = None
        else:
            tree.data = data
            tree.lchild = TreeNode()
            self.create_tree(tree.lchild)
            tree.rchild = TreeNode()
            self.create_tree(tree.rchild)

    def visit(self,tree):
        #输入#代表空树
        if tree.data is not '#':
            print str(tree.data)+'\t'

    def pre_order(self,tree):
        if tree is not None:
            self.visit(tree)
            self.pre_order(tree.lchild)
            self.pre_order(tree.rchild)

    def in_order(self,tree):
        if tree is not None:
            self.in_order(tree.lchild)
            self.visit(tree)
            self.in_order(tree.rchild)

    def post_order(self,tree):
        if tree is not None:
            self.post_order(tree.lchild)
            self.post_order(tree.rchild)
            self.visit(tree)

    def pre_stack(self,tree):
        if tree == None:
            return
        myStack = []
        none = tree
        while node or myStack:
            while node:
                print node.data
                myStack.append(node)
                node = node.lchild
            node = myStack.pop()
            node = node.rchild

    def in_stack(self,tree):
        if tree == None:
            return
        myStack = []
        node = tree
        while node or myStack:
            myStack.append(node)
            node=node.lchild
        node=myStack.pop()
        print node.data
        node=node.rchild

    def post_stack(self,tree):
        if tree == None:
            return
        myStack1 = []
        myStack2 = []
        node=tree
        myStack1.append(node)
        while myStack1:
            node = myStack1.pop()
            if node.lchild:
                myStack1.append(node.lchild)
            if node.rchild:
                myStack1.append(node.rchild)
            myStack2.append(node)
        while myStack2:
            print myStack2.pop().data

    def level_order(self,tree):
        if tree == None:
            return
        myQueue = []
        node = tree
        myQueue.append(node)
        while myQueue:
            node=myQueue.pop(0)
            print node.data
            if node.lchild:
                myQueue.append(node.lchild)
            if node.rchild:
                myQueue.append(node.rchild)