树的基本概念与存储结构

如果说前面的顺序表、链表、栈、队列都还属于“一条线上的世界”，那么从树开始，数据结构学习就正式进入了“层级世界”。树最大的不同在于，它不再只是简单地表示前后顺序，而是能够表示从属关系、层次关系和分支关系。现实里很多复杂对象，本来就不是排成一列的，而是天然分层的，比如文件目录、组织架构、HTML 文档、表达式结构、分类体系。

也正因为如此，树几乎是数据结构里的分水岭。学会树之后，你会开始真正习惯：

  • 不再只从“前一个后一个”看数据；
  • 而是从“父子、祖先、子孙、层次、路径”去理解结构；
  • 很多算法也会从简单遍历，过渡到递归处理和结构化分析。

所以这一篇的重点，是先把树的基础地图搭起来：树到底是什么，常见术语有哪些，和线性结构有何不同，以及树有哪些典型存储方式。后面所有关于二叉树、搜索树、堆、Trie、B+ 树的内容，都建立在这层基础认知之上。

一、什么是树

树可以先用一句比较抽象但很重要的话来定义：

树是由 n 个节点组成的有限集合，当 n > 0 时，其中有且仅有一个特定节点称为根，其余节点可分为若干个互不相交的子集，每个子集本身又是一棵树。

这一定义里最值得抓住的，不是措辞本身，而是两个核心点：

1. 树有根

和图、链表不同，树通常有一个起点，也就是根节点。

2. 树具有递归性

一棵树的子树，本身仍然是树。

也正因为这个递归特征，树问题和递归思维会天然绑定在一起。

二、为什么树适合表达层级关系

因为树天然支持“一对多”的分支结构。

在线性表中，一个元素前后通常只有一个直接邻居；但在树里，一个节点可以：

  • 有多个孩子；
  • 形成层级；
  • 延伸出不同分支。

例如文件目录：

  • 一个目录下面可以有多个子目录；
  • 每个子目录下面又可以继续分层；
  • 整体形成清晰的层级关系。

这种结构如果硬用线性表表示，会很别扭；而用树来描述则非常自然。

三、树中的常见术语有哪些

树一开始最容易让人混乱的就是术语比较多，所以这部分一定要先理顺。

1. 根节点

整棵树最上面的节点，没有父节点。

2. 节点的度

一个节点拥有的子节点个数，叫这个节点的度。

3. 树的度

整棵树中所有节点度的最大值。

4. 叶子节点

没有子节点的节点，也叫终端节点。

5. 内部节点

不是叶子节点的节点，通常至少有一个孩子。

6. 双亲节点与孩子节点

如果节点 A 的下一级包含节点 B，那么：

  • A 是 B 的双亲；
  • B 是 A 的孩子。
7. 兄弟节点

拥有同一个双亲的节点，彼此互称兄弟。

8. 祖先与子孙

从根到某节点路径上的所有上层节点，都是它的祖先；某节点下面所有层级的后代，都是它的子孙。

9. 节点的层次

通常根节点为第 1 层，其子节点为第 2 层，依此类推。

10. 树的高度或深度

树中节点的最大层数，叫树的高度。

这些术语后面几乎每篇树相关文章都会用到，所以这里一定要真正理解，而不是只背字面定义。

四、路径与路径长度是什么意思

树中一个节点到另一个节点之间，如果经过若干条边相连，就形成一条路径。

例如从根节点走到某个叶子节点，这条经过的节点序列就是一条路径。

  • 路径长度通常指经过的边数；
  • 从根到某节点的路径在树中通常是唯一的。

这点非常重要，因为树和一般图相比，一个很关键的特征就是：

树中任意两个节点之间通常只有唯一简单路径。

这让很多查找、遍历和递归问题都比一般图更容易分析。

五、树和线性结构到底差在哪里

这是从线性世界过渡到非线性世界时最该建立的认识。

1. 线性结构强调前后关系

例如数组、链表、栈、队列，本质上都只是在一条线上的不同访问方式。

2. 树结构强调层次与分支关系

一个节点可能连接多个下级，形成递归的分层网络。

所以树的价值在于：

  • 它能表达更复杂的关系；
  • 但处理方式也会更依赖递归和结构分析。

六、什么是有序树和无序树

如果一棵树中，节点各子树之间的左右或前后顺序有意义，那么它就是有序树；反之则是无序树。

例如：

  • 文件目录中，子目录顺序未必严格有意义，很多时候更偏无序；
  • 表达式树里，左孩子和右孩子位置不同，顺序就非常重要。

