二元樹教材 dict 版

 # 插入新值

def insert(tree, value):

    if tree is None:

        return {"value": value, "left": None, "right": None}

    if value < tree["value"]:

        tree["left"] = insert(tree["left"], value)

    else:

        tree["right"] = insert(tree["right"], value)

    return tree

# 搜尋特定值

def search(tree, value):

    if tree is None:

        return False

    if tree["value"] == value:

        return True

    elif value < tree["value"]:

        return search(tree["left"], value)

    else:

        return search(tree["right"], value)

# 前序遍歷

def preorder_traversal(tree):

    if tree is None:

        return []

    return [tree["value"]] + preorder_traversal(tree["left"]) + preorder_traversal(tree["right"])

# 中序遍歷

def inorder_traversal(tree):

    if tree is None:

        return []

    return inorder_traversal(tree["left"]) + [tree["value"]] + inorder_traversal(tree["right"])

# 後序遍歷

def postorder_traversal(tree):

    if tree is None:

        return []

    return postorder_traversal(tree["left"]) + postorder_traversal(tree["right"]) + [tree["value"]]

# 計算樹高

def height(tree):

    if tree is None:

        return 0

    left_height = height(tree["left"])

    right_height = height(tree["right"])

    return 1 + max(left_height, right_height)

# 計算樹的直徑

def diameter(tree):

    def _diameter_and_height(node):

        if node is None:

            return 0, 0

        left_height, left_diameter = _diameter_and_height(node["left"])

        right_height, right_diameter = _diameter_and_height(node["right"])

        current_height = 1 + max(left_height, right_height)

        current_diameter = left_height + right_height

        max_diameter = max(current_diameter, left_diameter, right_diameter)

        return current_height, max_diameter

    _, tree_diameter = _diameter_and_height(tree)

    return tree_diameter

# 測試二元搜尋樹功能

bst = None

for value in [5, 3, 2, 7, 1, 6, 4]:

    bst = insert(bst, value)

print("搜尋 5:", search(bst, 5))  # 預期 True

print("搜尋 2:", search(bst, 2))  # 預期 True

print("搜尋 8:", search(bst, 8))  # 預期 False

print("前序遍歷:", preorder_traversal(bst))   # 預期 [5, 3, 2, 1, 4, 7, 6]

print("中序遍歷:", inorder_traversal(bst))    # 預期 [1, 2, 3, 4, 5, 6, 7]

print("後序遍歷:", postorder_traversal(bst))  # 預期 [1, 2, 4, 3, 6, 7, 5]

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

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

# 執行結果

# 搜尋 5: True

# 搜尋 2: True

# 搜尋 8: False

# 前序遍歷: [5, 3, 2, 1, 4, 7, 6]

# 中序遍歷: [1, 2, 3, 4, 5, 6, 7]

# 後序遍歷: [1, 2, 4, 3, 6, 7, 5]

# 樹的高度: 4

# 樹的直徑（最大距離）: 5