PTA 7-2 二叉搜索树的结构(30 分)

7-2 二叉搜索树的结构(30 分)

二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。(摘自百度百科)

给定一系列互不相等的整数,将它们顺次插入一棵初始为空的二叉搜索树,然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后,得到一棵二叉搜索树,则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”(指自顶向下的深度相同)、“2是4的双亲结点”、“3是4的左孩子”都是正确的;而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式:

输入在第一行给出一个正整数N(≤100),随后一行给出N个互不相同的整数,数字间以空格分隔,要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M(≤100),随后M行,每行给出一句待判断的陈述句。陈述句有以下6种:

  • A is the root,即"A是树的根";
  • A and B are siblings,即"AB是兄弟结点";
  • A is the parent of B,即"AB的双亲结点";
  • A is the left child of B,即"AB的左孩子";
  • A is the right child of B,即"AB的右孩子";
  • A and B are on the same level,即"AB在同一层上"。

题目保证所有给定的整数都在整型范围内。

输出格式:

对每句陈述,如果正确则输出Yes,否则输出No,每句占一行。

输入样例:

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例:

Yes
Yes
Yes
Yes
Yes
No
No
No这个是26分的代码 ,少了一个判断 ,输出的点必须在给定的数里:最后给出满分代码:
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 220;
int BST[maxn];
int n,m;
typedef struct TNode
{
    int data;
    struct TNode *left,*right;
}TNode,*BiTree;
void buildtree(BiTree &T,int x)//建树
{
    if(T==NULL)
    {
        T=(BiTree)malloc(sizeof(BiTree));
        T->data=x;
        T->left=NULL;
        T->right=NULL;
    }
    else if(x<T->data)
    {
        buildtree(T->left,x) ;
    }
    else if(x>T->data)
    {
        buildtree(T->right,x);
    }
}
bool Search_BST(BiTree &T,int x)
{
    if(T==NULL||T->data==x) return true;
    if(T->data>x) return Search_BST(T->left,x);
    else return Search_BST(T->right,x);
}
int Get_value(BiTree &T)
{
    if(T==NULL) return -1;
    return T->data;
}
bool Judge_Parent(BiTree T,int x,int y)
{
    if(T==NULL)
    {
        return false;
    }
    if(T->data==x)
    {
        if(Get_value(T->left)==y||Get_value(T->right)==y)
            return true;
    }
    return (Judge_Parent(T->left,x,y)||Judge_Parent(T->right,x,y));
}
bool  Judge_LChild(BiTree T,int x,int y)
{
    if(T==NULL)
    {
        return false;
    }
    if(T->data==y)
    {
        if(Get_value(T->left)==x)
            return true;
    }
    return (Judge_LChild(T->left,x,y)||Judge_LChild(T->right,x,y));
}
bool Judge_RChild(BiTree T,int x,int y)
{
    if(T==NULL)
    {
        return false;
    }
    if(T->data==y)
    {
        if(Get_value(T->right)==x)
            return true;
    }
    return (Judge_RChild(T->left,x,y)||Judge_RChild(T->right,x,y));
}
void Height(BiTree& T,int e,int h,int &c)
{
    if(T==NULL) return;
    if(T->data==e) c=h;
    Height(T->left,e,h+1,c);
    Height(T->right,e,h+1,c);
}
bool Judge_Same(BiTree T,int x,int y)
{
    int f1 , f2;
    Height(T,x,0,f1);
    Height(T,y,0,f2);
    if(f1==f2) return true;
    return false;
}
bool Judge_Bother(BiTree T,int x,int y)
{
    if(T==NULL) return false;
    if(T->left!=NULL&&T->right!=NULL)
    {
        if(T->left->data==x&&T->right->data==y) return true;
        if(T->left->data==x&&T->right->data==y) return true;
    }
    Judge_Bother(T->left,x,y);
    Judge_Bother(T->right,x,y);
}
int main()
{
    scanf("%d",&n);
    BiTree T=NULL;
    for(int i=0;i<n;i++) scanf("%d",&BST[i]);
    for(int i=0;i<n;i++) buildtree(T,BST[i]);
    scanf("%d",&m);
    int _a,_b,_c;
    string a,b,c;
    while(m--)
    {
        scanf("%d",&_a);
        cin>>a;
        if(a=="is")
        {
            cin>>a>>b;
            if(b=="parent")
            {
                cin>>c>>_b;
                if(Judge_Parent(T,_a,_b))
                    printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else if(b=="left")
            {
                cin>>b>>c;
                cin>>_b;
                if(Judge_LChild(T,_a,_b))
                 printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else if(b=="right")
            {
                cin>>b>>c;
                cin>>_b;
                if(Judge_RChild(T,_a,_b))
                     printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else if(b=="root")
            {
                if(T!=NULL&&T->data==_a)
                    printf("Yes\n");
                else
                    printf("No\n");
                continue;
            }
        }
        else if(a=="and")
        {
            cin>>_b;
            cin>>b>>c;
            if(c=="siblings")
            {
                if(Judge_Bother(T,_a,_b))
                     printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else
            {
                getline(cin,b);
                if(Judge_Same(T,_a,_b)) // 层数相同
                 printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
        }
    }
}

  加了判断的满分代码:

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 220;
int BST[maxn];
int n,m;
typedef struct TNode
{
    int data;
    struct TNode *left,*right;
}TNode,*BiTree;
void buildtree(BiTree &T,int x)//建树
{
    if(T==NULL)
    {
        T=(BiTree)malloc(sizeof(BiTree));
        T->data=x;
        T->left=NULL;
        T->right=NULL;
    }
    else if(x<T->data)
    {
        buildtree(T->left,x) ;
    }
    else if(x>T->data)
    {
        buildtree(T->right,x);
    }
}
bool Search_BST(BiTree &T,int x)
{//查找关键字k并返回其指针
    if(T==NULL||T->data==x) return true;
    if(T->data>x) return Search_BST(T->left,x);
    else return Search_BST(T->right,x);
}
int Get_value(BiTree &T)
{
    if(T==NULL) return -1;
    return T->data;
}
bool Judge_Parent(BiTree T,int x,int y)
{
    if(T==NULL)
    {
        return false;
    }
    if(T->data==x)
    {
        if(Get_value(T->left)==y||Get_value(T->right)==y)
            return true;
    }
    return (Judge_Parent(T->left,x,y)||Judge_Parent(T->right,x,y));
}
bool  Judge_LChild(BiTree T,int x,int y)
{
    if(T==NULL)
    {
        return false;
    }
    if(T->data==y)
    {
        if(Get_value(T->left)==x)
            return true;
    }
    return (Judge_LChild(T->left,x,y)||Judge_LChild(T->right,x,y));
}
bool Judge_RChild(BiTree T,int x,int y)
{
    if(T==NULL)
    {
        return false;
    }
    if(T->data==y)
    {
        if(Get_value(T->right)==x)
            return true;
    }
    return (Judge_RChild(T->left,x,y)||Judge_RChild(T->right,x,y));
}
void Height(BiTree& T,int e,int h,int &c)
{
    if(T==NULL) return;
    if(T->data==e) c=h;
    Height(T->left,e,h+1,c);
    Height(T->right,e,h+1,c);
}
bool Judge_Same(BiTree T,int x,int y)
{
    int f1 , f2;
    Height(T,x,0,f1);
    Height(T,y,0,f2);
    if(f1==f2) return true;
    return false;
}
bool Judge_Bother(BiTree T,int x,int y)
{
    if(T==NULL) return false;
    if(T->left!=NULL&&T->right!=NULL)
    {
        if(T->left->data==x&&T->right->data==y) return true;
        if(T->left->data==x&&T->right->data==y) return true;
    }
    Judge_Bother(T->left,x,y);
    Judge_Bother(T->right,x,y);
}
bool finds(int x)
{
    for(int i=0;i<n;i++)
        if(x==BST[i]) return true;
    return false;
}
int main()
{
    scanf("%d",&n);
    BiTree T=NULL;
    for(int i=0;i<n;i++) scanf("%d",&BST[i]);
    for(int i=0;i<n;i++) buildtree(T,BST[i]);
    scanf("%d",&m);
    int _a,_b,_c;
    string a,b,c;
    while(m--)
    {
        scanf("%d",&_a);
        cin>>a;
        if(a=="is")
        {
            cin>>a>>b;
            if(b=="parent")
            {
                cin>>c>>_b;
                if(Judge_Parent(T,_a,_b)&&finds(_a)&&finds(_b))
                    printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else if(b=="left")
            {
                cin>>b>>c;
                cin>>_b;
                if(Judge_LChild(T,_a,_b)&&finds(_a)&&finds(_b))
                 printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else if(b=="right")
            {
                cin>>b>>c;
                cin>>_b;
                if(Judge_RChild(T,_a,_b)&&finds(_a)&&finds(_b))
                     printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else if(b=="root")
            {
                if(T!=NULL&&T->data==_a&&finds(_a))
                    printf("Yes\n");
                else
                    printf("No\n");
                continue;
            }
        }
        else if(a=="and")
        {
            cin>>_b;
            cin>>b>>c;
            if(c=="siblings")
            {
                if(Judge_Bother(T,_a,_b)&&finds(_a)&&finds(_b))
                     printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
            else
            {
                getline(cin,b);
                if(Judge_Same(T,_a,_b)&&finds(_a)&&finds(_b)) // 层数相同
                 printf("Yes\n");
                else
                printf("No\n");
                continue;
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 孩子们的游戏(圆圈中最后剩下的数) [剑指offer] 孩子们的游戏(圆圈中最后剩下的数)

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友...

773
来自专栏专知

关关的刷题日记85 – Leetcode 326. Power of Three

关关的刷题日记85 – Leetcode 326. Power of Three 题目 Given an integer, write a function t...

35510
来自专栏工科狗和生物喵

【计算机本科补全计划】图的连通性check by 并查集Union Find

具体的想法来自一篇写的超好的博客,如果底子不是很好,建议看下面这篇,当然如果可以给我顺手点个赞就更好了!!

612
来自专栏向治洪

Android开发如何写出优雅的代码

很多时候我们去面试,人家总会问一个问题,你们公司开发一个app是如何进行技术选择的,app中涉及到了哪些开发模式,谈谈你对mvc、mvp和mvvm的区别。或许在...

1856
来自专栏小樱的经验随笔

Uva - 12050 Palindrome Numbers【数论】

题目链接:uva 12050 - Palindrome Numbers 题意:求第n个回文串 思路:首先可以知道的是长度为k的回文串个数有9*10^(k-1),...

2454
来自专栏专知

【LeetCode 205】关关的刷题日记38 Isomorphic Strings

关关的刷题日记38 – Leetcode 205. Isomorphic Strings 题目 Given two strings s and t, deter...

2724
来自专栏程序生活

第四周编程作业(一)-Building your Deep Neural Network: Step by StepBuilding your Deep Neural Network: Step by

Building your Deep Neural Network: Step by Step Welcome to your week 4 assignmen...

58611
来自专栏专知

【LeetCode 136】 关关的刷题日记32 Single Number

关关的刷题日记32 – Leetcode 136. Single Number 题目 Given an array of integers, every ele...

3426
来自专栏专知

关关的刷题日记81 – Leetcode 258. Add Digits

关关的刷题日记81 – Leetcode 258. Add Digits 题目 Given a non-negative integer num, repeat...

2557
来自专栏数据处理

CEdit只能输入16进制数

1175

扫码关注云+社区