18 数据结构与算法之树与图

在上一篇中，我们讨论了 栈 和 队列 这两种重要的数据结构。本篇将深入探讨 树 和 图，这两者在计算机科学中扮演着至关重要的角色，尤其是在表示层次结构和复杂关系时。

5.3.1 树

1. 什么是树？

树是一种非线性数据结构，由节点（nodes）和边（edges）组成。树具有以下特征：

• 有一个根节点（root），其他节点通过边连接。
• 每个节点可以有零个或多个子节点（children）。
• 除根节点外，每个节点都有一个唯一的父节点（parent）。
• 树形结构没有循环。

2. 树的基本术语

• 高度（Height）：从树的根节点到最叶子节点的最长路径上的边数。
• 深度（Depth）：从根节点到某个节点的路径长度。
• 叶子节点（Leaf Node）：没有子节点的节点。

3. 树的类型

• 二叉树（Binary Tree）：每个节点最多有两个孩子，通常称为左孩（left child）和右孩（right child）。
• 二叉搜索树（Binary Search Tree, BST）：左孩子的值小于父节点，右孩子的值大于父节点。
• AVL树：一种自平衡的二叉搜索树，保证操作的时间复杂度为 $O(\log n)$。
• 红黑树：另一种自平衡的二叉搜索树，具有颜色标记的节点来保持平衡。

4. 树的基本操作

以下是一些基本操作的实现示例（以二叉树为例）：

插入节点

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* insert(Node* root, int data) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

遍历树

树的遍历可分为前序、中序和后序遍历。

void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

5.3.2 图

1. 什么是图？

图是一种由节点（顶点）和连接这些节点的边构成的数据结构。图可以表示复杂的关系，并具有以下基本特征：

• 节点通过边连接，边可以是有向的或无向的。
• 一个图可以包含环（cycles），也可以是无环（如树）。

2. 图的类型

• 有向图（Directed Graph）：边有方向，有序对 (u, v) 表示从顶点 $u$ 到 $v$ 的一条边。
• 无向图（Undirected Graph）：边没有方向，连接两个顶点的边可以用无序对 {u, v} 表示。
• 加权图（Weighted Graph）：边上有权值，常用来表示成本或距离。

3. 图的存储方式

图一般使用两种方式存储：

• 邻接矩阵（Adjacency Matrix）：使用一个二维数组存储节点间的关系。
• 邻接链表（Adjacency List）：使用链表存储每个节点的边的信息，适合稀疏图。

邻接链表的示例

typedef struct Edge {
    int destination;
    struct Edge* next;
} Edge;

typedef struct Vertex {
    int data;
    Edge* edges;
} Vertex;

typedef struct Graph {
    int numVertices;
    Vertex* vertices;
} Graph;

4. 图的基本操作

深度优先搜索（DFS）

void DFS(Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", graph->vertices[vertex].data);
    
    Edge* edge = graph->vertices[vertex].edges;
    while (edge != NULL) {
        if (!visited[edge->destination]) {
            DFS(graph, edge->destination, visited);
        }
        edge = edge->next;
    }
}

广度优先搜索（BFS）

void BFS(Graph* graph, int startVertex) {
    Queue* queue = createQueue();
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    memset(visited, 0, graph->numVertices * sizeof(int));

    enqueue(queue, startVertex);
    visited[startVertex] = 1;
    
    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("%d ", graph->vertices[currentVertex].data);

        Edge* edge = graph->vertices[currentVertex].edges;
        while (edge != NULL) {
            if (!visited[edge->destination]) {
                enqueue(queue, edge->destination);
                visited[edge->destination] = 1;
            }
            edge = edge->next;
        }
    }
}

5. 总结

本篇介绍了 树 和 图 两种重要的数据结构，讲解了它们的基本概念、操作及实现示例。树结构适合表示层级关系，而图结构则用于表示更为复杂的连接关系。在实际应用中，选择合适的数据结构是提升程序性能和可维护性的关键。

接下来，我们将进入经典算法的实现部分，这将帮助加深理解数据结构在解决问题中的应用，以及如何优化算法效率。