树、森林、二叉树的转换

一、将树转为二叉树步骤:

1、加线,将所有兄弟结点连线。

2、去线,对树中的每个结点,只保留其与左孩子的连线,删除其与右孩子之间的连线。

3、层次调整、以树的根结点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明。第一个孩子是二叉树的左孩子,兄弟转过来的孩子是结点的右孩子。

二、将森林转为二叉树步骤:

1、将每棵树转换为二叉树;

2、第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的右孩子,用线连起来。当所有二叉树都连起来后就由森林转为了二叉树。

 三、将二叉树转为树步骤:

1、若某结点的左孩子存在,则将这个左孩子的右孩子以及,右孩子的右孩子、右孩子的右孩子。。。都作为此结点的孩子,将他们用线连起来。

2、去线,删除原二叉树结点与右孩子的连线。

3、层次调整、使之结构分明。

 四、将二叉树转为森林步骤:

判断条件:二叉树的根结点是否有右孩子,有则可以转为森林。

1、从根结点开始,若右孩子存在,则把与右孩子之间的连线删除,再查看分离后的二叉树,若右孩子存在,则连线删除。。。直到所有右孩子连线都删除为止。

2、在将每棵分离后的二叉树转为树即可。

原文地址:https://www.cnblogs.com/dhhu007/p/13201537.html