HDU3791二叉搜索树(二叉树)

时间:2022-09-18 13:30:30
Problem Description
判断两序列是否为同一二叉搜索树序列
 
Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
 
Output
如果序列相同则输出YES,否则输出NO
 
Sample Input
2
567432
543267
576342
 
Sample Output
YES
NO
 
Source
浙大计算机研究生复试上机考试-2010年
#include<cstdio>
#include<string.h>
#include<cmath>
using namespace std;
const int maxn=+;
char S[+],s[+],Tree[maxn],tree[maxn];
//建立原始二叉树
void BuildTree(char c,int i)
{
if(Tree[i]=='#')Tree[i]=c;
else
{
if(c<Tree[i])BuildTree(c,*i);
if(c>Tree[i])BuildTree(c,*i+);
}
}
//建立判断二叉树
void Buildtree(char c,int i)
{
if(tree[i]=='#')tree[i]=c;
else
{
if(c<tree[i])Buildtree(c,*i);
if(c>tree[i])Buildtree(c,*i+);
}
}
int main()
{
int n;
while(scanf("%d",&n)==&&n)
{
//输入原始数组
scanf("%s",&S);
int Len=strlen(S);
//建原始树
memset(Tree,'#',sizeof(Tree));
for(int i=;i<Len;i++)
{
BuildTree(S[i],);
}
while(n--)
{
//输入判断树组
scanf("%s",&s);
int len=strlen(s);
if(len!=Len)printf("NO\n");
else
{
//建判断树
memset(tree,'#',sizeof(tree));
for(int i=;i<len;i++)
{
Buildtree(s[i],);
}
int res=;
for(int i=;i<maxn;i++)
{
if(tree[i]!=Tree[i])
{
printf("NO\n");
res=;
break;
}
}
if(res==)printf("YES\n");
}
}
}
return ;
}
  

HDU3791二叉搜索树(二叉树)的更多相关文章

  1. 二叉搜索树 &amp&semi; 二叉树 &amp&semi; 遍历方法

    二叉搜索树 & 二叉树 & 遍历方法 二叉搜索树 BST / binary search tree https://en.wikipedia.org/wiki/Binary_searc ...

  2. hdu3791二叉搜索树

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3791 题意:给定一个n(多组,n为0时结束),给一个串和n个串,分别判断n个串按序列构建的二叉搜索树和 ...

  3. 数据结构-二叉搜索树的js实现

    一.树的相关概念 1.基本概念 子树 一个子树由一个节点和它的后代构成. 节点的度 节点所拥有的子树的个数. 树的度 树中各节点度的最大值 节点的深度 节点的深度等于祖先节点的数量 树的高度 树的高度 ...

  4. javascript实现二叉搜索树

    在使用javascript实现基本的数据结构中,练习了好几周,对基本的数据结构如 栈.队列.链表.集合.哈希表.树.图等内容进行了总结并且写了笔记和代码. 在 github中可以看到  点击查看,可以 ...

  5. &lbrack;数据结构&rsqb;——二叉树(Binary Tree)、二叉搜索树(Binary Search Tree)及其衍生算法

    二叉树(Binary Tree)是最简单的树形数据结构,然而却十分精妙.其衍生出各种算法,以致于占据了数据结构的半壁*.STL中大名顶顶的关联容器--集合(set).映射(map)便是使用二叉树实现 ...

  6. PAT树&lowbar;层序遍历叶节点、中序建树后序输出、AVL树的根、二叉树路径存在性判定、奇妙的完全二叉搜索树、最小堆路径、文件路由

    03-树1. List Leaves (25) Given a tree, you are supposed to list all the leaves in the order of top do ...

  7. 树&amp&semi;二叉树&amp&semi;二叉搜索树

    树&二叉树 树是由节点和边构成,储存元素的集合.节点分根节点.父节点和子节点的概念. 二叉树binary tree,则加了"二叉"(binary),意思是在树中作区分.每个 ...

  8. 数据结构-二叉树(应用篇)-之二叉搜索树 C和C&plus;&plus;的实现

    一.概念 二叉搜索树(Binary Sort Tree/Binary Search Tree...),是二叉树的一种特殊扩展.也是一种动态查找表. 在二叉搜索树中,左子树上所有节点的均小于根节点,右子 ...

  9. L3-016 二叉搜索树的结构 (30 分&rpar; 二叉树

    二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值:若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值:它的左.右子树也分别 ...

随机推荐

  1. Htmlhelper—CheckBox自动生成两个input

    前言 在之前的一篇文章中小猪分享了Htmlhelper的用法.其中有意思的一个就是Checkbox,有必要单独拿出来讲一讲. Htmlhelper—CheckBox 细心的读者一定发现了当使用类似语法 ...

  2. gcc编译常用选项

    我的博客:www.while0.com GDB调试: -g 生成的可执行文件才可以用gdb调试 (建议在发行版中用strip filename 来把这些调试信息去除) 开始调试. 以下是基础调试命令: ...

  3. php 函数积累第一天

    htmlspecialchars 函数格式化表单输入的转化为html形式 exit - 输出一个消息并且退出当前脚本 list() 用一步操作给一组变量进行赋值. <?php$info = ar ...

  4. CentOS7切换源

    1.备份 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup 2.下载新的CentOS-Base ...

  5. word2vec概述

    既然是概述,那么我也只会在文中谈一点关于 Word2Vec 的思想和大概的方法.对于这个算法,如果一开始学习就深入到算法细节中,反而会陷入局部极值点,最后甚至不知道这个算法是干嘛的.在了解算法大概的思 ...

  6. AJAX返回值问题

    ajax同步方式获取返回值,必须以同步请求的的方式获取. //主函数部分 function confirm(id,...)//省略部分参数 { //...省略部分代码 //任务涉及专业 var Maj ...

  7. ios-UITextView输入时,字数限制的倒数及对超出的字数进行截取并弹出提示框

    效果图如上,主要是右上角的Label显示框,创建完各控件后,可以在代理方法里贴上下面代码: -(void)textViewDidChange:(UITextView *)obj { UITextVie ...

  8. &lbrack;git&rsqb;git project仓库迁移

    转自:https://segmentfault.com/q/1010000000124379 如果你想从别的 Git 托管服务那里复制一份源代码到新的 Git 托管服务器上的话,可以通过以下步骤来操作 ...

  9. Atitit&period;request&&num;160&semi;http乱码的设计防止&&num;160&semi;检测与解决最近实践p825&&num;160&semi;attilax总结&period;doc

    Atitit.request http乱码的设计防止 检测与解决最近实践p825 attilax总结.doc 1 浏览器判断一个页面的编码有俩个途径, 一种是通过HTTP响应头, 一个是通过meta: ...

  10. Window 窗口类

    窗口类 WNDCLASS 总结 总结为下面的几个问题: . 什么是窗口类 . 窗口类的三种类型 . 窗口类各字段含义 . 窗口类的注册和注销 . 如何使用窗口类,子类化.超类化是什么 下面分别描述: ...