轉(zhuǎn)載：https://www.cnblogs.com/ybf-yyj/p/8717601.html

見(jiàn)二叉樹(shù)先想遞歸。

            
              -*- coding:utf-8 -*-
class Node:
   def __init__(self,data):
       self.data=data
       self.lchild=None
       self.rchild=None
    
class Tree:
    def __init__(self):
        self.queue=[]#利用隊(duì)列存儲(chǔ)樹(shù)的節(jié)點(diǎn)
        self.flag=0#存儲(chǔ)樹(shù)根后flag置為1
        self.root=None
#建樹(shù)
def createTree(self,list):
    while True:
        #list中沒(méi)有數(shù)據(jù)，表示建樹(shù)完成
        if len(list)==0:
            return
        #flag為0，表示樹(shù)根不存在
        if self.flag==0:
            self.root=Node(list[0])
            #講樹(shù)根存入隊(duì)列
            self.queue.append(self.root)
            #樹(shù)根已創(chuàng)建，flag置為1
            self.flag=1
            #剔除list中第一個(gè)已經(jīng)使用數(shù)
            list.pop(0)
        else:
            '''
            treeNode:隊(duì)列中的第一個(gè)節(jié)點(diǎn)(該節(jié)點(diǎn)左右孩子不完全存在)
            添加treeNode的左右孩子，當(dāng)添加treeNode的右孩子之后，
            將隊(duì)列中的第一個(gè)節(jié)點(diǎn)出隊(duì)。
            '''
            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)


# 遞歸實(shí)現(xiàn)先序遍歷
def front_digui(self,root):
    if root==None:
        return
    else:
        print root.data,
        self.front_digui(root.lchild)
        self.front_digui(root.rchild)
# 遞歸實(shí)現(xiàn)中序遍歷
def middle_digui(self,root):
    if root==None:
        return
    else:
        self.middle_digui(root.lchild)
        print root.data,
        self.middle_digui(root.rchild)
# 遞歸實(shí)現(xiàn)后序遍歷
def behind_digui(self,root):
    if root==None:
        return
    else:
        self.behind_digui(root.lchild)
        self.behind_digui(root.rchild)
        print root.data,

# 隊(duì)棧實(shí)現(xiàn)先序遍歷
def front_queueAndStack(self,root):
    if root==None:
        return
    #定義一個(gè)棧,存儲(chǔ)節(jié)點(diǎn)
    stack=[]
    node=root
    while stack or node:
        #從樹(shù)根開(kāi)始一直輸出左孩子
        while node:
            print node.data,
            #將輸出的節(jié)點(diǎn)加入棧中
            stack.append(node)
            node=node.lchild
        #該節(jié)點(diǎn)不存在左節(jié)點(diǎn)時(shí),該節(jié)點(diǎn)出棧,搜索該節(jié)點(diǎn)右節(jié)點(diǎn)，
        node=stack.pop()
        node=node.rchild
# 隊(duì)棧實(shí)現(xiàn)中序遍歷
def middle_queueAndStack(self,root):
    if root==None:
        return
    # 定義一個(gè)棧,存儲(chǔ)節(jié)點(diǎn)
    stack = []
    node = root
    while stack or node:
        #一直查找樹(shù)的左節(jié)點(diǎn),一直進(jìn)棧
        while node:
            stack.append(node)
            node=node.lchild
        node=stack.pop()#該節(jié)點(diǎn)不存在左節(jié)點(diǎn)，該節(jié)點(diǎn)出棧，查找右節(jié)點(diǎn)
        print node.data,
        node=node.rchild
# 隊(duì)棧實(shí)現(xiàn)后序遍歷
def behind_queueAndStack(self,root):
    if root==None:
        return
    # 定義一個(gè)棧,存儲(chǔ)節(jié)點(diǎn)
    stack_1 = []
    stack_2 = []
    node = root
    stack_1.append(node)
    while stack_1:
        #該節(jié)點(diǎn)出棧1.左右節(jié)點(diǎn)進(jìn)棧1(對(duì)于左右節(jié)點(diǎn),右節(jié)點(diǎn)先出棧1,也先進(jìn)棧1)
        node=stack_1.pop()
        if node.lchild:
            stack_1.append(node.lchild)
        if node.rchild:
            stack_1.append(node.rchild)
        #該節(jié)點(diǎn)進(jìn)棧2
        stack_2.append(node)
    while stack_2:
        print stack_2.pop().data,
# 隊(duì)棧實(shí)現(xiàn)層次遍歷
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 '\n'
    tree.middle_digui(tree.root)
    print '\n'
    tree.behind_digui(tree.root)
    print '\n'
    tree.front_queueAndStack(tree.root)
    print '\n'
    tree.middle_queueAndStack(tree.root)
    print '\n'
    tree.behind_queueAndStack(tree.root)
    print '\n'
    tree.level_queueAndStack(tree.root)