首页 > 代码库 > 多叉树转换二叉树

多叉树转换二叉树

多叉转二叉,前提是我们仍要把树的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。

于是,就出现了网上广泛介绍的方法,当一个节点是另一个节点的孩子时,就放在父亲节点的左孩子上,是兄弟,就该放在右孩子上,也就是所谓的“左儿子,右兄弟”。

技术分享

当然多叉转二叉的形式不止一种,上图是其中的一种。

因为2,3,4都是1的孩子,所以都位于1的左子树里。至于谁跟1相连,这个顺序不唯一,但不影响,看是如何读取吧。

然后对于2,3,4互为兄弟,所以都放在各自的右子树里。

7是4的孩子,所以7就放在4的左子树上。

5,6是二的孩子,就放在2的左子树上。

5,6互为兄弟,就放到6(或5)的右子树上。

 

实现方法

 

一、

1.读入a,b表示a是b的孩子

2.如果b的左孩子为空,那么a就放在b的左孩子,否则循环左孩子直到该孩子的右孩子为空为止,放到该孩子的右孩子上。

技术分享
 1 for (int i=1;i<=m;i++)
 2 {
 3   cin>>a>>b     //a是b的孩子
 4   if (tree[b].l==0) tree[b].l=a;
 5   else {
 6             int tmp=tree[b].l;
 7             while (tmp!=0) tmp=tree[tmp].r;
 8             tree[tmp].r=a;
 9           }
10 }
代码

 

 二、

当孩子过多的时候,会发现循环可能会过慢,降低效率。

我们还可以用类似储存链式前向星的方法,让父亲的左孩子为读入的孩子,然后这个孩子的右孩子是父亲的之前第一个左孩子。

如:

技术分享

我们现在读入的是4是1的孩子,按照方法一的话最终是这样的

技术分享

很明显当右孩子过多的时候,循环可能会过久,方法二减小循环就是这样做的:

读入4是1的孩子,那么

技术分享

把1的左孩子给4的右孩子

 技术分享

然后4给1的左孩子

技术分享

最终就是这样子啦~

技术分享
1 for (int i=1;i<=m;i++)
2 {
3    cin>>a>>b     //a是b的孩子
4    tree[a].r=tree[b].l;    //把b的左孩子给a的右孩子
5    tree[b].l=a;     //把a给b的左孩子
6 }
代码

 

多叉树转换二叉树