'# -*- coding: utf-8 -*-'
'# 節(jié)點(diǎn)類' 
class Node(object):
    def __init__(self, data=None, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild
'# 二叉樹類'
class Bitree(object):
    def __init__(self):
        self.root = Node()
        self.myqueue = []

    # 添加節(jié)點(diǎn)（利用隊列來實(shí)現(xiàn)，判斷節(jié)點(diǎn)的左右子樹是否有值，沒值賦值后并將左右節(jié)點(diǎn)添加到隊列中，若右節(jié)點(diǎn)，將該節(jié)點(diǎn)從隊列中移除
    def addnode(self, value):
        node = Node(value)
        if self.root.data is None:   # 如果樹是空的，則對根節(jié)點(diǎn)賦值
            self.root = node
            self.myqueue.append(self.root)
        else:
            treenode = self.myqueue[0]   # 此節(jié)點(diǎn)的子樹還不完全
            if treenode.lchild is None:
                treenode.lchild = node
                self.myqueue.append(treenode.lchild)
            else:
                treenode.rchild = node
                self.myqueue.append(treenode.rchild)
                self.myqueue.pop(0)        # 經(jīng)歷過給右節(jié)點(diǎn)賦值，該節(jié)點(diǎn)一定是完全的，故從列表中pop出（隊列，先進(jìn)先出）

    # 利用遞歸實(shí)現(xiàn)先序遍歷二叉樹
    def preorder_re(self, root):
        if root is None:
            return
        else:
            # 遍歷順序為“根左右”
            print(root.data, end=' ')
            self.preorder_re(root.lchild)
            self.preorder_re(root.rchild)

    # 利用遞歸實(shí)現(xiàn)中序遍歷二叉樹
    def inorder_re(self, root):
        if root is None:
            return
        else:
            # 遍歷順序為“左根右”
            self.inorder_re(root.lchild)
            print(root.data, end=' ')
            self.inorder_re(root.rchild)

    # 利用遞歸實(shí)現(xiàn)后序遍歷二叉樹
    def backorder_re(self, root):
        if root is None:
            return
        else:
            # 遍歷順序為“左右根”
            self.backorder_re(root.lchild)
            self.backorder_re(root.rchild)
            print(root.data, end=' ')

    # 利用堆棧實(shí)現(xiàn)先序遍歷二叉樹，棧的特點(diǎn)先進(jìn)后出
    def preorder_stack(self, root):
        if root is None:
            return
        node = root
        mystack = []
        while node or mystack:             # 當(dāng)?？?，則代表所有節(jié)點(diǎn)都已遍歷完
            while node:
                print(node.data, end=' ')
                mystack.append(node)   # 將節(jié)點(diǎn)添加到棧中
                node = node.lchild    # 將節(jié)點(diǎn)的左節(jié)點(diǎn)當(dāng)作父節(jié)點(diǎn)，繼續(xù)循環(huán)，找出所有左節(jié)點(diǎn)，并添加到棧中，while循環(huán)結(jié)束表示當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)沒有左子樹
            node = mystack.pop()     # 將沒有左節(jié)點(diǎn)的pop出
            node = node.rchild       # 左子樹遍歷完，開始遍歷右子樹

    # 利用堆棧實(shí)現(xiàn)中序遍歷二叉樹
    def inorder_stack(self, root):
        if root is None:
            return
        node = root
        mystack = []
        while node or mystack:
            while node:
                mystack.append(node)
                node = node.lchild    # 這個while循環(huán)是為了找左子樹為空的節(jié)點(diǎn)
            node = mystack.pop()     # 左
            print(node.data, end=' ')  # 根
            node = node.rchild         # 右

    # 利用堆棧實(shí)現(xiàn)后序二叉樹遍歷
    def backorder_stack(self, root):
        if root is None:
            return
        node = root
        mystack1 = []
        mystack2 = []
        mystack1.append(node)
        while mystack1:                        # 找出后序遍歷的逆序，并存入mystack2中
            node = mystack1.pop()
            if node.lchild is not None:
                mystack1.append(node.lchild)
            if node.rchild is not None:
                mystack1.append(node.rchild)
            mystack2.append(node)
        while mystack2:
            print(mystack2.pop().data, end=' ')     # 逆序輸出

    # 利用隊列實(shí)現(xiàn)二叉樹的層次遍歷
    def level_queue(self, root):
        if root is None:
            return
        myqueue = []
        node = root
        myqueue.append(node)
        while myqueue:
            node = myqueue.pop(0)  # 先進(jìn)先出
            print(node.data, end=' ')
            if node.lchild is not None:
                myqueue.append(node.lchild)
            if node.rchild is not None:
                myqueue.append(node.rchild)
s
if __name__ == '__main__':
   
    elems = range(10)  # 生成十個數(shù)據(jù)作為樹節(jié)點(diǎn)
    tree = Bitree()  # 新建一個樹對象
    for elem in elems:
        tree.addnode(elem)  # 逐個添加樹的節(jié)點(diǎn)
    print('隊列實(shí)現(xiàn)層次遍歷:')
    tree.level_queue(tree.root)
    print('\n\n遞歸實(shí)現(xiàn)先序遍歷:')
    tree.preorder_re(tree.root)
    print('\n遞歸實(shí)現(xiàn)中序遍歷:')
    tree.inorder_re(tree.root)
    print('\n遞歸實(shí)現(xiàn)后序遍歷:')
    tree.backorder_re(tree.root)
    print('\n\n堆棧實(shí)現(xiàn)先序遍歷:')
    tree.preorder_stack(tree.root)
    print('\n堆棧實(shí)現(xiàn)中序遍歷:')
    tree.inorder_stack(tree.root)
    print('\n堆棧實(shí)現(xiàn)后序遍歷:')
    tree.backorder_stack(tree.root)
'''