5.4.2 树、森林与二叉树转换

树转二叉树采用左孩子右兄弟：每结点最左孩子成为左孩子，其余兄弟沿右链连接。森林中各棵树的根互为兄弟，第一棵树根作为二叉树根，其余根沿右链。逆转换按同一语义还原。

手工推演

森林含 T1 根 A（孩子 B、C）和 T2 根 D（孩子 E）。二叉表示：A.left=B，B.right=C，A.right=D，D.left=E。A.right 代表下一棵树根，不代表原森林中 A 的孩子。

结构与代码

转换保持结点数但改变边的解释。普通树中一个结点的所有孩子，转后成为“左孩子起始的一条右兄弟链”。画图时先连兄弟水平线，再只保留最左孩子竖线，最后旋转理解。

错解反馈

把所有孩子都连成左链；忘记森林根之间的右链；转换后仍按二叉树左右孩子解释原树度。

迁移练习

将括号树 A(B(E,F),C,D) 转成左孩子右兄弟表示，写 A、B、E 的两指针。答案 A.left=B；B.left=E,B.right=C；E.right=F。