树、森林与左孩子右兄弟转换

考点定位

本课深化 树、森林与左孩子右兄弟转换。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

森林可用左孩子右兄弟表示转成二叉树：结点左指针指向第一个孩子，右指针指向下一个兄弟。转换保留层次亲属关系但二叉树深度含义改变。

算法推演

从森林各棵树根开始，把同一父结点的孩子按顺序连成右链，再把第一个孩子接到父结点左侧；森林根结点之间也用右链相连。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

任一结点的所有孩子在转换后二叉树中恰好是其左孩子开始的一条右链。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：森林转二叉树后不能继续把右指针解释为原树的右孩子。

随课应用

森林有3棵树，其根依次为A、B、C。转换后根结点之间形成的右兄弟指针共有多少条？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。