树是一种非线性数据结构，用于表示具有层次关系的数据
树是一种非线性数据结构，用于表示具有层次关系的数据。根据你提供的内容，以下是对相关概念的梳理与解释：
树的基本概念
- 内部结点：除了叶子结点以外的所有非终端结点，即至少有一个子结点的结点（如示例中的 B、D）。
- 结点层次：从根开始定义，根结点位于第 1 层，其子结点为第 2 层，依此类推，每一层比父层 +1。例如 A 在第 1 层，B、C、D 在第 2 层。
- 树的高度：树中所有结点的最大层次数。若最大层次为 3，则树的高度为 3。
- 有序树与无序树：如果子树之间的顺序有区别（如左、右不同），则称为有序树；否则为无序树。二叉树是典型的有序树。
二叉树的定义
二叉树是一个有限结点集合，满足：- 空树（n = 0）；
- 或由一个根结点和两棵互不相交的左子树和右子树组成，且左右子树也均为二叉树（递归定义）。
二叉树与普通树的核心区别
| 区别点 | 二叉树 | 普通树 |
|---|---|---|
| 子树区分 | 明确区分左、右子树（即使为空） | 不区分左右 |
| 结点最大度数 | 最多有两个孩子（度 ≤ 2） | 度可以大于 2，无限制 |
- 二叉树的性质（节选）
- 性质 1：在第 $ i $ 层上最多有 $ 2^{i-1} $ 个结点（$ i \geq 1 $）。
如第 3 层最多有 $ 2^{2} = 4 $ 个结点。
- 性质 2：高度为 $ k $ 的二叉树最多有 $ 2^k - 1 $ 个结点（$ k \geq 1 $）。
这种情况出现在满二叉树中。
- 性质 1：在第 $ i $ 层上最多有 $ 2^{i-1} $ 个结点（$ i \geq 1 $）。
满二叉树（Full Binary Tree）：
在一棵高度为 $ k $ 的二叉树中，如果所有层次上的结点数都达到最大值，即第 $ i $ 层有 $ 2^{i-1} $ 个结点（$ 1 \leq i \leq k $），且总节点数为 $ 2^k - 1 $，则称为满二叉树。
满二叉树的特点是：每个内部结点都有两个子结点，叶子结点全部集中在最底层。
完全二叉树（Complete Binary Tree）：
对于一棵高度为 $ k $ 的二叉树，如果其前 $ k-1 $ 层构成一个满二叉树，并且第 $ k $ 层的叶子结点从左到右连续分布（没有空缺），则称为完全二叉树。
完全二叉树允许最后一层不满，但必须“从左向右填满”，不能跳过位置。
主要区别：
| 特性 | 满二叉树 | 完全二叉树 |
|---|---|---|
| 定义要求 | 所有层都完全填满 | 前 $ k-1 $ 层满，最后一层左对齐 |
| 结点数量 | 必须是 $ 2^k - 1 $ | 可以是 $ n $，满足 $ 2^{k-1} \leq n < 2^k $ |
| 结构特点 | 每个非叶结点都有两个孩子 | 允许某些非叶结点只有一个孩子（只能是左孩子） |
| 是否一定是完全二叉树 | 是 | 否（例如：只有根和右孩子就不是完全二叉树） |
| 应用场景 | 较少直接应用 | 堆（Heap）、优先队列常用结构 |
✅举例说明：
- 高度为 3 的满二叉树：
A / \ B C / \ / \ D E F G → 共 7 个结点（= 2³ - 1）- 高度为 3 的完全二叉树（非满）：
A / \ B C / \ / D E F → 第三层从左开始连续，G 缺失也合法- 不是完全二叉树的例子：
A / \ B C / \ D E → 中间缺少F或G，右子树出现而左为空，不连续