📖 定长子网划分和变长子网划分的二叉树解法

🎯 课程摘要：本节介绍一种基于二叉树的子网划分(subnetting)解题方法。基于 CIDR 的子网划分分为定长子网划分（统一子网掩码，各子网前缀相同）和变长子网划分（不同子网掩码，各子网前缀可不同）。二叉树解法将地址块表示为树根，每次增加一位网络前缀就将节点分裂为两个子块，通过在树上选取节点来分配子网。配套"阀门堵水"法可快速判断变长子网划分方案是否可行。本节包含两道 408 考研真题实战。

📝 详细笔记

1. 基本概念

前置知识：IPv4 地址的无分类编制(CIDR)方法，以及定长/变长子网划分的一般方法。

2. 二叉树解法基本原理

核心思想：用一个节点表示一个 CIDR 地址块，每次将网络前缀增加一位，就把该地址块均分为两个子块（二叉树分裂）。

• 增加的这一位取值为 0 → 左子块
• 增加的这一位取值为 1 → 右子块
• 每分裂一次，子块地址数减半

地址数量计算：地址块前缀为 /n，则包含 2^(32−n) 个地址。

3. 定长子网划分的二叉树解法

3.1 例题：将 /24 地址块均分为 8 个子网

已知：某 CIDR 地址块网络前缀为 24 比特（/24），包含 2^(32−24) = 256 个地址。

划分过程：

要均分为 8 个子网，需增加 3 位，网络前缀变为 /27，主机号由 8 比特缩减为 5 比特。

二叉树结构：

选取第 3 层（/27）的全部 8 个叶子节点，分配给 8 个子网。

求各子网的网络地址（各子块第一个地址）：

• 原地址块：前 24 比特为网络前缀，后 8 比特为主机号
• 均分为 8 个子网 → 主机号中取 3 比特作为网络前缀，构成 27 比特网络前缀，剩余 5 比特为主机号
• 每个子块的第一个地址 = 该子块的 3 比特新增前缀 + 5 比特主机号全取 0

⚠️ 重点/考点：每个子块的第一个地址作为该子网的网络地址，写成点分十进制形式并在其后添加网络前缀长度（如 /27），用来表示该地址块自身。

3.2 练习：将 /24 地址块均分为 4 个子网

增加 2 位，网络前缀变为 /26，每个子块 64 个地址。

4. 变长子网划分的二叉树解法

4.1 例题：将 /24 地址块划分为 5 个子网

由于 5 不是 2 的整数次幂，属于变长子网划分。

步骤一：画出子块划分二叉树

步骤二：在二叉树中选取 5 个节点（子块）分配给 5 个子网

方案一（三个 /26 + 两个 /27）：

选取 00/26、01/26、10/26、110/27、111/27

• 三个 /26 子块各 64 个地址：64 × 3 = 192
• 两个 /27 子块各 32 个地址：32 × 2 = 64
• 合计：192 + 64 = 256 ✅ 可行

方案二（一个 /25 + 四个 /27）：

选取 0/25、100/27、101/27、110/27、111/27

• 一个 /25 子块 128 个地址
• 四个 /27 子块各 32 个地址：32 × 4 = 128
• 合计：128 + 128 = 256 ✅ 可行

4.2 "阀门堵水"法——选取节点的判定方法

这是一种形象易记的方法，用于判断变长子网划分方案是否可行：

类比：在树根处打开水龙头，要求在各分支的末端不能有水流出（即所有地址都被分配，无剩余）。

规则：

1. 封堵一个节点 = 选取该节点作为一个子网（水不会继续流向该节点下方）
2. 各分支末端不能有水流出 = 所有地址必须被恰好分配完，不能有剩余
3. 同一分支中只能选取一个节点进行封堵 = 不能重复封堵（选取的子网不能重叠）

判定方法：

• 在二叉树上选取若干节点进行"封堵"
• 检查各分支末端是否都不漏水（地址全部分配完）
• 检查是否有重复封堵（同一分支选了两个节点 → 不允许）
• 封堵的节点数 = 子网数，须满足题目要求

反例：若在某两个节点所在分支上进行了重复封堵，则该方案不可行（子网地址重叠）。

⚠️ 重点/考点：同一分支不能重复封堵是关键约束——如果已经选了上层节点（如 0/25），就不能再选其下层的子节点（如 00/26），因为后者包含在前者之中，会导致地址重叠。

