建立二叉搜索树并查找父结点 C++语言

Question

建立二叉搜索树并查找父结点
按输入顺序建立二叉搜索树，并搜索某一结点，输出其父结点。
输入格式:
输入有三行： 第一行是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

Answer 1

 #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());

        }

}