2024年11月7日 星期四

二元搜尋樹教材

 以下是二元搜尋樹教材的分步驟設計，針對每一個步驟提供解釋與相應的 Python 可執行程式碼。最後提供完整的統整程式碼以便檢查整體功能。

(0) 前置作業

在開始建構二元搜尋樹前，先定義樹的基本組成單位——節點 (Node) 和 二元搜尋樹 (Binary Search Tree, BST) 類別。

節點類別和二元搜尋樹的初始設定

# 節點類別，包含值、左連結、右連結
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 二元搜尋樹類別
class BinarySearchTree:
    def __init__(self):
        self.root = None

(1) 插入 (Insert)

插入操作用來將新數值加入到二元搜尋樹中。每次插入時，從根節點開始，依序比較值的大小，決定向左或向右插入新節點。

插入程式碼

class BinarySearchTree:
    # 省略 __init__ 和 Node 類別

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursive(node.right, value)

測試插入

# 建立並插入數值
bst = BinarySearchTree()
for value in [5, 3, 2, 7, 1, 6, 4]:
    bst.insert(value)

搜尋操作用來檢查特定數值是否存在於二元搜尋樹中。從根節點開始，依次比較目標值與當前節點值的大小，決定向左或向右尋找，直到找到目標或確認目標不存在。

搜尋程式碼

class BinarySearchTree:
    # 省略前面插入程式碼

    def search(self, value):
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

測試搜尋

print('搜尋 5:', bst.search(5))  # 輸出 True
print('搜尋 2:', bst.search(2))  # 輸出 True
print('搜尋 8:', bst.search(8))  # 輸出 False

(3) 遍歷 (Traversal)

遍歷是指以特定的順序訪問所有節點。常見的遍歷方法有前序、中序和後序遍歷。

前序遍歷 (Preorder Traversal)

在前序遍歷中，先訪問根節點，然後依次訪問左子節點和右子節點。

class BinarySearchTree:
    # 省略前面的插入和搜尋程式碼

    def preorder_traversal(self):
        result = []
        self._preorder_recursive(self.root, result)
        return result

    def _preorder_recursive(self, node, result):
        if node:
            result.append(node.value)
            self._preorder_recursive(node.left, result)
            self._preorder_recursive(node.right, result)

中序遍歷 (Inorder Traversal)

在中序遍歷中，先訪問左子樹，再訪問根節點，最後訪問右子樹。這樣的順序在二元搜尋樹中會得到排序好的節點。

class BinarySearchTree:
    # 省略前面的插入、搜尋和前序遍歷程式碼

    def inorder_traversal(self):
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

後序遍歷 (Postorder Traversal)

在後序遍歷中，先依次訪問左子節點和右子節點，最後訪問根節點。

class BinarySearchTree:
    # 省略前面的插入、搜尋和其他遍歷程式碼

    def postorder_traversal(self):
        result = []
        self._postorder_recursive(self.root, result)
        return result

    def _postorder_recursive(self, node, result):
        if node:
            self._postorder_recursive(node.left, result)
            self._postorder_recursive(node.right, result)
            result.append(node.value)

測試遍歷

print('前序遍歷:', bst.preorder_traversal())   # 預期 [5, 3, 2, 1, 4, 7, 6]
print('中序遍歷:', bst.inorder_traversal())    # 預期 [1, 2, 3, 4, 5, 6, 7]
print('後序遍歷:', bst.postorder_traversal())  # 預期 [1, 2, 4, 3, 6, 7, 5]

(4) 樹的高度 (Height)

樹的高度是從根節點到最遠葉節點的層數。計算樹的高度可以用遞迴，分別求出左子樹和右子樹的高度，並取較大值再加上 1。

樹的高度程式碼

class BinarySearchTree:
    # 省略前面的插入、搜尋和遍歷程式碼

    def height(self):
        return self._height_recursive(self.root)

    def _height_recursive(self, node):
        if node is None:
            return 0
        else:
            left_height = self._height_recursive(node.left)
            right_height = self._height_recursive(node.right)
            return 1 + max(left_height, right_height)

測試樹高

print('樹的高度:', bst.height())  # 預期 4

(5) 樹的直徑（最大距離）

樹的直徑是樹中兩個節點之間的最長路徑，通常也叫「最大距離」。計算直徑可以使用遞迴，找出每個節點的左子樹和右子樹高度，並比較出最大的距離。

樹的直徑程式碼

class BinarySearchTree:
    # 省略前面的插入、搜尋、遍歷和高度程式碼

    def diameter(self):
        return self._diameter_recursive(self.root)[1]

    def _diameter_recursive(self, node):
        if node is None:
            return 0, 0  # 高度、直徑都為0

        left_height, left_diameter = self._diameter_recursive(node.left)
        right_height, right_diameter = self._diameter_recursive(node.right)

        current_diameter = left_height + right_height
        max_diameter = max(current_diameter, left_diameter, right_diameter)
        current_height = 1 + max(left_height, right_height)

        return current_height, max_diameter

測試樹的直徑

print('樹的直徑（最大距離）:', bst.diameter())  # 預期 4

完整統整程式碼

以下為完整的程式碼，將所有步驟統整在一起：

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursive(node.right, value)

    def search(self, value):
       

 return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

    def preorder_traversal(self):
        result = []
        self._preorder_recursive(self.root, result)
        return result

    def _preorder_recursive(self, node, result):
        if node:
            result.append(node.value)
            self._preorder_recursive(node.left, result)
            self._preorder_recursive(node.right, result)

    def inorder_traversal(self):
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

    def postorder_traversal(self):
        result = []
        self._postorder_recursive(self.root, result)
        return result

    def _postorder_recursive(self, node, result):
        if node:
            self._postorder_recursive(node.left, result)
            self._postorder_recursive(node.right, result)
            result.append(node.value)

    def height(self):
        return self._height_recursive(self.root)

    def _height_recursive(self, node):
        if node is None:
            return 0
        else:
            left_height = self._height_recursive(node.left)
            right_height = self._height_recursive(node.right)
            return 1 + max(left_height, right_height)

    def diameter(self):
        return self._diameter_recursive(self.root)[1]

    def _diameter_recursive(self, node):
        if node is None:
            return 0, 0

        left_height, left_diameter = self._diameter_recursive(node.left)
        right_height, right_diameter = self._diameter_recursive(node.right)

        current_diameter = left_height + right_height
        max_diameter = max(current_diameter, left_diameter, right_diameter)
        current_height = 1 + max(left_height, right_height)

        return current_height, max_diameter

# 測試
bst = BinarySearchTree()
for value in [5, 3, 2, 7, 1, 6, 4]:
    bst.insert(value)

print('搜尋 5:', bst.search(5))
print('搜尋 2:', bst.search(2))

print('前序遍歷:', bst.preorder_traversal())
print('中序遍歷:', bst.inorder_traversal())
print('後序遍歷:', bst.postorder_traversal())

print('樹的高度:', bst.height())
print('樹的直徑（最大距離）:', bst.diameter())

這份教材應包含所有基本操作，並可用於學習與練習二元搜尋樹的核心功能。

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)