"""
bitree.py  二叉樹的簡單實踐
思路分析：
1. 使用鏈式存儲，一個Ｎｏｄｅ表示一個樹的節(jié)點
2. 節(jié)點考慮使用兩個屬性變量分別表示左連接和右連接
"""
from squeue import *

#　二叉樹節(jié)點
class Node:
    def __init__(self,val,left=None,right = None):
        self.val = val
        self.left = left
        self.right = right

# 二叉樹遍歷類
class Bitree:
    def __init__(self,root = None):
        self.root = root

    #　先序遍歷
    def preOrder(self,node):
        if node is None:  #　終止條件
            return
        print(node.val,end = '')
        self.preOrder(node.left)
        self.preOrder(node.right)

    # 　中序遍歷
    def inOrder(self, node):
        if node is None:  # 終止條件
            return
        self.inOrder(node.left)
        print(node.val,end = "")
        self.inOrder(node.right)

    # 　后序遍歷
    def postOrder(self, node):
        if node is None:  # 終止條件
            return
        self.postOrder(node.left)
        self.postOrder(node.right)
        print(node.val, end="")

    #　層次遍歷
    def levelOrder(self,node):
        """
        讓初始節(jié)點先入隊，誰出隊就遍歷誰，并且讓它的左右孩子分別入隊，直到隊列為空
        """
        sq = SQueue()
        sq.enqueue(node) #　初始節(jié)點入隊
        while not sq.is_empty():
            node = sq.dequeue()
            # 　打印出隊元素
            print(node.val,end='')
            if node.left:
                sq.enqueue(node.left)
            if node.right:
                sq.enqueue(node.right)

if __name__ == "__main__":
    # B F G  D  I H E C A
    #　根據(jù)后續(xù)遍歷構建二叉樹
    b = Node('B')
    f = Node('F')
    g = Node('G')
    d = Node('D',f,g)
    i = Node('I')
    h = Node('H')
    e = Node('E',i,h)
    c = Node('C',d,e)
    a = Node('A',b,c)  #樹根

    #　將a作為遍歷的起始位置
    bt = Bitree(a)

    bt.preOrder(bt.root)
    print()
    bt.inOrder(bt.root)
    print()
    bt.postOrder(bt.root)
    print()
    bt.levelOrder(bt.root)