L3-016. 二叉搜索树的结构

二叉搜索树是空树或具有以下属性的二叉树: 如果其左子树不为空二叉排序树 构造，则左子树上所有节点的值小于其根的值节点;如果其右子树不为空，则右子树上所有节点的值大于其根节点的值；它的左和右子树也是二叉搜索树. （摘自百度百科）

给出一系列不相等的整数，将它们插入最初为空的二进制搜索树中，然后描述结果树的结构. 您需要能够判断给定的描述是否正确. 例如，插入{2 4 1 3 0}以获取二叉搜索树后，语句语句为“ 2是树的根”，“ 1和4是同级节点”，“ 3和0在同一位置”级别”（从上到下指的是相同深度），“ 2是4的父节点”，“ 3是4的左子节点”是正确的；和“ 4是2的左孩子”，“ 1和3是兄弟”“节点”都是不正确的.

输入格式:

第一行的输入给出一个正整数N（<= 100），下一行给出N个不同的整数，以空格分隔二叉排序树 构造，要求将它们插入最初为空的Binary搜索树的树中. 然后给出一个正整数M（<= 100），后跟M行，每行给出一个要判断的陈述性句子. 陈述性句子有6种:

该问题确保所有给定的整数都在整数范围内.

输出格式:

对于每个语句，如果正确，则输出“是”，否则输出“否”，每个句子仅占一行.

输入示例:

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 <bits/stdc++.h>
using namespace std;
struct tree
{
    tree *left, *right, *f;
    int height,data;
}*root;
int n,d,k,a,b;
map<int,tree *> q;
map<int,int>o;
tree *creat(int d)
{
    tree *p = new tree();
    p->left = NULL;
    p->right = NULL;
    p->f = NULL;
    p->height = 0;
    p->data = d;
    q[d] = p;
    o[d] = 1;
    return p;
}
void insert_(tree *root,tree *t)
{
    if(t->data > root->data)
    {
        if(root -> right == NULL)root -> right = t,t -> f = root,t-> height = root -> height + 1;
        else insert_(root -> right,t);
    }
    else
    {
        if(root -> left == NULL)root -> left = t,t -> f = root,t-> height = root -> height + 1;
        else insert_(root -> left,t);
    }
}
int main()
{
    cin>>n;
    if(n)
    {
        cin>>d;
        root = creat(d);
    }
    for(int i = 1;i < n;i ++)
    {
        cin>>d;
        tree *p = creat(d);
        insert_(root,p);
    }
    cin>>k;
    for(int i = 0;i < k;i ++)
    {
        cin>>a;
        string op;
        cin>>op;
        if(op == "is")
        {
            cin>>op>>op;
            if(op == "root")
            {
                if(o[a] && root == q[a])cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
            else if(op == "parent")
            {
                cin>>op>>b;
                if(o[a] && o[b] && q[b] -> f == q[a])cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
            else if(op == "left")
            {
                cin>>op>>op>>b;
                if(o[a] && o[b] && q[b] -> left == q[a])cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
            else
            {
                cin>>op>>op>>b;
                if(o[a] && o[b] && q[b] -> right == q[a])cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
        }
        else
        {
            cin>>b>>op>>op;
            if(op == "on")
            {
                cin>>op>>op>>op;
                if(o[a] && o[b] && q[a] -> height == q[b] -> height)
                {
                    cout<<"Yes"<<endl;
                }
                else cout<<"No"<<endl;
            }
            else
            {
                if(o[a] && o[b] && q[a] -> f == q[b] -> f)cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
        }
    }
}

建立一个数组.

代码:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-265380-1.html