🏷️ 知识点：Ds.05.04.03
森林T=(T₁,T₂,…,Tₘ)转化为二叉树BT的过程为：若m=0，则BT为空，若m≠0，则（ ）。
A. 将中间子树的根作为BT的根 B. 将子树T₁的根作为BT的根；将T₁的子树森林转换成BT的左子树；将(T₂,…,Tₘ)转换成BT的右子树 C. 将子树T₁的根作为BT的根并分别转换左右子树 D. 将森林T的根作为BT的根再转换
[tag_link]
正确答案：B
结论
选项 B 符合本题的树/森林规则。
推导
递归取T₁根为BT根，T₁子树森林转左子树，其余T₂..Tₘ转右子树。
易错点
本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。
设F是一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
A. n-1 B. n C. n+1 D. n+2
[tag_link]
正确答案：C
结论
选项 C 符合本题的树/森林规则。
推导
仅对非空森林计数：每个非终端结点最后孩子的right为空，共n个；最后一棵树根再贡献1个且不重叠，合计n+1；空森林结果为0。
易错点
本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。
若T₁是由有序树T转换而来的二叉树，则T中结点的后根序列就是T₁中结点的（ ）。
A. 先序 B. 中序 C. 后序 D. 层序
[tag_link]
正确答案：B
推导
孩子-兄弟二叉树转换保持原树后根遍历与二叉树中序遍历一致，因此答案为中序。
易错点
不要把先根/后根与二叉树先序/后序机械对应。
某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括（ ）棵树。
A. 1 B. 2 C. 3 D. 4
[tag_link]
正确答案：C
推导
后序末项A为根；结合中序递归重建，沿根的right链A→C→F，共有3个森林根，故为3棵树。
易错点
需先用后序确定根，再用中序划分左右子树，不能只数叶子或层数。
给定一棵树的先根遍历序列和后根遍历序列，能否唯一确定一棵树？若能，请举例说明；若不能，请给出反例。
[tag_link]
参考答案
有序树且结点标识互异时，孩子兄弟二叉树的先序等于原树先根，中序等于原树后根；先序与中序可唯一重建二叉树，故能唯一确定。若是一般二叉树只给先序与后序，或允许重复标识，则不成立：例如只有 A、B 两个结点时，B 作 A 的左孩子或右孩子，先序均为 AB、后序均为 BA。
推导过程
孩子兄弟转换把第一个孩子连为 left、下一个兄弟连为 right；递归展开可得先序访问根及孩子链、后序访问孩子后根与兄弟链，恰对应原树先根/后根。互异标识保证中序根划分唯一。
复杂度与边界
时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。
易错点
不要把一般二叉树的先序+后序误当作总能唯一重建；本题能唯一确定依赖转换后得到的是先序+中序且结点标识互异。
评分要点
- 写出核心结构对应关系或伪代码
- 给出正确性理由
- 给出复杂度与边界
给定二叉树先序序列 ABDEHCFIMGJKL、中序序列 DBHEAIMFCGKLJ，完整重建二叉树并转换为森林，写出二叉树边、森林父子边以及先根和后根序列。
[tag_link]
参考答案
二叉树边为 A-L-B、A-R-C、B-L-D、B-R-E、E-L-H、C-L-F、C-R-G、F-L-I、I-R-M、G-R-J、J-L-K、K-R-L。转换森林的根链为 A→C→G→J，父子边为 A-B、A-E、B-D、E-H、C-F、F-I、F-M、J-K、J-L；森林先根为 ABDEHCFIMGJKL，后根为 DBHEAIMFCGKLJ。
推导过程
先序首项 A 为根；在中序 DBHE|A|IMFCGKLJ 中划分左右子树，递归得到 B/E/H 与 C/F/G/J，再按孩子兄弟规则将右链解释为兄弟链。
复杂度与边界
时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。
易错点
右指针在孩子兄弟表示中是兄弟而非右孩子；森林根链也不能误报成同一棵树的父子链。
评分要点
- 写出核心结构对应关系或伪代码
- 给出正确性理由
- 给出复杂度与边界
在孩子-兄弟表示下，设计算法计算森林叶结点数。给出伪代码、不变量、正确性证明、复杂度和边界情况。
[tag_link]
参考答案
Leaves(t): 空返回0；若 firstchild(t)为空，返回 1+Leaves(nextsibling(t))；否则返回 Leaves(firstchild(t))+Leaves(nextsibling(t))。空森林为0，单点为1。
推导过程
不变量：调用 Leaves(t) 返回从 t 开始的兄弟链森林叶数。无孩子时 t 是一棵树的叶，递归计入1并继续兄弟；有孩子时叶子全在孩子森林与兄弟森林，二者不交且完备。每结点至多访问常数次，时间 O(n)，递归栈 O(h_cs)，最坏 O(n)。
复杂度与边界
时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。
易错点
不能把 nextsibling 当作右孩子，也不能在有孩子时把当前结点计为叶。
评分要点
- 写出核心结构对应关系或伪代码
- 给出正确性理由
- 给出复杂度与边界
以孩子兄弟链表为存储结构，请设计递归算法求树的深度。
[tag_link]
参考答案
对单棵树根调用：Depth(t)=0（t为空），否则 max(1+Depth(firstchild(t)), Depth(nextsibling(t)))；兄弟分支不增加层数。空森林深度0，单点树深度1（若采用边高则相应整体减1）。
推导过程
递归不变量：Depth(t) 是 t 所在兄弟链森林中，从该森林根到最深结点的层数。首孩子路径增加一层，兄弟路径仍在同层取最大，故归纳成立。每结点访问一次，时间 O(n)，栈 O(h_cs)，最坏 O(n)。
复杂度与边界
时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。
易错点
必须明确调用语义（单棵树根或森林链）和深度按层/按边的约定；不能让兄弟递归加1。
评分要点
- 写出核心结构对应关系或伪代码
- 给出正确性理由
- 给出复杂度与边界