15.1.3 树的性质
已知 ，求叶数？
考研计算机 408 全程课 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 章9第 2 章8第 3 章14第 4 章20第 5 章7第 6 章21第 7 章20第 8 章21第 9 章25第 10 章9第 11 章8第 12 章12第 13 章16第 14 章23第 15 章15第 16 章21第 17 章9第 18 章10第 19 章8第 20 章1第 21 章4第 22 章4第 23 章6第 24 章2第 25 章1第 26 章3第 27 章14第 28 章14第 29 章18第 30 章8第 31 章19第 32 章13第 33 章16第 34 章3第 35 章6第 36 章8第 37 章8第 38 章9第 39 章7第 40 章8第 41 章8第 42 章19第 43 章19第 44 章9第 45 章10第 46 章4第 47 章4第 48 章4第 49 章4第 50 章16第 51 章20第 52 章16第 53 章12第 54 章14第 55 章25第 56 章14第 57 章10第 58 章4第 59 章6
第 1 页 · 正面（题目）
25.1 树的定义和基本术语、树的性质·选择题讲评
度不超过 3、高度 4 的树最多多少结点？
35.1 树的定义和基本术语、树的性质·综合题讲评
构造一棵满足 的树并检查公式？
45.2.1 二叉树的定义和基本术语、二叉树的性质
完全二叉树有 100 个结点，叶可能从哪个编号开始？最后一个非叶为 ，所以 51 至 100 都是叶。独立验收：能用编号验证孩子与双亲。
55.2.2 二叉树的存储结构
7 个结点的二叉链表有多少空指针？
65.2 二叉树的定义和基本术语、二叉树的性质·选择题讲评
完全树结点 37，编号 18 的孩子有哪些？有左孩子36、右孩子37。验收要求再写出其双亲编号9。
75.2 二叉树的定义和基本术语、二叉树的性质·综合题讲评
完全树有 31 与 32 个结点时分别求 ？
85.3.1 二叉树的先中后序遍历、二叉树的层次遍历、由遍历序列构造二叉树
先序 12435、中序 42135，重建并写后序？
95.3.2 线索二叉树的概念、二叉树的线索化、在线索二叉树中找前驱后继
给中序序列 DBEAC，写 E、A 的前后继。E 前驱 B、后继 A；A 前驱 E、后继 C。验收要求区分哪条是线索、哪条是真孩子边。
105.3 二叉树的先中后序遍历、二叉树的层次遍历·选择题讲评
已知中序 DBEAFC、先序 ABDECF，根的左右子树各含几个结点？
第 1 页 · 背面（答案）
答案 。验收要求同时解释何时能取到等号。
答案 ，与 无关。独立验收：能从边的两种计数现场推导，而非背结果。
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
答案满足 ；独立验收还需画出连通、无环且度数吻合的具体树。
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
答案 8。独立验收：能用指针总数减实际边数推导，并比较完全树与斜树的空间。
答案 42531。独立验收：每次递归都标出根、左右区间。
答案 31：16,0,15；32：16,1,15。独立验收：用编号和公式双重验证。
答案左3、右2。验收要求说明来自中序分割。
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
第 2 页 · 正面（题目）
115.3 二叉树的先中后序遍历、二叉树的层次遍历·综合题讲评
为空、单结点、左斜、只有右孩子四棵树分别实跑中序。独立验收：每一步写 cur、栈、输出，并说明循环不变量。
125.4.1 树的存储结构
为部门树“公司→研发、销售；研发→前端、后端”写出所有 firstChild/nextSibling 指针。验收要求从表示还原原树。
135.4.2 树、森林与二叉树的转换
将括号树 A(B(E,F),C,D) 转成左孩子右兄弟表示，写 A、B、E 的两指针？
145.4.3 树和森林的遍历
森林两棵树分别为 A(B,C) 与 D(E)，写先根和后根？
155.4 树的存储结构、树、森林与二叉树的转换·选择题讲评
二叉表示根 A 的右孩子 D，原结构意味着什么？若来自森林，D 是下一棵树的根。验收要求说明转换背景。
165.4 树的存储结构、树、森林与二叉树的转换·综合题讲评
自行构造一棵度为4的树，转换、恢复，并核对每个结点孩子列表和两组遍历对应。
175.5.1 哈夫曼树
权值 1、2、4、8 求 WPL。合并3、再7、再15，总和25。独立验收：画树并用叶深加权再次核对。
185.5.2 并查集、并查集的进一步优化
处理边 (0,1),(1,2),(3,4),(2,4)，最终有几个集合（含0..4）？
195.5 哈夫曼树、并查集·选择题讲评
6 个叶的哈夫曼树总结点数是多少？
205.5 哈夫曼树、并查集·综合题讲评
对边 01:1、12:2、02:2、23:5 手推 Kruskal？
第 2 页 · 背面（答案）
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
答案先根 A-B-C-D-E；后根 B-C-A-E-D。
答案 A.left=B；B.left=E,B.right=C；E.right=F。
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
答案1。独立验收：每次合并后画父数组并实跑连通性。
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。
答案先01，再12或02之一，跳过另一条成环边，再23，总权8。独立验收：每步记录集合划分和选择理由。
答案11。验收要求由 推导。
第 3 页 · 正面（题目）
215.1.1 树的定义和基本术语
画一棵 8 结点、树度为 3、高度为 4 的树，标出每个结点的度、深度和高度。独立验收：能由任意树图准确回答根、叶、兄弟、祖先、路径与边数。
第 3 页 · 背面（答案）
按正文方法完成结构图或逐步状态，并检查所有边界与不变量。