建立二叉搜索树并查找父结点
按输入顺序建立二叉搜索树，并搜索某一结点，输出其父结点。
输入格式:
输入有三行： 第一行是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
#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());
}
}
解释都在代码里了QAQ
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1005;
struct BinaryTree{
int val;
int l;
int r;
BinaryTree(){val=0;l=r=-1;}
}tree[N];
int ar[N],n,tot,x;
bool flag;//是否找到父节点
int ans;//答案
//递归建树，k为当前建树已经跑到了输入序列数组的第几号元素
void build(int k){
if(k>n)return;
tree[++tot].val=ar[k];
tree[tot].l=tree[tot].r=-1;
int i=1;
while(1){
if(ar[k]>=tree[i].val){//如果不小于此节点值就往右边建树
if(tree[i].r!=-1){
i=tree[i].r;
}else{
tree[i].r=tot;
break;
}
}else {
if(tree[i].l!=-1){
i=tree[i].l;
}else{
tree[i].l=tot;
break;
}
}
}
build(k+1);
return;
}
void Find(int k,int fa){
if(flag)return;//已找到就回溯
if(tree[k].val==x){
flag=true;
ans=fa;
return;
}
if(tree[k].l!=-1){//如果有左儿子往左搜索
Find(tree[k].l,tree[k].val);
if(flag)return;
}
if(tree[k].r!=-1){//如果有右儿子往右搜索
Find(tree[k].r,tree[k].val);
if(flag)return;
}
}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;++i){
scanf("%d",&ar[i]);
}
tot=1;//节点编号
tree[1].val=ar[1];//根节点
tree[1].l=tree[1].r=-1;
build(2);
scanf("%d",&x);
flag=0;ans=-1;
Find(1,-1);//找x
if(flag==false||ans==-1)printf("It doesn't have parent.\n");
else printf("%d\n",ans );
}
return 0;
}