二叉樹

# 構建節點類
class BiTreeNode:
    def __init__(self, item):
        self.item = item
        self.leftChild = None
        self.rightChild = None

# 創建樹節點
a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')

# 模擬樹
e.leftChild = a
e.rightChild = g
a.rightChild = c
c.leftChild = b
c.rightChild = d
g.rightChild = f
# 根節點
root = e

from collections import deque
# 遍歷樹類
class ForInBiTree:
    # 前序遍歷：以根節點為中點分為左右兩邊，從根節點出發先遍歷左邊在遍歷右邊，從上左右原則
    def pre_order(self, root):
        # 判斷是否是一個空樹
        if root:
            print(root.item, end=',')           # 先遍歷根節點
            self.pre_order(root.leftChild)      # 遞歸傳入左節點為參數，即往左邊走
            self.pre_order(root.rightChild)     # 遞歸傳入右節點為參數，沒有左子樹，在往右走

    # 中序遍歷：以根節點為中心點，先遍歷左邊在到根節點再遍歷左邊，先左上右原則
    def cen_order(self, root):
        if root:
            self.cen_order(root.leftChild)      # 遞歸傳入左節點為參數，即往左邊走
            print(root.item, end=',')           # 沒有左子樹則遍歷自己
            self.cen_order(root.rightChild)     # 在往右進行遍歷

    # 后序遍歷：以根節點為中心點，先遍歷左邊再遍歷右邊再根節點，從左右上原則
    def later_order(self, root):
        if root:
            self.later_order(root.leftChild)    # 先找左邊的子節點
            self.later_order(root.rightChild)   # 在找優點的子節點
            print(root.item, end=',')           # 沒有則輸出當前根節點

    # 層次遍歷：從根節點開始，從上往下開始遍歷
    def level_order(self, root):
        # 利用隊列的先進先出原則
        queue = deque()
        queue.append(root)      # 根節點進入隊列
        while len(queue) > 0:   # 當隊列中存在元素則說明還有子節點
            node = queue.popleft()      # 當前根節點指向出隊列的節點
            print(node.item, end=',')
            # 按照從左往右的順序加入隊列
            if node.leftChild:
                queue.append(node.leftChild)
            if node.rightChild:
                queue.append(node.rightChild)

forInBiTree = ForInBiTree()
# 前序遍歷結果：E,A,C,B,D,G,F
forInBiTree.pre_order(root)
# 中序遍歷結果：A,B,C,D,E,G,F
forInBiTree.cen_order(root)
# 后序遍歷結果：B,D,C,A,F,G,E
forInBiTree.later_order(root)
# 層次遍歷結果：E,A,G,C,F,B,D
forInBiTree.level_order(root)