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

[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 当作右孩子，也不能在有孩子时把当前结点计为叶。

评分要点

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