🏷️ 知识点：Ds.05.04.01

设森林F中有4棵树，第1、2、3、4棵树的结点数分别为a、b、c和d，与森林F对应的二叉树的根结点的左子树上的结点数是（　　）。

A. a B. b+c+d C. a-1 D. a+b+c

[tag_link]

正确答案：C

结论

选项 C 符合本题的树/森林规则。

推导

根的左子树表示第一棵树的全部孩子，除去第一棵树根后剩a-1个结点。

易错点

本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。

设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点数为n，森林F中第一棵树的结点数是（　　）。

A. m-n B. m-n-1 C. n+1 D. 条件不足，无法确定

[tag_link]

正确答案：A

结论

选项 A 符合本题的树/森林规则。

推导

根及其左子树恰为第一棵树，右子树含n个其余结点，故第一棵树大小m-n。

易错点

本题需区分树根与兄弟、左孩子与右兄弟，并避免把空森林套入非空森林计数公式。

设某树的孩子兄弟链表示中共有6个空的左指针域、7个空的右指针域，包括5个结点的左右指针域都为空，则该树中叶结点的个数是（ ）。

A. 7 B. 6 C. 5 D. 不能确定

[tag_link]

正确答案：B

推导

左指针为空等价于孩子兄弟表示中的叶结点；因此叶结点数为6。左右指针都为空的5个结点只是叶结点的子集，不能把更强条件误当作等价条件。

易错点

易错点是把‘左右皆空’的5误作答案，忽略叶结点只要求没有孩子。

在孩子-兄弟表示下，设计算法计算森林叶结点数。给出伪代码、不变量、正确性证明、复杂度和边界情况。

[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。

评分要点

• 写出核心结构对应关系或伪代码
• 给出正确性理由
• 给出复杂度与边界