软考知识点——树、图的定义、存储和基本运算

树的定义、存储和基本运算

定义

树是一种非线性数据结构，由 n（n ≥ 0）个节点 组成的有限集合。当 n = 0 时称为空树；非空树中有一个根节点，其余节点分为 m（m ≥ 0）个互不相交的有限集合，每个子集本身又是一棵树，称为子树。树的核心条件包括：

1. 唯一根节点：有且仅有一个根节点。
2. 互斥子树：除根节点外，其他节点形成互不相交的子树集合。

存储方式

1. 双亲表示法（顺序存储）

   • 结构：用数组存储节点，每个节点包含数据域和父指针（如 parent = -1 表示根节点）。
   • 优点：查找父节点高效（O(1)）。
   • 缺点：查找子节点需遍历整个数组（O(n)）。
   • 示例：

     #define MAX_SIZE 100
     typedef struct {
         int data;
         int parent; // 父节点下标
     } TreeNode;
     TreeNode tree[MAX_SIZE];
     

2. 孩子表示法（顺序+链式存储）

   • 结构：每个节点维护一个子节点链表，包含数据域和指向子节点的指针。
   • 优点：查找子节点高效（O(1) 遍历链表）。
   • 缺点：需额外空间存储指针，且子节点数量不固定时可能浪费空间。
   • 示例：

     #define MAX_CHILD 3
     typedef struct ChildNode {
         int data;
         struct ChildNode *children[MAX_CHILD]; // 子节点指针数组
     } ChildNode;
     

3. 孩子兄弟表示法（二叉链表）

   • 结构：每个节点包含两个指针，分别指向第一个孩子和右兄弟，将树转化为二叉树形式。
   • 优点：统一存储结构，便于实现树的遍历和操作。
   • 示例：

     typedef struct TreeNode {
         int data;
         struct TreeNode *firstChild; // 第一个孩子
         struct TreeNode *nextSibling; // 右兄弟
     } TreeNode;
     

基本运算

1. 创建树：初始化根节点及子树结构。
2. 遍历：
   • 先序遍历：访问根节点后，依次遍历每棵子树。
   • 后序遍历：先遍历子树，再访问根节点。
   • 层次遍历：按层级从上到下、从左到右访问节点。
3. 查找节点：根据值或位置查找节点（如查找父节点、子节点）。
4. 插入/删除子树：在指定位置插入或删除子树，需维护节点间关系。
5. 求树深度：计算从根节点到最远叶子节点的路径长度。
6. 判断空树：检查根节点是否存在。

图的定义、存储和基本运算

定义

图是一种非线性数据结构，由 顶点集合（V） 和 边集合（E） 组成，表示对象之间的复杂关系。图分为：

• 有向图：边有方向（如 A → B）。
• 无向图：边无方向（如 A - B）。
• 加权图：边带有权重（如距离、成本）。

存储方式

1. 邻接矩阵

   • 结构：用二维数组 matrix[n][n] 表示顶点间关系，matrix[i][j] = 1 表示存在边 i → j。
   • 优点：快速检查任意两个顶点是否相连（O(1)）。
   • 缺点：空间复杂度高（O(n²)），稀疏图中浪费空间。
   • 示例：

     #define N 5
     int matrix[N][N] = {
         {0, 1, 0, 0, 1},
         {1, 0, 1, 1, 0},
         // ... 其他行
     };
     

2. 邻接表

   • 结构：每个顶点对应一个链表，链表节点存储相邻顶点及边权值。
   • 优点：节省空间（O(V + E)），适合稀疏图。
   • 缺点：检查任意两点是否相连需遍历链表（O(degree(v))）。
   • 示例：

     typedef struct EdgeNode {
         int adjvex; // 相邻顶点下标
         int weight; // 边权值
         struct EdgeNode *next;
     } EdgeNode;
     
     typedef struct VertexNode {
         int data;
         EdgeNode *firstEdge;
     } VertexNode;
     
     VertexNode graph[N]; // 邻接表
     

3. 十字链表（有向图优化）

   • 结构：结合邻接表和逆邻接表，每个弧节点包含指向弧头和弧尾的指针，便于计算顶点的出度和入度。
   • 优点：高效统计顶点的入度和出度。

4. 邻接多重表（无向图优化）

   • 结构：每条边用一个节点表示，同时链接在两个顶点的链表中，适合频繁删除边的操作。

基本运算

1. 创建图：初始化顶点集合和边集合，构建邻接矩阵或邻接表。
2. 遍历：
   • 深度优先搜索（DFS）：从起点出发，尽可能深地探索图的分支。
   • 广度优先搜索（BFS）：按层级遍历顶点，适合寻找最短路径。
3. 查找顶点/边：根据值或位置查找顶点或边。
4. 插入/删除顶点/边：
   • 删点：需删除所有关联边。
   • 删边：仅需更新邻接结构。
5. 图运算：
   • 并运算（G1 ∪ G2）：合并两个图的顶点和边。
   • 交运算（G1 ∩ G2）：保留两个图共有的顶点和边。
   • 差运算（G1 - G2）：从 G1 中删除 G2 的边。
   • 联运算（G1 ∨ G2）：将两个不相交图的顶点两两连接。
   • 积图（G1 × G2）：通过笛卡尔积生成新图的顶点和边。
6. 最短路径算法：如 Dijkstra 算法（加权图）或 Floyd 算法（多源最短路径）。
7. 最小生成树：如 Prim 算法或 Kruskal 算法（加权无向图）。