应急食品——树

忘忧兽

2025-09-20 22:38:58

发布于：江西

7阅读

0回复

0点赞

树核心知识点与解题技巧（初一级别 / CSP 备考适用）

在 CSP 初赛（笔试）中，树的考查聚焦于概念定义、性质推导、基础计算，不涉及复杂代码实现，核心是理解树的本质特征并能灵活运用公式解决问题。以下是针对初一级别备考的核心知识点与解题技巧，完全匹配初赛考查范围：

树是一种无环的连通无向图，是图论中最简单的连通结构，所有概念需精准记忆，避免与 “图”“森林” 混淆：

概念	定义（初赛核心考点）
树(Tree)	1. 连通（任意两点有且只有一条路径）；2. 无环；3. 边数 = 节点数 - 1（三个条件等价，初赛常用来判断 “是否为树”）。
森林(Forest)	由多棵互不连通的树组成（无环，但不连通）；边数 = 总节点数 - 树的棵数。
节点	- 根节点：有根树中唯一 “顶端” 节点（如二叉树的根）；- 叶子节点：度数为 1 的节点（无子节点）；- 父 / 子节点：有根树中，连接的上下层节点（如二叉树中，一个节点的直接下层是子节点）。
二叉树	每个节点最多有 2 个子节点（左子节点、右子节点），是初赛树类问题的高频载体。
特殊二叉树	- 满二叉树：除叶子外，所有节点都有 2 个子节点（叶子在同一层）；- 完全二叉树：按 “层序遍历” 顺序编号（1~n），所有节点编号与满二叉树完全对应（叶子只可能在最后两层，且最后一层叶子靠左）。

初赛中 80% 的树相关题目围绕以下性质展开，需理解推导逻辑 + 牢记公式，避免死记硬背：

性质 1：边数与节点数的关系

对任意一棵树，若节点数为 n，边数为 m，则 m = n - 1（树的本质特征，初赛常用来 “反向计算节点数” 或 “判断是否为树”）。

例：一棵有 10 条边的树，节点数是多少？答：10 + 1 = 11。
性质 2：度数和与边数的关系

所有节点的度数之和 = 2 × 边数（图的通用性质，结合树的 “边数 = n-1”，可推导树的度数关系）。

例：一棵有 n 个节点的树，所有节点度数之和是多少？答：2 (n-1)。
性质 3：叶子节点数的计算（高频考点）

若树中只有 “叶子节点（度数 1）” 和 “度数≥2 的节点”，设叶子数为 L，度数≥2 的节点数为 k，则：

由度数和公式：L×1 + （度数≥2节点的总度数） = 2(n-1)，且 n = L + k，代入可简化为：

L = （度数≥2 节点的总度数） - 2k + 2

最常见场景：树中只有叶子（度数 1）和度数为 2 的节点（如一条 “链”），此时 “度数≥2 节点的总度数 = 2k”，代入得 L = 2（链的两端是叶子，中间节点度数 2，符合常识）。

例：一棵树上有 3 个度数为 3 的节点，其余都是叶子，求叶子数？答：总度数 = 3×3 + L×1 = 9 + L；边数 =(3+L)-1 = L+2；度数和 = 2× 边数 → 9+L=2 (L+2) → L=5。

二叉树的性质围绕 “节点数、层数、叶子数” 展开，尤其是完全二叉树的计算，几乎每年初赛都会涉及：

性质	内容（初赛必考）
性质 1：第 k 层节点数上限	若二叉树的根节点在第 1 层（初赛默认层数从 1 开始），则第 k 层最多有 $2^{k-1}$ 个节点。
性质 2：深度为 h 的节点数上限	深度（最大层数）为 h 的二叉树，最多有 $2^{h - 1}$ 个节点（即满二叉树的节点数）。
性质 3：完全二叉树的节点编号	对 n 个节点的完全二叉树，按层序编号（1~n），对任意编号为 i 的节点：- 左子节点编号：2i（若 2i ≤n，否则无左子节点）；- 右子节点编号：2i+1（若 2i+1 ≤n，否则无右子节点）；- 父节点编号：i//2（i>1 时，整除）。
性质 4：完全二叉树的叶子数	对 n 个节点的完全二叉树，叶子节点数为 n//2 或 (n+1)//2（两种情况等价，因整数除法特性）：- 若 n 为偶数：叶子数 = n/2；- 若 n 为奇数：叶子数 = (n+1)/2。
性质 5：完全二叉树的深度	深度 h = floor(log₂n) + 1（floor 表示 “向下取整”，初赛可通过 “ $2^{h-1}$ $≤n$ $<2^h$ ” 反向推导 h）。

初赛中树的题目以 “选择题”“填空题” 为主，题型固定，掌握技巧可快速得分：

解题技巧：利用树的三个等价条件，满足任意一个即可判断：

解题技巧：分两步：

确定 “非叶子节点的度数总和”（如 “2 个度数 3 的节点，1 个度数 4 的节点”，总和 = 2×3+1×4=10）；
代入公式：叶子数 L = 非叶子节点总度数 - 2× 非叶子节点数 + 2（推导自 “度数和 = 2× 边数” 和 “边数 = 总节点数 - 1”）。

例：一棵树上有 1 个度数为 4 的节点，2 个度数为 3 的节点，其余为叶子，求叶子数？答：非叶子总度数 = 4+2×3=10；非叶子节点数 = 3；L=10 - 2×3 +2=6。

解题技巧：牢记 “编号规则” 和 “叶子数公式”，优先用 “编号” 推导：

求某节点的子 / 父节点：直接用 “左子 = 2i，右子 = 2i+1，父 = i//2”（注意判断 “是否存在子节点”，即编号≤n）；
求叶子数：直接用 “n//2”（无论 n 奇偶，结果正确）；
求深度：找到最大的 h 使得 2^(h-1) ≤n <2^h（如 n=10，2^{3=8≤10<16=2}4，深度 h=4）。

例 1：完全二叉树有 15 个节点，求叶子数？答：15//2=7？错！15 是满二叉树（2^4-1=15），叶子数 = 8，此时用 “(15+1)//2=8” 更准确，本质是 “n 为奇数时叶子数 =(n+1)/2”。

例 2：完全二叉树中，编号为 6 的节点的左子节点编号是多少？答：2×6=12（若总节点数≥12，则存在，否则不存在）。

解题技巧：利用森林的核心公式：边数 m = 总节点数 n - 树的棵数 k（森林是多棵树，每棵树满足 $m_i = n_i -1$ ，总和即 $m=Σm_i=Σn_i -Σ1 =n - k$ ）。

例：一个森林有 20 个节点、15 条边，求森林中有几棵树？答：k = n -m =20-15=5。

层数起点：初赛中二叉树的 “层数” 默认从 1 开始（根为第 1 层），若按 “第 0 层” 计算会出错（如第 k 层节点数会变成 $2^k$ ，而非 $2^{k-1}$ ）；
完全二叉树 vs 满二叉树：满二叉树是特殊的完全二叉树，但完全二叉树不一定是满的（最后一层叶子靠左），计算叶子数时别混淆；
度数的定义：无向树中 “节点的度数” 是 “连接的边数”（根节点的度数也按边数算，如根有 2 个子节点，度数为 2），别误将 “子节点数” 当作 “度数”（有根树中父 / 子是相对概念，度数是图的绝对概念）。