二叉树与森林的转化
对于一般树，树中孩子的次序并不重要，只要双亲与孩子的关
系正确即可。但在二叉树中，左、右孩子的次序是严格区分的。
所以在讨论二叉树与一般树之间的转换时，为了不引起混淆，
约定按树上现有结点次序进行转换。这里研究二叉树与一般树
之间的转换，可以了解两者之间的内在本质联系，同时在研究
解决一般树的问题时，有时可以将其转换为二叉树问题来解决。
树或森林与二叉树之间有一个自然的一一对应关系。任何一个
森林或一棵树可唯一地对应到一棵二叉树。反之，任何一棵二
叉树也能唯一地对应到一个森林或一棵树。
（1）树、森林到二叉树的转换
1)将树转换为二叉树
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄
弟。按照这种关系很自然地就能将树转换成相应的二叉树。
将一般树转化为二叉树的思路，主要根据树的孩子-兄弟存储方
式而来，步骤是：
① 加线：在各兄弟结点之间用虚线相连。可理解为每个结点的
兄弟指针指向它的一个兄弟。
评论3