这个区别会在二叉树、堆、Trie 等结构里体现得更明显。

七、为什么说二叉树只是树的一种特殊形式

很多人一学树就立刻进入二叉树，以至于误以为“树就是二叉树”。其实不是。

普通树允许一个节点有任意多个孩子；
二叉树则额外限定：

  • 每个节点最多只有两个孩子；
  • 通常称为左孩子和右孩子；
  • 左右位置有区别。

所以更准确的理解是：

二叉树是树的一种重要特化形式，而不是树的全部。

先把普通树的概念立起来，后面再进入二叉树，会更清楚。

八、树有哪些常见存储方式

树的逻辑结构很直观，但真正实现时，节点关系必须落到具体存储结构上。常见方式主要有下面几类。

1. 双亲表示法

可以用一个数组存所有节点，每个节点额外记录它的双亲下标。

优点：

  • 找父节点方便；
  • 结构较直观。

缺点：

  • 找孩子不够方便；
  • 对树的下行遍历支持一般。
2. 孩子表示法

为每个节点维护一个孩子列表，直接记录它有哪些子节点。

优点：

  • 找孩子方便；
  • 更贴合自顶向下遍历。

缺点：

  • 如果还要频繁找父节点，就需要额外设计。
3. 双亲孩子综合表示法

同时记录父节点信息和孩子列表，适合需要双向导航的场景，但空间开销更高。

4. 孩子兄弟表示法

这是一种非常重要的树存储技巧。它的思想是：

  • 每个节点记录第一个孩子；
  • 同时记录下一个兄弟。

这样一来，任意普通树都能转换成类似“二叉链表”的结构表示。

这一方法很重要，因为它在理论上把“普通树”与“二叉树式表示”连接起来了。

九、为什么孩子兄弟表示法值得重点理解

因为它非常优雅地解决了“普通树孩子数不固定”的问题。

一个节点可能有很多孩子，但通过：

  • 一个指针连到第一个孩子；
  • 一个指针连到下一个兄弟；

就能把整棵树统一地存下来。

这说明数据结构里一个很重要的思想：

逻辑上复杂的关系，往往可以通过合适的指针组织被转换成更易实现的结构。

这和前面学压缩存储时的思路其实是一致的，都是在利用结构特征重新设计存储方式。

十、树的存储和遍历为什么密切相关

因为你怎么存，往往就决定了你怎么访问更自然。

例如：

  • 如果记录了孩子列表，自顶向下遍历会很顺；
  • 如果记录了父节点，向上回溯会更方便；
  • 如果采用孩子兄弟表示法，就能用更统一的链式方式处理整棵树。

也就是说，树的存储不是纯粹的实现细节，它会直接影响后续操作和算法写法。

十一、树在真实开发里常见在哪里

几乎所有有层级概念的系统都会用到树。

例如：

  • 文件系统目录；
  • DOM 树；
  • 组织架构与分类体系；
  • 编译器的抽象语法树；
  • 数据库索引树；
  • 路由和前缀匹配结构；
  • 权限菜单树。

所以树不是课本中的“抽象练习”，而是非常普遍的现实模型。

十二、学习树的入门难点在哪里

1. 术语多，容易混

根、叶子、层次、高度、度、祖先、子孙，这些概念一定要真正建立图像感。

2. 线性思维惯性太强

很多人习惯了数组和链表，第一次看树时还在用“一条线”的方式理解，会很别扭。

3. 递归意识不牢

树的一大本质就是“子树还是树”，如果递归思维不顺，很多树问题会显得很绕。

4. 只学二叉树，不理解普通树

这样会导致视角过窄，看不清更一般的层级结构问题。

总结

树的意义，不只是比线性结构多几个分支，而是它让数据结构正式进入了“层级与递归”的世界。真正值得先建立起来的，是这些核心认识：

  • 树是一种具有根和递归子树结构的非线性数据结构；
  • 它特别适合表达层级关系、从属关系和分支关系；
  • 根、叶子、度、层次、高度、路径等术语是理解树的基础语言；
  • 二叉树只是树的一种特殊形式，不能把树完全等同于二叉树；
  • 双亲表示法、孩子表示法和孩子兄弟表示法，分别反映了不同的存储取舍；
  • 真正学会树，不只是会画结构图，而是能理解逻辑层级关系如何落到具体存储方式上。

把这一篇理解透之后，后面再去学二叉树遍历、BST、AVL、红黑树和 Trie 时，你会更清楚它们不是彼此割裂的新结构，而都是建立在“树的基本语言”之上的不同特化模型。

参考资源：