【数据结构】树的基本概念与二叉树定义
考点频率：★★★★★（数据结构必考，选择题常考树的基本术语与二叉树性质）
难度：⭐⭐
建议：重点掌握树的基本术语（根/叶子/度/深度），理解二叉树的递归定义，区分满二叉树与完全二叉树
1️⃣ 什么是树？
树（Tree）是一种非线性数据结构，它由nnn（n≥0n \ge 0n≥0）个节点组成，节点之间有层次关系。
递归定义：树是nnn个节点的有限集合。当n=0n=0n=0时称为空树；当n>0n>0n>0时，有且仅有一个根节点（Root），其余节点可分为mmm（m≥0m \ge 0m≥0）个互不相交的有限集合，每个集合本身又是一棵树（称为子树）。
打个比方：树就像公司的组织架构图。总经理（根节点）下面有多个部门经理（子树），每个部门经理下面又有多个员工（子树的子树）。总经理是所有人的“祖先”，最底层的员工是“叶子”。
树的特点：
- 每个节点有零个或多个子节点
- 除根节点外，每个节点有且仅有一个父节点
- 节点之间没有环路（不是图）
2️⃣ 树的基本术语（软考必考）
| 术语 | 含义 | 示例说明 |
|---|---|---|
| 根节点（Root） | 树中唯一没有父节点的节点 | 总经理 |
| 父节点（Parent） | 某节点的直接上层节点 | 部门经理是员工的父节点 |
| 子节点（Child） | 某节点的直接下层节点 | 员工是部门经理的子节点 |
| 兄弟节点（Sibling） | 具有相同父节点的节点 | 同一部门下的员工 |
| 叶子节点（Leaf） | 没有子节点的节点（度为0） | 最底层的员工 |
| 度（Degree） | 节点拥有的子节点个数 | 一个经理管3个人 → 度为3 |
| 树的度 | 树中所有节点的度的最大值 | 全公司最多管5个人 → 树的度为5 |
| 深度（Depth） | 从根节点到某节点的唯一路径长度（根节点深度为0，根节点高度为0） | 第3层员工的深度为3（从0开始）或深度为2（从0开始）？不同教材定义可能不同，考试时以题目定义为准 |
| 高度（Height） | 从某节点到其最远叶子节点的路径长度 | 同上 |
| 层次（Level） | 根节点为第1层，往下递增 | 根节点在第1层 |
| 森林（Forest） | mmm（m≥0m \ge 0m≥0）棵互不相交的树的集合 | 多个组织架构图放一起 |
3️⃣ 二叉树（Binary Tree）
3.1 什么是二叉树？
二叉树是一种特殊的树结构，其特点是：每个节点最多只有两个子节点，分别称为左子节点和右子节点。
正式定义：二叉树是nnn（n≥0n \ge 0n≥0）个节点的有限集合。当n=0n=0n=0时为空二叉树；当n>0n>0n>0时，由一个根节点和两棵互不相交的子树组成，这两棵子树分别称为左子树和右子树，且左子树和右子树本身也是二叉树。
3.2 二叉树与树的区别
| 对比项 | 树（一般） | 二叉树 |
|---|---|---|
| 子节点个数 | 任意（0≤degree≤m0 \le degree \le m0≤degree≤m） | 最多2个（左、右） |
| 子节点顺序 | 无序 | 有序（区分左右） |
| 度数限制 | 无 | 每个节点度≤2\le 2≤2 |
| 空树 | 允许 | 允许 |
| 是否为有序树 | 一般树无序 | 二叉树有序 |
关键点：二叉树是有序树——左子树和右子树不能互换。即使只有一个子节点，也必须明确它是左子节点还是右子节点。
3.3 二叉树的五种基本形态
| 形态 | 描述 | 图示 |
|---|---|---|
| 空二叉树 | 没有节点 | 无 |
| 只有根节点 | 根节点没有子节点 | (A) |
| 只有左子树 | 根节点只有左子节点 | (A( B )) |
| 只有右子树 | 根节点只有右子节点 | (A( C )) |
| 左右子树均有 | 根节点同时有左右子节点 | (A( B )( C )) |
4️⃣ 满二叉树与完全二叉树（重点）
4.1 满二叉树（Full Binary Tree）
定义：一棵高度为hhh的二叉树，如果所有叶子节点都在第hhh层，且每个非叶子节点都有两个子节点，则称为满二叉树。
特点：
- 每一层的节点数都达到最大值
- 第iii层有2i−12^{i-1}2i−1个节点（根节点为第1层）
- 总节点数 =2h−12^h - 12h−1
4.2 完全二叉树（Complete Binary Tree）
定义：一棵高度为hhh的二叉树，如果第111层到第h−1h-1h−1层都是满的，且第hhh层的节点从左到右连续排列（中间没有空缺），则称为完全二叉树。
特点：
- 满二叉树一定是完全二叉树
- 完全二叉树不一定是满二叉树
- 叶子节点只能出现在最后两层
- 可以通过数组顺序存储（无需指针）
4.3 满二叉树 vs 完全二叉树（易混淆）
| 对比项 | 满二叉树 | 完全二叉树 |
|---|---|---|
| 所有叶子节点 | 都在最底层 | 只能在最后两层 |
| 非叶子节点 | 都有两个子节点 | 每个节点度≤2\le 2≤2 |
| 节点数 | 2h−12^h - 12h−1 | 不一定 |
| 顺序存储 | 可以 | 可以（经典考点） |
5️⃣ 经典例题
例题1：一棵高度为hhh的满二叉树，其节点总数为（ ）。
A.2h2^h2h
B.2h−12^h - 12h−1
C.2h+12^h + 12h+1
D.2h+1−12^{h+1} - 12h+1−1
解析：高度为hhh的满二叉树共有2h−12^h - 12h−1个节点。选B。
例题2：下列关于完全二叉树的叙述中，正确的是（ ）。
A. 完全二叉树中所有叶子节点都在同一层
B. 完全二叉树可以用数组顺序存储
C. 完全二叉树就是满二叉树
D. 完全二叉树中每个节点的度都为2
解析：A错误——完全二叉树的叶子节点可以在最后两层；B正确——完全二叉树是顺序存储的经典应用；C错误——完全二叉树不一定是满二叉树；D错误——叶子节点度为0。选B。
6️⃣ 记忆口诀
树是非线性结构，根节点唯一无父。
叶子度为0，树的度看最大。
二叉树最多两个子，左右有序不混淆。
满二叉树全满，完全二叉树连续填。
7️⃣ 小测验（评论区对答案）
一棵高度为hhh的完全二叉树，其节点数最多为（ ）。
A.2h2^h2h
B.2h−12^h - 12h−1
C.2h+1−12^{h+1} - 12h+1−1
D.2h+12^{h} + 12h+1
🔔本专栏日更，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #树 #二叉树 #满二叉树 #完全二叉树 #数据结构 #软考备考