数据结构之非线性结构

非线性结构：树与图的核心概念与特性

非线性结构是指数据元素之间存在一对多或多对多关系的结构，无法用线性序列完整描述。常见的非线性结构包括树（一对多）和图（多对多），它们广泛应用于层次关系建模（如文件系统）、网络关系描述（如社交网络）等场景。

树是一种具有层次关系的非线性结构，核心特征是存在一个根节点，其余节点分属不同子树，形成一对多的分支关系。

树是由 n（n ≥ 0） 个节点组成的有限集合：

核心特征：

父节点、子节点、兄弟节点：
若节点 A 是节点 B 的直接前驱，则 A 是 B 的父节点，B 是 A 的子节点；具有相同父节点的节点互称为兄弟节点。
节点的度：
节点拥有的子节点数量（即直接后继的个数）。度为 0 的节点称为叶子节点（终端节点）；度不为 0 的节点称为分支节点（非终端节点）。
树的度：
树中所有节点的最大度数（反映树的 “分支能力”）。
层数与深度：
- 根节点为第 1 层，其子节点为第 2 层，依次类推。
- 树的深度（高度）是树中节点的最大层数。
有序树与无序树：
- 有序树：子树按固定顺序（如左到右）排列，交换子树位置会改变树的结构。
- 无序树：子树无固定顺序，交换子树位置不改变树的结构。
森林：
由 m（m ≥ 0） 棵互不相交的树组成的集合（可理解为 “多棵树的组合”）。

二叉树是每个节点最多有两个子节点的树（度 ≤ 2），且子节点有明确的 “左”“右” 之分（即使只有一个子节点，也需区分左 / 右子树）。

第 i 层最多有 2^(i-1) 个节点（i ≥ 1）。
深度为 k 的二叉树最多有 2^k - 1 个节点（满二叉树的情况）。
对任意二叉树，若叶子节点数为 n₀，度为 2 的节点数为 n₂，则 n₀ = n₂ + 1（推导：总边数 = 总节点数 - 1，且边数 = 度为 1 的节点数 + 2× 度为 2 的节点数）。
具有 n 个节点的完全二叉树，深度为 ⌊log₂n⌋ + 1（⌊x⌋ 表示向下取整）。

满二叉树：
深度为 k 且节点总数为 2^k - 1 的二叉树（每一层都满，无空缺）。
完全二叉树：
深度为 k 的二叉树，前 k-1 层为满二叉树，第 k 层的节点从左到右连续排列（无跳跃）。
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

二叉树的存储需体现节点间的父子关系，常见方式有：

存储方式	结构定义	优点	缺点
双亲表示法	每个节点存储 `(数据, 父节点索引)`	便于找父节点（O (1)）	找子节点需遍历全树（O (n)）
孩子表示法	每个节点存储 `(数据, 子节点链表)`	便于找子节点（O (1) 到链表头）	找父节点需额外存储（如双亲指针）
孩子兄弟表示法	每个节点存储 `(数据, 左孩子指针, 右兄弟指针)`	可将任意树转为二叉树处理（左孩子为第一个子节点，右兄弟为同级节点）	理解稍复杂，需明确左 / 右指针含义

图是比树更通用的非线性结构，允许任意节点之间建立关系（多对多），无 “层次” 或 “前驱唯一” 的限制。

图由顶点（Vertex）和边（Edge）组成，记为 G = (V, E)：

核心特征：

有向图与无向图：
- 无向图：边无方向，若顶点 u 和 v 相连，则边可表示为 (u, v)（与 (v, u) 等价）。
- 有向图：边有方向，从 u 到 v 的边记为 <u, v>（u 为起点，v 为终点，与 <v, u> 不同）。
顶点的度：
- 无向图中，顶点的度是与该顶点相连的边的数量。
- 有向图中，分为入度（指向该顶点的边数）和出度（从该顶点出发的边数），总度数 = 入度 + 出度。
路径与回路：
- 路径：从顶点 u 到 v 的顶点序列，相邻顶点由边连接。
- 回路（环）：起点与终点相同的路径。
连通图：
- 无向图中，任意两个顶点之间都存在路径，称为连通图；否则为非连通图。
- 有向图中，任意两个顶点 u 和 v 之间都存在从 u 到 v 和从 v 到 u 的路径，称为强连通图。