建树的⼏种常⽤⽅法
⽅法⼀:
此⽅法适⽤条件:
1.当我们遍历这颗树时只需要从⽗节点查到⼦节点，不需要从⼦节点查到⽗节点.
2.所建树为⼀颗⼆叉树
实现代码:
class Tree{
int value;//代表该点的权值
int left_son;//左⼉⼦编号
int right_son;//右⼉⼦编号
int leftSide_value;//连接左⼉⼦的边的权值
int rightSide_value;//连接右⼉⼦边的权值
}
nextint()方法根据题⽬描述进⾏输⼊.
如依次输⼊ 节点编号 节点权值 左⼉⼦编号 右⼉⼦编号 连接左⼉⼦的边的权值 连接右⼉⼦边的权值
for(int i=1;i<=n;i++)//n代表节点的个数
{Int();
tree[num].Int();
tree[num].left_Int();
.......
}
⽅法⼆:
此⽅法适⽤条件:
1.当我们遍历这颗树时只需要从⽗节点查到⼦节点，不需要从⼦节点查到⽗节点.
2.此⽅法弥补了⽅法⼀的⼀个不⾜,⽅法⼀只适⽤于⼆叉树，不适⽤于有多个⼦节点的树,⽽此⽅法可以可以有多个⼦节点
实现代码:
void add(int a,int b){//表⽰a为⽗ b为⼦
edge[cnt]= b;
ne[cnt]= last[a];
last[a]= cnt++;
}
相信看到这代码有点晕，当初我也是，看看下⾯的查的过程
我们在看看它的储存结构，我们按输⼊的顺序给节点排队，假设存在这样⼀颗树
数字代表输⼊的顺序，我们展⽰⼀下树右边是如何联系起来的(cnt代表的是输⼊顺序并不是点真正的编号,edge[cnt]才是点真正的编号)
故可得查询代码
for(int i=last[a];i>=1;i=ne[i])
持续更新!

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。