建立二叉搜索树并查找父结点
按输入顺序建立二叉搜索树,并搜索某一结点,输出其父结点。
输入格式:
输入有三行: 第一行是n值,表示有n个结点; 第二行有n个整数,分别代表n个结点的数据值; 第三行是x,表示要搜索值为x的结点的父结点。
输出格式:
输出值为x的结点的父结点的值。 若值为x的结点不存在,则输出:It does not exist. 若值为x的结点是根结点,则输出:It doesn't have parent.
输入样例:
2
20
30
20
输出样例:
It doesn't have parent.
输入样例:
2
20
30
30
输出样例:
20
建立二叉搜索树并查找父结点 C++语言
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答
- dabocaiqq 2018-05-06 13:59关注
#include <iostream> #include<stdio.h> using namespace std; const int size=10005; int T,N,first,second; vectorvec[size]; //用来记录图的信息 bool root[size]; //用来查找根节点 int depth[size]; //用来记录该节点的深度 int father[size]; //用来记录该节点的父节点 //录入数据 void In_data() { scanf("%d",&N); for(int i=1;i<=N;++i) { vec[i].clear(); depth[i]=0; root[i]=true; father[i]=i; } for(int i=1;i { int beg,end; scanf("%d%d",&beg,&end); vec[beg].push_back(end); father[end]=beg; root[end]=false; } scanf("%d%d",&first,&second); } //parent表示根节点,dep表示当前节点的深度 void depth_plus(int parent,int dep) { for(int i=0;i { depth_plus(vec[parent][i],dep+1); } depth[parent]=dep; } //在线算法查找最近公共祖先 int find_ancestor() { if(depth[first]>depth[second]) { while(depth[first]!=depth[second]) { first=father[first]; } } else if(depth[second]>depth[first]) { while(depth[first]!=depth[second]) { second=father[second]; } } while(first!=second) { first=father[first]; second=father[second]; } return first; } int main() { //freopen("1.txt","r",stdin); scanf("%d",&T); while(T--) { In_data(); //以根节点为入口,给每个点赋予深度 for(int i=1;i<=N;++i) { if(root[i]==true) { depth_plus(i,0); break; } } printf("%d\n",find_ancestor()); } }
解决 无用评论 打赏 举报
悬赏问题
- ¥20 删除和修改功能无法调用
- ¥15 kafka topic 所有分副本数修改
- ¥15 小程序中fit格式等运动数据文件怎样实现可视化?(包含心率信息))
- ¥15 如何利用mmdetection3d中的get_flops.py文件计算fcos3d方法的flops?
- ¥40 串口调试助手打开串口后,keil5的代码就停止了
- ¥15 电脑最近经常蓝屏,求大家看看哪的问题
- ¥60 高价有偿求java辅导。工程量较大,价格你定,联系确定辅导后将采纳你的答案。希望能给出完整详细代码,并能解释回答我关于代码的疑问疑问,代码要求如下,联系我会发文档
- ¥50 C++五子棋AI程序编写
- ¥30 求安卓设备利用一个typeC接口,同时实现向pc一边投屏一边上传数据的解决方案。
- ¥15 SQL Server analysis services 服务安装失败