5.4.2树、森林与二叉树的转换

知识总览：

树->二叉树的转换：

过程：

           1.先画一个根节点

           2.再按照树的层序依次处理每个节点(从上到下、从左到右的顺序依次处理每个节点)

如下例子：

先画一个根节点A，开始从上到下从左到右处理第一层的A节点，A有B、C孩子，用右指针把B、C连起来，然后把第一个孩子B挂在当前节点A的左指针指向下边，此时C是B的右孩子，B是A的左孩子，再处理第2层B、C，从左到右先处理B，B有3个孩子D、H、F，用右指针依次连起来D-H-F，然后把第一个孩子D放到B的左指针下边成为B的左孩子，H成为D的右孩子，F成为H的右孩子。C同，把第一个孩子放到E的左指针下边成为E的左孩子，再处理第3层D、H、F、E、J、K，先处理D，D没有孩子不处理，再处理H，H有GIL孩子，上同把第一个孩子G放到当前节点H的左指针下边成为H的左孩子，I成为G的右孩子，L成为I的右孩子，再处理第4层GIL，GIL都没有孩子不做处理，转换结束

最后一个图上同：重点是转换二叉树节点的时候各个层级的节点都写谁，好像作为右指针的非第一个节点都比原来同一级的节点下降了一个层次，即原来是兄弟节点的转二叉树的时候被依次当作节点的右指针

 

森林->二叉树的转换：

过程：

          1.先把所有树的根节点画出来，在二叉树中用右指针串起来(因为树只有一个根节点，但是森林有多个根节点，所以森林中各个树的根节点应该是以平级的兄弟关系)

           2.再按照森林的层序依次处理每个节点(从上到下、从左到右的顺序依次处理每个节点)【注意各个树的相同层次看作是森林的层次】

如下例子：

ABD根节点看作是一个层次用右指针串起来。第一层是A、D、G，即从左到右先处理A，A有孩子BC，BC用右指针连起来，然后把第一个孩子B放到A的左指针下面成为B的左孩子，C成为B的右孩子，再处理D，D的孩子是E，直接放到D的左指针下边成为D的左孩子，再处理G，G的孩子是HIJ，用右指针连起来，然后把第一个孩子H放到G的左指针下面成为G的左孩子，I成为H的右孩子，J成为I的右孩子，再处理第2层BCEHIJ，从左到右先是B，B没有孩子下一个，C也没有孩子下一个，E有孩子F直接把F放到E的左指针下边成为E的左孩子，接着是H，H有孩子KL，KL用右指针连起来，然后把第一个孩子K放到H左指针下边成为H的左孩子，L成为K的右孩子，接着是I没有孩子不做处理，J有孩子MNO用右指针连起来，把第一个孩子M放到J的左指针下边成为J的左孩子，N成为M的右孩子，O成为N的右孩子，再处理第3层FKLMNO，先处理F没孩子，KL也没孩子不做处理，再处理M有孩子P放到左指针下边成为P的左孩子，ND没孩子不处理，最后处理第4层P，P没孩子不处理结束。

最后一个图的例子上同：ACFL是根节点作为第一层出现，将ACFL用右指针依次连起来，然后C作为A的右孩子出现，F作为C的右孩子出现，L作为F的右孩子出现，再依次从左到右处理ACFL，先处理A，A有孩子B，放在A的左指针下方，即B作为A的左孩子出现，C有孩子EJ，用右指针连起来，J放在E的右指针下方作为E的右孩子出现，E作为连起来的右指针中第一个孩子作为C的左孩子出现，即放在C的左指针下方，F有孩子K，K作为F的左孩子放在F的左指针下方，L没孩子不做处理，下一层BEJK，处理B，B有孩子D、H，DH用右指针连起来，H是D的右孩子，D作为连起来的第一个孩子称为B的左孩子放在D的左下方，E有孩子I放在E的左下方，JK没孩子不处理，处理下一层DHI，D有孩子G放在D的左指针下方作为左孩子，HI没孩子，结束。

二叉树->树的转换：

过程：

           1.先画出树的根节点

           2.从树的根节点开始，按树的层序恢复每个节点(注意是树的层序，不是二叉树的层序，从上到下、从左到右的顺序)

如下例子：

树的根节点即为二叉树的根节点A，先处理树的第一层A，A有左孩子B，则把和B相连的一串右指针上的节点C依次放到A节点的下方作为A的孩子，此时树有2层，第一层为A，第2层为BC，按照从左到右处理第2层的B，B在二叉树有左孩子D，证明B在树里边有孩子，把和D相连的一串右指针DHF拆开依次放到B的下方作为B的孩子，然后处理C，C有左孩子E，把和C相连的一串右指针EJK拆开依次放到C的下方作为C的孩子，再处理树的第3层DHFEJK，处理D，D没有左孩子证明D在树中没有孩子，再处理H有左孩子G,把一连串右指针GIL拆开放到H的下边，再处理F，F在二叉树中没有左孩子证明F在树中没有孩子不处理，处理E也没有孩子，JK也没有左孩子不处理，再处理树中第4层GIL，这仨都没有左孩子证明在树中都没有孩子不处理，结束。

 

 二叉树->森林的转换：

过程：

           1.先把二叉树的与根节点相连的一连串右指针拆开依次作为森林中各个树的根节点

           2.按照森林的层序恢复每个节点的孩子(注意是森林的层序，不是二叉树的层序，从上到下、从左到右)和二叉树->树同

如下例子：

二叉树的根节点A，和A相连的一连串右指针上的节点ADG拆开依次作为森林中各个树的根节点，目前森林中的第一层ADG，从左到右先处理A，A有左孩子B，把和B相连的一连串右指针上的节点BC拆开依次放在A的下边作为A的孩子，再处理D，D有左孩子E，和E相连的一连串右指针只有E，把E放在D的下方作为D的孩子，再处理G，G有左孩子H，把和H相连的一连串右指针HIJ拆开依次放在G的下方作为G的孩子，处理森林第2层BCEHIJ，从左到右处理B，B没有左子树证明在森林中B没有孩子，再处理C，C也没有，E有左孩子F，与F相连的一连串右指针只有F，则证明E只有孩子F，把F放在E的下边，H有左孩子K，与K相连的一连串右指针节点KL拆开依次放在H的下边作为H的孩子，I没有左孩子不处理，J有左孩子M，与M相连的一连串的右指针节点MNO拆开依次放在J的下方作为G 的孩子，处理森林第3层FKIMNO，FKI没有左孩子不处理，M有左孩子P，与P相连的一连串右孩子没有则M下边只有一个孩子P，把P放在M的下边，NO都没左孩子不处理，处理森林第4层P，P没有孩子不处理，处理结束

知识回顾：

 

。。。。。。。。。