C / C++ / 系统课时
树结构怎样表示层级关系
树结构怎样表示层级关系
线性表擅长表达“前后相邻”,但文件目录、组织架构和分类菜单更关心“谁属于谁”。树结构通过父子关系把数据组织成层级,本节先建立树的基本术语,再理解它与线性结构的根本区别。
学习目标
- 能识别根、父节点、子节点、叶子节点和子树等基本概念
- 能用父子关系解释层级数据为何适合用树表示
- 能区分树结构与数组、链表这类线性结构的组织方式
从线性关系到父子关系
数组和链表主要描述一条连续序列:一个元素前面或后面还有哪个元素。树则允许一个节点连接多个下一层节点,因此能自然表示“一对多”的层级关系。
一棵非空树只有一个根节点。除根节点外,每个节点都有且只有一个父节点;一个节点可以没有子节点,也可以有多个子节点。沿父子关系向下,可以把某个节点及其所有后代看成一棵子树。

树里的基本术语
理解树时,先把术语放回关系中,而不是孤立记定义。
- 根节点:整棵树的起点,没有父节点。
- 父节点与子节点:若两个节点直接相连且存在上下层关系,上层是父节点,下层是子节点。
- 兄弟节点:拥有同一个父节点的节点。
- 叶子节点:没有子节点的节点。
- 子树:某个节点连同它全部后代形成的树。
- 层级:从根开始按连接关系向下划分的深度位置;具体从 0 还是 1 开始计数取决于约定。
层级数据怎样映射成树
例如一个项目目录可以抽象成节点与父节点的关系。重点不在文件名本身,而在“哪个节点直接归属于哪个父节点”。
| 节点 | 父节点 | 角色 |
|---|---|---|
| project | 无 | 根节点 |
| src | project | 中间节点 |
| docs | project | 中间节点 |
| main.c | src | 叶子节点 |
| guide.md | docs | 叶子节点 |
从 project 到 main.c 需要经过 src,这条路径体现了层级。因为每个非根节点只有一个父节点,所以从根到任意节点只有一条确定的父子路径;这也是树与一般图结构的重要区别之一。
与线性表的核心区别
线性表中的元素主要形成一条顺序关系,适合表示队列、顺序记录或按位置访问的数据。树中的节点形成层级关系,更适合表达分类、隶属、包含和递归分解。
| 比较点 | 线性表 | 树 |
|---|---|---|
| 关系形态 | 前后相邻的一维序列 | 父子构成的多层结构 |
| 一个元素的下一层连接 | 通常至多一个直接后继 | 可以有多个子节点 |
| 常见场景 | 顺序记录、队列、栈底层存储 | 目录、组织架构、语法结构、搜索结构 |
| 典型处理方式 | 从头到尾或按下标访问 | 从根出发按层级递归或迭代遍历 |
当数据的核心问题是“前后顺序”时,线性表通常更直接;当问题是“包含谁、属于谁、下一层有哪些成员”时,树能把关系直接编码进结构。后续学习二叉树时,只是在“每个节点最多有几个孩子”上进一步增加约束,层级组织思想并没有改变。
按自己的节奏,确认真正理解。