企业官网建设流程全解析

一、二叉树

二叉树是每个节点最多有两个子节点的树结构，这两个子节点分别称为左子节点和右子节点。其核心特征如下：

• 度不超过 2：二叉树中每个节点的度（子节点个数）最大为 2，即度可以取 0、1 或 2。
• 有序树：节点的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

例如下面这棵二叉树：节点 1 为根节点，2 和 3 分别是它的左右子节点，每个节点的子节点都有明确的左右位置：

1 / \ 2 3 / \ \ 4 5 6

二叉树的重要性质

以下性质在面试和考试中经常出现，需要熟练掌握：

• 第 i 层最多节点数：二叉树的第 i 层最多有2^(i-1)个节点（i ≥ 1）。
• 深度为 k 的二叉树最多节点数：深度为 k 的二叉树最多有2^k - 1个节点（k ≥ 1）。
• 叶子节点与度为 2 的节点关系：对任意非空二叉树，若叶子节点数为 n0，度为 2 的节点数为 n2，则n0 = n2 + 1。
• 节点总数与度关系：若二叉树节点总数为 n，度为 0、1、2 的节点数分别为 n0、n1、n2，则 n = n0 + n1 + n2，且 n = n1 + 2×n2 + 1。

易错点提示：性质 3 中「叶子节点数 = 度为 2 的节点数 + 1」是常考结论，推导依据是「总边数 = 节点数 - 1」与「总边数 = n1 + 2×n2」两个等式联立。

二、二叉树的遍历

遍历是按照某种顺序访问二叉树中的每个节点，且每个节点只访问一次。下面以这棵二叉树为例：

a / \ b c / \ \ d e f / g

1. 先序遍历

访问顺序：根节点 → 左子树 → 右子树。

遍历结果：a b d e g c f，图中括号里的数字表示访问先后顺序：

a(1) / \ b(2) c(6) / \ \ d(3) e(4) f(7) / g(5)

2. 中序遍历

访问顺序：左子树 → 根节点 → 右子树。

遍历结果：d b g e a c f。

注:根节点左边是左子树的遍历结果，右边是右子树的遍历结果。

a(5) / \ b(2) c(6) / \ \ d(1) e(4) f(7) / g(3)

3. 后序遍历

访问顺序：左子树 → 右子树 → 根节点。

遍历结果：d g e b f c a。

注:1.第一个节点不一定是左子树节点，但最后一个一定是根节点
后序遍历交换左右子树后，再逆序结果就是前序遍历。

a(7) / \ b(4) c(6) / \ \ d(1) e(3) f(5) / g(2)

4. 层序遍历

访问顺序：一层一层，从上到下，从左往右。

遍历结果：a b c d e f g。

a(1) / \ b(2) c(3) / \ \ d(4) e(5) f(6) / g(7)

三、两种特殊二叉树

1. 满二叉树

其每个节点都为最大值，如果其层数为 k，那结点总数是 (2^k) - 1。

例如层数 k=3 时，结点总数是 2^3 - 1 = 7，图形如下：

1 / \ 2 3 / \ / \ 4 5 6 7

2. 完全二叉树

把若干元素一层层从左往右填充，过程中没有缺口就是完全二叉树。

例如下面这棵完全二叉树，节点从左往右连续填充，没有空缺：

1 / \ 2 3 / \ / 4 5 6