C / C++ / 系统课时

树结构怎样表示层级关系

树结构怎样表示层级关系

线性表擅长表达“前后相邻”,但文件目录、组织架构和分类菜单更关心“谁属于谁”。树结构通过父子关系把数据组织成层级,本节先建立树的基本术语,再理解它与线性结构的根本区别。

学习目标

  • 能识别根、父节点、子节点、叶子节点和子树等基本概念
  • 能用父子关系解释层级数据为何适合用树表示
  • 能区分树结构与数组、链表这类线性结构的组织方式

从线性关系到父子关系

数组和链表主要描述一条连续序列:一个元素前面或后面还有哪个元素。树则允许一个节点连接多个下一层节点,因此能自然表示“一对多”的层级关系。

一棵非空树只有一个根节点。除根节点外,每个节点都有且只有一个父节点;一个节点可以没有子节点,也可以有多个子节点。沿父子关系向下,可以把某个节点及其所有后代看成一棵子树。

树结构中的根节点父子节点与层级

树里的基本术语

理解树时,先把术语放回关系中,而不是孤立记定义。

  • 根节点:整棵树的起点,没有父节点。
  • 父节点与子节点:若两个节点直接相连且存在上下层关系,上层是父节点,下层是子节点。
  • 兄弟节点:拥有同一个父节点的节点。
  • 叶子节点:没有子节点的节点。
  • 子树:某个节点连同它全部后代形成的树。
  • 层级:从根开始按连接关系向下划分的深度位置;具体从 0 还是 1 开始计数取决于约定。

层级数据怎样映射成树

例如一个项目目录可以抽象成节点与父节点的关系。重点不在文件名本身,而在“哪个节点直接归属于哪个父节点”。

节点 父节点 角色
project 无 根节点
src project 中间节点
docs project 中间节点
main.c src 叶子节点
guide.md docs 叶子节点

从 project 到 main.c 需要经过 src,这条路径体现了层级。因为每个非根节点只有一个父节点,所以从根到任意节点只有一条确定的父子路径;这也是树与一般图结构的重要区别之一。

与线性表的核心区别

线性表中的元素主要形成一条顺序关系,适合表示队列、顺序记录或按位置访问的数据。树中的节点形成层级关系,更适合表达分类、隶属、包含和递归分解。

比较点 线性表 树
关系形态 前后相邻的一维序列 父子构成的多层结构
一个元素的下一层连接 通常至多一个直接后继 可以有多个子节点
常见场景 顺序记录、队列、栈底层存储 目录、组织架构、语法结构、搜索结构
典型处理方式 从头到尾或按下标访问 从根出发按层级递归或迭代遍历

当数据的核心问题是“前后顺序”时,线性表通常更直接;当问题是“包含谁、属于谁、下一层有哪些成员”时,树能把关系直接编码进结构。后续学习二叉树时,只是在“每个节点最多有几个孩子”上进一步增加约束,层级组织思想并没有改变。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

树结构怎样表示层级关系

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通