树是一种非线性数据结构，用于表示具有层次关系的数据

树是一种非线性数据结构，用于表示具有层次关系的数据。根据你提供的内容，以下是对相关概念的梳理与解释：

1. 树的基本概念

   • 内部结点：除了叶子结点以外的所有非终端结点，即至少有一个子结点的结点（如示例中的 B、D）。
   • 结点层次：从根开始定义，根结点位于第 1 层，其子结点为第 2 层，依此类推，每一层比父层 +1。例如 A 在第 1 层，B、C、D 在第 2 层。
   • 树的高度：树中所有结点的最大层次数。若最大层次为 3，则树的高度为 3。
   • 有序树与无序树：如果子树之间的顺序有区别（如左、右不同），则称为有序树；否则为无序树。二叉树是典型的有序树。

2. 二叉树的定义
   二叉树是一个有限结点集合，满足：

   • 空树（n = 0）；
   • 或由一个根结点和两棵互不相交的左子树和右子树组成，且左右子树也均为二叉树（递归定义）。

3. 二叉树与普通树的核心区别

区别点	二叉树	普通树
子树区分	明确区分左、右子树（即使为空）	不区分左右
结点最大度数	最多有两个孩子（度 ≤ 2）	度可以大于 2，无限制

4. 二叉树的性质（节选）
   • 性质 1：在第 $ i $ 层上最多有 $ 2^{i-1} $ 个结点（$ i \geq 1 $）。

     如第 3 层最多有 $ 2^{2} = 4 $ 个结点。

   • 性质 2：高度为 $ k $ 的二叉树最多有 $ 2^k - 1 $ 个结点（$ k \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，右子树出现而左为空，不连续

---