5. 408 考研真题实战

5.1 真题一：将某 IP 网络划分为 3 个子网（答案：B）

题干：给定子网简记为 10/26，题目要求将某个 IP 网络（/24，256 个地址）划分为 3 个子网。

各选项：

• 选项 A：（被排除）
• 选项 B：00/26
• 选项 C：11/26
• 选项 D：110/27

分析：为简化，仅写出第四字节左起相关比特。

判定各选项：

• 选项 C（11/26）：题干 10/26 已封堵 + 11/26 封堵 → 右半 1/25 全部覆盖。左半 0/25 漏水 → 封堵 0/25 一个节点即可。共 3 个封堵（10/26、11/26、0/25），无重复，无漏水。✅ 可行 → C 排除

• 选项 B（00/26）：题干 10/26 已封堵。左半 0/25 漏水于 00/26 和 01/26；右半 1/25 漏水于 11/26。

  • 封堵 00/26（选项 B）→ 仍漏水于 01/26 和 11/26
  • 封堵 01/26 → 仍漏水于 11/26，需再封堵 → 共 4 个
  • 封堵 11/26 → 仍漏水于 01/26，需再封堵 → 共 4 个
  • 能否封堵 0/25？不行！0/25 包含已封堵的 00/26 → 重复封堵
  • 能否封堵 1/25？不行！1/25 包含已封堵的 10/26 → 重复封堵
  • 无论怎样都需 4 个子网，不满足"恰好 3 个" ❌ 不可行 → B 是答案

• 选项 D（110/27）：由于题目未具体给定 IP 网络的地址块大小，该选项也可排除。

答案：B。选取 00/26 后无法恰好用 3 个子网分配完所有地址，必然需要 4 个。

5.2 真题二：将地址块划分为 5 个子网，使至少一个子网的 IP 地址数最小（答案：B）

题干：给定地址块网络前缀 /20，包含 2^(32−20) = 4096 个地址。要求划分为 5 个子网（不多不少），且其中至少一个子网包含的 IP 地址数量最小。

方法：类比"切蛋糕"——每次切剩余的一半，直到蛋糕份数满足需求。

划分过程：

二叉树路径：

验证：2048 + 1024 + 512 + 256 + 256 = 4096 ✅，共 5 个子网 ✅

最小子网：包含 256 个地址（/24）

• 去掉主机号全 0 的网络地址和主机号全 1 的广播地址
• 可分配给主机或路由器接口的地址数 = 256 − 2 = 254 个

⚠️ 重点/考点：要让最小子网尽可能小，采用贪心策略——每次取走当前最大的一块，将剩余部分继续均分，直到满足子网数量要求。"切蛋糕"每次切剩余的一半。

6. 二叉树解法总结

"阀门堵水"法核心规则：

• 各分支末端不能漏水（地址全部分配完）
• 同一分支不能重复封堵（子网不能重叠）
• 封堵节点数 = 子网数

💡 核心总结

• 二叉树解法将地址块视作树根，每增加一位前缀就分裂为两个子块，直观展示子网划分过程
• 定长子网划分：选同一层全部叶子节点，子网数必须是 2 的整数次幂
• 变长子网划分：可在不同层选取节点，用"阀门堵水"法判定可行性——不漏水且不重复封堵
• 求网络地址：新增前缀位 + 主机号全 0 → 点分十进制 + 前缀长度
• 切蛋糕策略：要求最小子网时，每次取走最大块，剩余继续均分
• 二叉树解法比基础解法更快，适合考试中快速判定

❓ 课后思考 / 经典考题

1. 定长子网划分和变长子网划分的区别是什么？各自对 IP 地址利用率有何影响？
2. 将 /24 地址块均分为 8 个子网时，每个子网的网络前缀是多少？包含多少个地址？可分配给主机的地址数是多少？
3. 用"阀门堵水"法判断：从 /24 地址块中选取 0/25、10/26、110/27、111/27 共 4 个子网是否可行？为什么？
4. 408 真题一中，为什么选取 00/26 后无法恰好用 3 个子网分配完所有地址？尝试列出所有可能的组合。
5. 408 真题二中，若要求最小子网包含的地址数尽可能小，为什么要采用"每次取最大块"的贪心策略？如果改为"每次取最小块"会怎样？
6. "同一分支不能重复封堵"对应子网划分中的什么原则？如果违反会导致什么后果？