软考必备二叉树核心考点叶子度公式计算题不丢分备考软考软件设计师二叉树是高频考点也是很多人容易丢分的模块——尤其分不清「叶子」「度」的定义记混公式里的1、-1导致计算题频频出错。本文整理二叉树最核心的考点全程大白话结构图极简公式摒弃冗余理论专注软考必考内容收藏起来刷题、考前复盘直接用帮你彻底吃透二叉树计算题一、先搞懂2个核心定义不搞懂公式白记二叉树的所有计算题都围绕「度」和「叶子结点」展开先记住这2个定义再记公式永远不混。1. 结点的「度」一个结点的度就是这个结点拥有的「直接子节点个数」只算直接孩子不算孙子分为3种情况度0没有直接子节点无左、右孩子度1只有1个直接子节点要么只有左要么只有右度2有2个直接子节点左、右孩子都有2. 叶子结点n₀一句话记住叶子结点 度为0的结点就是没有任何子节点、挂在二叉树最底层的结点记为 n₀。3. 度为2的结点n₂有左、右两个直接子节点的结点记为 n₂是二叉树计算题的核心关键。二、一张图看懂「度」和「叶子」直观不混淆用Mermaid绘制一棵标准二叉树对应标注度和叶子一看就懂graph TD A((根结点 度2)) -- B((左孩子 度2)) A -- C((右孩子 度0 叶子)) B -- D((左孩子 度0 叶子)) B -- E((右孩子 度0 叶子))对照图数一数快速巩固度2的结点n₂A、B → 共2个叶子结点n₀C、D、E → 共3个重点观察叶子结点3个 度2结点2个 1这就是二叉树的核心公式记准这个关系计算题就成功了一半。三、软考必考3个公式极简版直接背软考二叉树计算题只考这3个公式记住「什么时候1、什么时候-1」闭眼做对。公式1普通二叉树任意二叉树必考核心铁律永远成立n₀ n₂ 1翻译成人话直接套题已知「叶子结点n₀」求「度2结点n₂」→ 用−1公式n₂ n₀ - 1已知「度2结点n₂」求「叶子结点n₀」→ 用1公式n₀ n₂ 1口诀叶子多一个求二度就减一给二度求叶子就加一不翻倍、不瞎算。举例叶子28个 → 度2结点 28 - 1 27度2结点15个 → 叶子 15 1 16公式2哈夫曼树高频计算题哈夫曼树的特殊性质没有度1的结点只有叶子n₀和度2结点n₂核心公式固定不变总结点数 2 × n₀ - 1口诀哈夫曼无一度总数两倍叶子减一永远×2−1没有1。举例叶子20个 → 总结点数 2×20 - 1 39叶子16个 → 总结点数 2×16 - 1 31公式3完全二叉树给总节点求叶子必考完全二叉树特点除最后一层其余层结点全满最后一层结点靠左排列适合用数组存储。核心公式叶子数 ⌊n÷2⌋ 1⌊⌋表示向下取整简单说就是“总数折半取整数部分再加1”口诀完全二叉求叶子折半取整再加一永远最后1。举例总节点80个 → 叶子 80÷2 1 40 1 41总节点81个 → 叶子 81÷2取整40 1 41总节点61个 → 叶子 61÷2取整30 1 31四、易错点避坑软考高频丢分点❌ 误区1普通二叉树求叶子给度2结点后翻倍正确只加1不翻倍❌ 误区2哈夫曼树总结点用n₀1正确固定2×n₀−1❌ 误区3完全二叉树求叶子折半后不加1正确折半取整后必须1✅ 正确逻辑只记3句口诀不记复杂原理套公式就对五、总结考前快速复盘版1. 定义叶子 度0度2 有左右两个孩子2. 普通二叉树n₀ n₂ 1求二度减1求叶子加13. 哈夫曼树总结点 2×n₀−1固定减14. 完全二叉树叶子 总节点折半取整 1固定加1。把这篇收藏好软考二叉树计算题再也不会因为分不清1、-1丢分刷题时随时对照考前读一遍直接拿捏