在 Python 中實現樹資料結構

樹會以節點和邊來組織資料。每條邊連接一個父節點與子節點，沒有子節點的節點則稱為葉節點。常見的樹包括二元樹、三元樹、二元搜尋樹和 AVL 樹；二元樹中的每個節點最多有兩個子節點。本指南會使用自訂的 Node 類別建立一棵小型二元樹，示範三種深度優先遍歷順序，並介紹可作為替代方案的 anytree 函式庫。

在 Python 中從頭開始實作樹資料結構

簡單的二元樹節點需要一個欄位來存放值，並以參照連結兩個子節點。下方的 Node 類別將值存放在 data；left 和 right 起初都是 None，之後可以指向子節點。將這些物件連接起來，就能建立樹。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

在這裡，root 是 34 和 89 的父節點。節點 45 和 50 是 34 的子節點；89、45 和 50 則是葉節點。這種結構是二元樹，因為每個節點最多有兩個子節點參照。其他樹類型可能需要不同的表示方式，例如使用子節點集合，而不是固定的 left 和 right 屬性。

在 Python 中遍歷二元樹

遍歷會處理每個節點一次；處理順序取決於在遞迴呼叫前後的哪個位置造訪節點。前序遍歷會先造訪目前節點，再遍歷左、右子樹。中序遍歷會依序遍歷左子樹、目前節點、右子樹。後序遍歷則會先遍歷兩個子樹，最後才造訪目前節點。下方的完整範例會建立相同的樹，並印出每種遍歷順序。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)


def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)


def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

print("Pre-order:")
preorder(root)
print("In-order:")
inorder(root)
print("Post-order:")
postorder(root)

遞迴呼叫會沿用第一個章節建立的 left 和 right 參照。若要遍歷另一棵樹，可以保留遍歷函式並替換節點的建立方式；造訪節點的位置會決定值的排列順序。

使用 Python 函式庫實作樹

如果樹包含許多節點，或需要這個小型二元樹範例以外的功能，anytree 可用來管理節點關係並呈現樹狀結構。請在專案環境中使用 pip install anytree 安裝。在它的 API 中，Node 的位置引數是節點名稱；若要附加子節點，請以關鍵字引數傳入 parent=root。RenderTree 會逐一走訪階層，並提供用來顯示各層的前綴。

若要建立與上方相同的結構，可以先使用 root = Node("10")，接著建立 Node("34", parent=root) 和 Node("89", parent=root)。再建立 Node("45", parent=left_child) 和 Node("50", parent=left_child)，將兩個葉節點放在 34 之下；然後使用 for pre, fill, node in RenderTree(root) 進行迭代，並印出 pre + node.name。這些片段說明的是函式庫 API；未提供其執行證據。