企业官网建设流程全解析

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

1. 树的基本概念

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

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

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

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

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 $ 层的叶子结点从左到右连续分布（没有空缺），则称为完全二叉树。

完全二叉树允许最后一层不满，但必须“从左向右填满”，不能跳过位置。

主要区别：

✅举例说明：

• 高度为 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，右子树出现而左为空，不连续