树/森林的转换

1.树->二叉树

用下面这个二叉树举例:

        A

    /       \

           B         C

       /   |   \      |  \

        D   E   F     G  H

第一步:加线。在所有兄弟结点之间加一条连线后如下图

         A

    /        \

   B   ----   C

/   |   \     |  \

D---E---F     G---H      

第二步:去线:从根结点开始,依次把每个结点除去最左孩子的线保存外,跟其他孩子相连的线全部去掉,如下图

    A

/       

B ---- C

/ |

D---E---F G---H

第三步:层次调整。此时某结点的右兄弟会变成该结点的右孩子。
A

   /

  B

/ \

D C

\ /

E G

 \     \ 

 F    H

2.二叉树->树

用上面刚刚改装成了二叉树的树举例:

    A

   /

  B

/ \

D C

\ /

E G

 \     \ 

 F    H

第一步:加线。从根结点的左节点开始, 如果该结点有左孩子,则将该左孩子的右孩子,该右孩子的右孩子(如果有),一直到没有右孩子为止,与该结点加一条线。如下图,图中红线则为新加的线(A到C,B到E、F,C到H):

       A

   /     |

 /       |

B       |

/ |\ \ |

D | \ C

\ | \ / \

E   \ G    \

    \  \  \   |

        F   H

第二步:去线。删除结点中所有结点与其右孩子的连线。如下图:

       A

   /     |

 /       |

B       |

/ |\ |

D | \ C

|   \   /  \

E   \ G    \

      \       |

        F   H

第三步:层次调整。如下图:

        A

    /       \

  B         C

/ | \ | \

D E F G H

3.森林->二叉树

例如有下列三棵树:

A               E                          G

/ | \ | / \

B C D F H I

                                       /

                                      J

如何转换成二叉树呢?

第一步:首先将每棵树转换为二叉树:

A         E          G

/ / /

B F H

\ / \

 C             J       I

    \

      D

第二步:从第二棵二叉树开始以此把后一颗二叉树的跟结点作为前一棵二叉树的根结点的右孩子,用线连起来。

 A

/ \

B E

\ / \

C F G

 \        /   

   D   H

       /  \

      J    I

4.二叉树->森林

第一步:判断一颗二叉树是否可以转换为森林。如果该二叉树根结点有右孩子,则可以,否则则不行。

第二步:从根结点开始把右孩子,右孩子的右孩子....直到叶结点的连线删除.如下图
A

/

B E

\ /

C F G

 \        /   

   D   H

      /  \

         J    I

第三步:把分离后的二叉树转化为森林:

A                  E                           G

/ | \ | / \

B C D F H I

                         /
                                           J