10 数据结构概述之树和图

在我们了解完整个数据结构的框架后，上一篇文章中我们探讨了“栈”和“队列”的基本概念及其应用。接下来，我们将重点讲解“树”和“图”这两种重要的数据结构。树和图在计算机科学中起着至关重要的作用，广泛应用于数据库、网络、路由、编译器等多个领域。

一、树

1. 什么是树

树是一种层次型的数据结构，由节点（node）组成。它的每一个节点都可以有零个或多个子节点，但每个节点只有一个父节点，树的顶层称为“根节点”（root）。树的特点包括：

• 无环性：树结构中不存在环。
• 层次性：节点有一定的层级关系，根节点为层级0，其子节点为层级1，依此类推。

2. 树的分类

• 二叉树：每个节点最多有两个子节点（左、右）。
• 平衡树：所有叶子节点的深度相同。
• 二叉搜索树（BST）：对于每个节点，其左子树的值小于该节点的值，右子树的值大于该节点的值。

3. 树的常见操作

对于树的操作主要包括插入、删除和遍历。以下是一个简单的二叉搜索树的插入操作的 Python 代码示例：

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

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

# 示例用法
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)

在这个示例中，我们定义了一个Node类表示树的节点，并实现了insert函数将新节点插入到二叉搜索树中。

4. 树的遍历

树的遍历分为三种主要方式：

• 前序遍历（Pre-order）：根 -> 左 -> 右
• 中序遍历（In-order）：左 -> 根 -> 右
• 后序遍历（Post-order）：左 -> 右 -> 根

以下是中序遍历的示例代码：

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=' ')
        inorder_traversal(root.right)

# 使用中序遍历输出树的内容
inorder_traversal(r)  # 输出: 20 30 40 50 60 70 80

二、图

1. 什么是图

图是一种由节点（或称为“顶点”）和连接这些节点的边（edge）组成的数据结构。不同于树，图是非线性结构，它可以包含环（cycle），并且节点之间的连接是多对多的关系。

2. 图的表示

图可以通过以下两种方式表示：

• 邻接矩阵（Adjacency Matrix）：使用二维数组表示边的连接关系。
• 邻接列表（Adjacency List）：使用链表或字典（hash map）表示每个节点的相邻节点。

以下是邻接矩阵的示例：

# 无向图的邻接矩阵表示
graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

3. 图的遍历

图的遍历方式主要有两种：

• 深度优先搜索（DFS）：尽可能深的搜索图的分支。
• 广度优先搜索（BFS）：层层往外搜索图的节点。

以下是深度优先搜索的 Python 实现：

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    
    for i in range(len(graph[v])):
        if graph[v][i] == 1 and not visited[i]:
            dfs(graph, i, visited)

# 示例用法
visited = [False] * len(graph)
dfs(graph, 0, visited)  # 从第一个节点开始DFS

结语

在本篇教程中，我们对树和图这两种数据结构进行了详细的概述，重点讲解了它们的基本概念、分类及常见操作。树提供了一种简洁的层次化数据组织方式，而图则展示了更为复杂的关系。理解这些数据结构的基本特性，对于后续的算法分析（如时间复杂度）将大有裨益。

在下一篇文章中，我们将讲解“算法分析之时间复杂度”，继续深入算法领域的探讨。希望本篇内容对你理解树和图有所帮助！