首页 > 代码库 > 多叉树转换二叉树
多叉树转换二叉树
多叉转二叉,前提是我们仍要把树的信息保留下来,也就是谁是谁的孩子,谁是谁的兄弟。但是二叉只能保存两个孩子,但我们可以把两个孩子改成两个关系,也就是我们利用二叉来储存关系,一个是孩子,一个是兄弟。
于是,就出现了网上广泛介绍的方法,当一个节点是另一个节点的孩子时,就放在父亲节点的左孩子上,是兄弟,就该放在右孩子上,也就是所谓的“左儿子,右兄弟”。
当然多叉转二叉的形式不止一种,上图是其中的一种。
因为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 }
多叉树转换二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。