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

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

2个回答

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

        }

}
sinat_26083883
sinat_26083883 回复weixin_41107720: c你都看不懂
大约一年之前 回复
weixin_41107720
weixin_41107720 这是C++吗,我看不懂欸
一年多之前 回复

解释都在代码里了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;
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

2
求一用数据结构c++编写的纸牌游戏程序
1
跪求大佬,请问怎么用代码实现求二叉排序树的平均检索长度,或者用什么思路实现
1
c++运用树结构解决等价性问题,详细要求如下
1
C++ 数据结构 创建一个二叉树,广度优先遍历。为啥结果不正确?
1
C++语言编程 二叉搜索树 查找
1
用最邻近法于最小生成树法解决货郎问题
0
C/C++ char类型指针数组输入问题
2
数据结构(C++版)哈弗曼 编码
1
[C++数据结构]自己按书中代码打了一个二叉查找树模板类,发现不能在树上正常插入元素
1
C++用哈弗曼编码实现压缩,编码文件比原文件大是怎么回事,怎么能实现压缩,代码如下,求修改
0
C++ 二叉搜索树 根节点的值运行过程中改变了 代码很短
1
C++ 写了一个二叉排序树的小程序,在牛客网OJ报错,请教一下各位。
0
二叉搜索树在数据结构方面的综合运用,如何利用C语言编程解决这个算法?
0
二叉平衡树的高效率的求法的问题,运用C语言系统的编程的技术
1
大佬们帮忙看看这个二叉搜索树哪错了
1
还是被二叉搜索树难住了,结果出不来,求教各位大佬到底哪错了
1
[Python] 尾递归方式求二叉查找树r中大于x的最小key
1
在查找方面二叉排序树效率与顺序查找的效率谁高(这里一般二叉排序树 不是指平衡二叉树)
0
数据结构相关问题,一直没有找到错误。代码哪里出错了呢?
2
二分查找判定树,有两个问题,求大佬支援。