基於Python的BinaryTree實現

引言

二叉樹是一種非常常見且重要的數據結構，它廣泛應用於計算機科學和演算法的設計中。其中，二叉樹所用的數據結構關係比較簡單，適合各類演算法的實現。這篇文章將會介紹基於Python的BinaryTree實現，它為我們深入了解二叉樹的工作方式和如何應用演算法提供了一個很好的起點。

二叉樹數據結構

二叉樹是由節點組成的樹狀數據結構，每個節點有一個值、一個左節點、和一個右節點。左節點和右節點可以是空值。如果節點的左、右節點都不為空，那麼分別稱這個節點為該節點左孩子和右孩子。如果一個節點沒有子節點，那麼稱這個節點為葉節點。

class Node:
    def __init__(self, val: int):
        self.value = val
        self.left = None
        self.right = None

上面的代碼創建了一個簡單的節點類。它有一個值、一個左節點和右節點。left、right 可以是一個Node類型或者None。

二叉樹的遍歷

遍歷是指按照一定次序，依次對所有的節點進行訪問。在二叉樹中，最常見的遍歷方式為：前序遍歷、中序遍歷、後序遍歷和層序遍歷。

前序遍歷

前序遍歷的順序是：根節點、左子樹、右子樹。以下是前序遍歷的代碼：

def pre_order_traversal(node: Node):
    if node is None:
        return
    print(node.value, end=' ')
    pre_order_traversal(node.left)
    pre_order_traversal(node.right)

中序遍歷

中序遍歷的順序是：左子樹、根節點、右子樹。以下是中序遍歷的代碼：

def in_order_traversal(node: Node):
    if node is None:
        return
    in_order_traversal(node.left)
    print(node.value, end=' ')
    in_order_traversal(node.right)

後序遍歷

後序遍歷的順序是：左子樹、右子樹、根節點。以下是後序遍歷的代碼：

def post_order_traversal(node: Node):
    if node is None:
        return
    post_order_traversal(node.left)
    post_order_traversal(node.right)
    print(node.value, end=' ')

層序遍歷

層序遍歷即按照層次依次訪問，使用隊列實現。從根節點開始，先將根節點壓入隊列，每次從隊列中取出一個節點，若其左子節點不為空，則將左子節點壓入隊列，同樣，如果其右子節點不為空，則將右子節點壓入隊列。直到隊列為空為止。

def level_order_traversal(root: Node):
    if not root: return []
    res, queue = [], [root]
    while queue:
        level_res = []
        size = len(queue)
        for _ in range(size):
            node = queue.pop(0)
            level_res.append(node.value)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level_res)
    return res

二叉樹的查找、插入、刪除

查找操作

因為二叉樹的數據結構可以保持其子樹中的所有左子樹的值都小於父節點的值，子樹中所有右子樹的值都大於父節點的值。因此，查找一個值可以使用下面代碼：

def search_bst(root: Node, val: int):
    while root and root.value != val:
        if val < root.value:
            root = root.left
        else:
            root = root.right
    return root

插入操作

插入節點操作，加入一個節點到二叉樹中。可以使用下面代碼實現：

def insert_node(root: Node, val: int):
    if not root: return Node(val)
    if root.value  val:
        root.left = insert_node(root.left, val)
    return root

刪除操作

二叉樹中的節點是可以被刪除的，刪除一個節點需要知道一個盡量好的節點來取代被刪除的節點。在二叉樹中，常見的取代方式是：將右子樹中最小的節點或者左子樹中最大的節點取代要刪除的節點。這裡我們僅實現將右子樹中最小的節點取代的情況，可以使用如下代碼：

def remove_node(root: Node, val: int):
    if not root: return None
    if root.value == val:
        # 左右孩子均為空
        if not root.left and not root.right:
            return None
        # 左右孩子均非空
        elif root.left and root.right:
            min_node = root.right
            while min_node.left:
                min_node = min_node.left
            root.value = min_node.value
            root.right = remove_node(root.right, min_node.value)
        # 左孩子為空
        elif not root.left:
            return root.right
        # 右孩子為空
        elif not root.right:
            return root.left
    elif root.value < val:
        root.right = remove_node(root.right, val)
    else:
        root.left = remove_node(root.left, val)
    return root

應用示例：判斷二叉樹是否為BST

上面我們已經介紹了二叉樹的遍歷、查找、插入和刪除操作。這裡我們以判斷一個二叉樹是否為BST為例子，並展示如何使用二叉樹進行演算法設計。

該演算法需要判斷二叉樹是否符合BST的定義，即左子樹的所有節點應該的小於其父節點，右子樹的所有節點應該大於其父節點。可以遞歸進行判斷：

def is_valid_bst(root: Node) -> bool:
    def check(root, left, right):
        if not root:
            return True
        if left and root.value = right.value:
            return False
        return check(root.left, left, root) and check(root.right, root, right)
    return check(root, None, None)

結論

本文介紹了Python語言中的二叉樹數據結構。通過對這些演算法的詳細解釋和Python實現，我們希望能夠幫助讀者更好地理解和應用該數據結構。這些演算法是程序員必備的基礎演算法，不僅在面試中經常被提及，而且在實際工作中也經常被使用。