数据结构介绍（二）

6. 二叉搜索树（Binary Search Tree，BST）：

二叉搜索树是一种特殊的二叉树，它满足左子节点的值小于根节点，右子节点的值大于根节点。

特点：

• 有序性：树的结构使得查找、插入和删除操作具有较高效率。
• 常用于有序数据的存储和搜索。

Python 示例：

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

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

# 创建一个二叉搜索树
root = None
values = [5, 3, 8, 1, 4, 7, 9]
for value in values:
    root = insert(root, value)

7. 堆（Heap）：

堆是一种基于树的数据结构，具有特定的性质，例如最大堆中每个节点的值都大于或等于其子节点的值。

特点：

• 堆的根节点是最大或最小值，用于高效地查找和删除。
• 常用于优先级队列、排序算法等。

Python 示例：

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

print(heapq.heappop(heap))  # 弹出并输出最小值：1

8. 图（Graph）：

图是一种非线性数据结构，由节点和边组成，用于表示对象之间的关系。

特点：

• 节点和边：图由节点（顶点）和边（连接节点的线）组成。
• 可用于表示社交网络、地图、网络等。

Python 示例：

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, from_node, to_node):
        if from_node not in self.graph:
            self.graph[from_node] = []
        self.graph[from_node].append(to_node)

# 创建一个图
graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'C')

9. 哈希表（Hash Table）：

哈希表是一种用于存储键-值对的数据结构，通过哈希函数将键映射到对应的索引。

特点：

• 高效的插入、查找和删除操作，平均情况下具有常数时间复杂度。
• 常用于字典、缓存等。

Python 示例：

hash_table = {}
hash_table['name'] = 'Alice'
hash_table['age'] = 25

print(hash_table['name'])  # 输出：Alice