'# -*- coding: utf-8 -*-'
'# 节点类' 
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 = []

    # 添加节点（利用队列来实现，判断节点的左右子树是否有值，没值赋值后并将左右节点添加到队列中，若右节点，将该节点从队列中移除
    def addnode(self, value):
        node = Node(value)
        if self.root.data is None:   # 如果树是空的，则对根节点赋值
            self.root = node
            self.myqueue.append(self.root)
        else:
            treenode = self.myqueue[0]   # 此节点的子树还不完全
            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)        # 经历过给右节点赋值，该节点一定是完全的，故从列表中pop出（队列，先进先出）

    # 利用递归实现先序遍历二叉树
    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)

    # 利用递归实现中序遍历二叉树
    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)

    # 利用递归实现后序遍历二叉树
    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=' ')

    # 利用堆栈实现先序遍历二叉树，栈的特点先进后出
    def preorder_stack(self, root):
        if root is None:
            return
        node = root
        mystack = []
        while node or mystack:             # 当栈空，则代表所有节点都已遍历完
            while node:
                print(node.data, end=' ')
                mystack.append(node)   # 将节点添加到栈中
                node = node.lchild    # 将节点的左节点当作父节点，继续循环，找出所有左节点，并添加到栈中，while循环结束表示当前节点的父节点没有左子树
            node = mystack.pop()     # 将没有左节点的pop出
            node = node.rchild       # 左子树遍历完，开始遍历右子树

    # 利用堆栈实现中序遍历二叉树
    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循环是为了找左子树为空的节点
            node = mystack.pop()     # 左
            print(node.data, end=' ')  # 根
            node = node.rchild         # 右

    # 利用堆栈实现后序二叉树遍历
    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=' ')     # 逆序输出

    # 利用队列实现二叉树的层次遍历
    def level_queue(self, root):
        if root is None:
            return
        myqueue = []
        node = root
        myqueue.append(node)
        while myqueue:
            node = myqueue.pop(0)  # 先进先出
            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)  # 生成十个数据作为树节点
    tree = Bitree()  # 新建一个树对象
    for elem in elems:
        tree.addnode(elem)  # 逐个添加树的节点
    print('队列实现层次遍历:')
    tree.level_queue(tree.root)
    print('\n\n递归实现先序遍历:')
    tree.preorder_re(tree.root)
    print('\n递归实现中序遍历:')
    tree.inorder_re(tree.root)
    print('\n递归实现后序遍历:')
    tree.backorder_re(tree.root)
    print('\n\n堆栈实现先序遍历:')
    tree.preorder_stack(tree.root)
    print('\n堆栈实现中序遍历:')
    tree.inorder_stack(tree.root)
    print('\n堆栈实现后序遍历:')
    tree.backorder_stack(tree.root)
'''