数据结构：树、森林与二叉树的转换

数据结构：树、森林与二叉树的转换

以二叉链表为媒介，找出对应关系

树用孩子兄弟表示法（左指针指向第一个孩子，右指针指向下一个兄弟）

                                                    原理解释

1将树转化成二叉树：兄弟相连留长子（兄弟间相连，各孩子中只保留长子与双亲的连线）

 

2将二叉树转化成树：左孩右右连双亲（双亲结点a的左孩子b分支下所有的右孩子均与a相连）

                                   去掉原来右孩线（抹去原二叉树中双亲与右孩子的连线）

 

3森林转化为二叉树：树变二叉根相连（每个树都转换成二叉树，将其根连接在一起）

4二叉树转化成森林：去掉全部右孩线，孤立二叉再还原