模板--二叉搜索树

╰半夏微凉° 2022-06-11 04:20 138阅读 0赞

问题描述：   
  
判断两序列是否为同一二叉搜索树序列  
  
 输入：

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

输出：

如果序列相同则输出YES，否则输出NO

样例输入：

2  
567432  
543267  
576342  
0

样例输出：

YES  
NO

思路：  
  
二叉搜索树和二叉树不同，他的意思是基于根节点，左孩子节点值比根节点小，右孩子比根节点值大。  
  
代码：

#include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    int tree1[10010],tree2[10010];
    void Insert(char word ,int *tree)
    {
        int rt=1;
        int c=word-'0';
        while(tree[rt]!=-1){
            if(tree[rt]<c)
                rt=rt<<1|1;
            else rt=rt<<1;
        }
        tree[rt]=c;
    }
    void build (char *str,int *tree)
    {
        int len=strlen(str);
        tree[1]=str[0]-'0';
        for(int i=1;i<len;i++)
        {
            Insert(str[i],tree);
        }
    }
    int main()
    
    {
        char str[10010];
        int n;
        while(scanf("%d",&n)&&n)
        {
            memset(tree1,-1,sizeof(tree1));
            scanf("%s",str);
            build(str,tree1);
            int j=0;
            for(int i=0;i<n;i++)
            {
                memset(tree2,-1,sizeof(tree2));
            scanf("%s",str);
            build(str,tree2);
            for( j=0;j<1000;j++)
            {
                if(tree1[j]!=tree2[j])
                    break;
            }
            if(j==1000)
                printf("YES\n");
            else
                printf("NO\n");
          }
       }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，138人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉搜索树、平衡二叉树

一、二叉搜索树这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 104 阅读

相关二叉搜索树

在计算机术语中，二叉搜索树又叫二叉查找树、二叉排序树。二叉搜索树（Binary Search Tree）的定义：它或者是一棵空树，或者是具有下列性质的二叉树：若它的

Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 258 阅读

相关二叉搜索树

搜索树数据结构支持许多动态集合操作，包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此，我们使用一

╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 247 阅读

相关模板--二叉搜索树

问题描述：判断两序列是否为同一二叉搜索树序列输入：开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。接

╰半夏微凉°/ 2022年06月11日 04:20/ 0 赞/ 139 阅读

相关二叉搜索树

二叉搜索树的特征定义就是：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字大于或等于这个父节点 package Trees; import java.ut

客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 331 阅读

相关 c++模板编程，搜索二叉树构造

// 树的迭代器 tree\_iterator.h // // Created by Yongyu Wu on 2018/11/11. //

妖狐艹你老母/ 2022年04月17日 01:53/ 0 赞/ 159 阅读

相关二叉搜索树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy

た入场券/ 2022年03月17日 02:18/ 0 赞/ 327 阅读

相关二叉搜索树

二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不

小咪咪/ 2021年12月20日 02:53/ 0 赞/ 351 阅读

相关二叉搜索树

二叉搜索树 C++实现![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9

今天药忘吃喽~/ 2021年12月14日 08:47/ 0 赞/ 328 阅读

相关二叉搜索树

二叉搜索树基本概念二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 409 阅读