二叉排序树

小编 2026-07-05 阅读:263 评论:0
二叉排序树 Problem Description 二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子...

二叉排序树

Problem Description
二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树

Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉排序树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)
Output

Sample Input
2
123456789
987654321
432156789
0
Sample Output
NO
NO

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
typedef struct treenode
{
    char data;
    struct treenode*l,*r;
}tree;//改名字,少打两个字嘻嘻嘻
char a[30];
char b[30];
tree *plant(char x,tree*t)//排序树的建立
{
    if(t==NULL)
    {
        t=(tree*)malloc(sizeof(tree));
        t->data=x;
        t->l=t->r=NULL;
        return t;
    }
    if(x<t->data)
    {
        t->l=plant(x,t->l);
    }else
    {
        t->r=plant(x,t->r);
    }
    return t;
};
int k;//定义标记变量k来判断是否为同一棵树
void judge(tree*atree,tree*btree)
{
    if(atree&&btree)
    {
        if(atree->data!=btree->data)
        {
            k=1;
            return;
        }
        judge(atree->l,btree->l);//若相等则递归判断左子树
        judge(atree->r,btree->r);//若相等则递归判断右子树
    }
}
int main()
{
    int i,n,len1,len2;
    while(~scanf(\"%d\",&n)&&n)//若n==0跳出循环
    {
        scanf(\"%s\",a);
        len1=strlen(a);
        tree*atree=NULL;//注意这个坑,要把树初始化
        for(i=0;i<len1;i++)
        {
            atree=plant(a[i],atree);
        }
        while(n--)
        {
            tree*btree=NULL;//同样注意
            scanf(\"%s\",b);
            len2=strlen(b);
            k=0;//记得每次都要初始化标记变量k=0
            for(i=0;i<len2;i++)
            {
                btree=plant(b[i],btree);
            }
            judge(atree,btree);
            if(k)//若k=1则说明不是同一棵树
            {
                printf(\"NO\\n\");
            }else
            {
                printf(\"YES\\n\");
            }
        }
    }
    return 0;
}

版权声明

本文仅代表作者观点,不代表百度立场。
本文系作者授权百度百家发表,未经许可,不得转载。

上一篇:Docker安装和卸载 下一篇:Docker容器
热门文章
  • Sequential Monte Carlo Methods (SMC) 序列蒙特卡洛/粒子滤波/Bootstrap Filtering

    Sequential Monte Carlo Methods (SMC) 序列蒙特卡洛/粒子滤波/Bootstrap Filtering
    Problem Statement 我们考虑一个具有马尔可夫性质、非线性、非高斯的状态空间模型(State Space Model):对于一个时间序列上的观测结果{yt,t∈N}\\{ y_t , t \\in N \\}{yt​,t∈N},我们认为每个观测结果yty_tyt​的生成依赖于一个无法直接观察的隐变量xt∈{xt,t∈N}x_t \\in \\{x_t , t \\in N \\}xt​∈{xt​,t∈N},即:p(...
  • 机房智能化温湿度解决方式之POE供电以太网温湿度传感器

    机房智能化温湿度解决方式之POE供电以太网温湿度传感器
    机房智能化温湿度解决方式之POE供电以太网温湿度传感器 北京盈创力和电子科技有限公司 智能型TCP网口温湿度记录仪 北京IP网络温湿度记录仪厂家,北京盈创力和 北京智能型TCP网口温湿度记录仪IP网络温湿度记录仪是一种新型的基于TCP/IP协议双绞线以太网标准温湿度采集模块,利用它可以实现现场温度值、相对湿度值的采集,同时利用其自身的RJ45通信接口可以方便地和机房监控主机或交换机集线器进行联网。 工作于-40℃~85℃工业级带...
  • Hive 系统函数及示例

    Hive 系统函数及示例
    查看所有系统函数 show functions; 函数分类 内置函数【系统函数】 数学函数: floor、round、ceil、cos、log2等 字符串函数: length、reverse、trim、lower、get_json_object、repeat等 收集函数: size 转换函数: cast 日期函数: year、month、datediff、date、date_add等 条件函数: coalesce、case…w...
  • HTTP状态保持的原理

    HTTP状态保持的原理
    a)在用户登录之后,浏览器返回响应的时候会在响应中添加上cookieb)浏览器接收到cookie之后会自动保存c)当用户再次请求同一服务器中的其他网页的时候,浏览器会自动带上之前保存的cookied)服务接收到请求之后可以请 request 对象中取到cookie 判断当前用户是否登录  Http是无状态的,就是连接时数据互通,关闭后...
  • CSRF的原理和防范措施

    CSRF的原理和防范措施
    a)攻击原理:i.用户C访问正常网站A时进行登录,浏览器保存A的cookieii.用户C再访问攻击网站B,网站B上有某个隐藏的链接或者图片标签会自动请求网站A的URL地址,例如表单提交,传指定的参数iii.而攻击网站B在访问网站A的时候,浏览器会自动带上网站A的cookieiv.所以网站A在接收到请求之后可判断当前用户是登录状态,所以...
标签列表