PTA 数据结构二叉搜索树的结构

秒速五厘米 2022-04-17 01:44 202阅读 0赞

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`，即"`A`和`B`是兄弟结点"；
 *  `A is the parent of B`，即"`A`是`B`的双亲结点"；
 *  `A is the left child of B`，即"`A`是`B`的左孩子"；
 *  `A is the right child of B`，即"`A`是`B`的右孩子"；
 *  `A and B are on the same level`，即"`A`和`B`在同一层上"。

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

### 输出格式： ###

对每句陈述，如果正确则输出`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

#include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #define maxn 110
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    #define INFEASIBLE -1
    #define OVERFLOW   -2
    using namespace std;
    typedef int Status;
    typedef struct BSTNode
    {
        int data;
        BSTNode *lchild,*rchild,*parent;
    }BSTNode,*BSTree;
    
    Status InitTree(BSTree &T)
    {
        T = (BSTree)malloc(sizeof(BSTNode));
        if(!T)
            exit(OVERFLOW);
        T->lchild = NULL;
        T->rchild = NULL;
        T->parent = NULL;
        return OK;
    }
    void InsertTree(BSTree T, int a)
    {
    
        BSTree p = T;
        BSTree prep = NULL;
        while (p)  //找到插入位置
        {
            prep = p;
            if (p->data < a)
                p = p->rchild;
            else
                p = p->lchild;
        }
        p = (BSTree)malloc(sizeof(BSTNode));
        p->data = a;
        p->lchild = NULL;
        p->rchild = NULL;
        p->parent = prep;
        if (prep->data > a)  //决定左右
            prep->lchild = p;
        else if (prep->data < a)
            prep->rchild = p;
        else
            return;
    }
    BSTree Search(BSTree T,int a)
    {
        BSTree p = T;
        while (p)  
        {
            if(p->data == a)
                break;
            else if (p->data < a)
                p = p->rchild;
            else
                p = p->lchild;
        }
        return p;
    }
    int GetLevel(BSTree T,int a)
    {
        int level = 0;
        BSTree p = T;
        while (p)  
        {
            if(p->data == a)
                return level;
            else if (p->data < a)
            {
                p = p->rchild;
                level++;
            }
            else
            {
                p = p->lchild;
                level++;
            }
        }
        return -1;
    }
    
    int main()
    {
        int n;
        cin>>n;
        int arr[maxn];
        BSTree T;
        InitTree(T);
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            if(!i)
                T->data = arr[i];
            else
                InsertTree(T,arr[i]);
        }
        int m;
        cin>>m;
        while(m--)
        {
            int A,B;
            cin>>A;
            char s[10];
            cin>>s;
            if(!strcmp(s,"is"))
            {
                char tmp[10],relation[10];
                cin>>tmp>>relation;
                if(!strcmp(relation,"root"))
                {
                    if(arr[0]==A)
                        cout<<"Yes"<<endl;
                    else
                        cout<<"No"<<endl;
                }
                else if(!strcmp(relation,"parent"))
                {
                    cin>>tmp>>B;
                    BSTree p = Search(T,B);
                    if(p && p->parent && p->parent->data==A)
                        cout<<"Yes"<<endl;
                    else
                        cout<<"No"<<endl;
                }
                else if(!strcmp(relation,"left"))
                {
                    char temp[3];
                    cin>>tmp>>temp>>B;
                    BSTree p =Search(T,B);
                    if(p && p->lchild && p->lchild->data==A)
                        cout<<"Yes"<<endl;
                    else
                        cout<<"No"<<endl;
                }
                else if(!strcmp(relation,"right"))
                {
                    char temp[3];
                    cin>>tmp>>temp>>B;
                    BSTree p =Search(T,B);
                    if(p && p->rchild && p->rchild->data==A)
                        cout<<"Yes"<<endl;
                    else
                        cout<<"No"<<endl;
                }
            }
            else if(!strcmp(s,"and"))
            {
                cin>>B;
                char tmp[10],relation[10];
                cin>>tmp>>relation;
                if(!strcmp(relation,"siblings"))
                {
                    BSTree pa = Search(T,A);
                    BSTree pb = Search(T,B);
                    if(pa && pb && pa->parent && pb->parent && pa->parent == pb->parent)
                        cout<<"Yes"<<endl;
                    else 
                        cout<<"No"<<endl;
                }
                else if(!strcmp(relation,"on"))
                {
                    char the[10],same[10],level[10];
                    cin>>the>>same>>level;
                    int levela = GetLevel(T,A);
                    int levelb = GetLevel(T,B);
                    if(levela == -1 && levelb == -1 )
                        cout<<"No"<<endl;
                    else if(levela == levelb)
                        cout<<"Yes"<<endl; 
                    else
                        cout<<"No"<<endl; 
                }
            }      
        }
    
        return 0;
    }