二叉排序树-白红宇

二叉排序树

阅读量：6368 次

发布时间：2019-06-23

本文共 1562 字，大约阅读时间需要 5 分钟。

Time Limit: 1000MS Memory limit: 65536K

题目描写叙述

二叉排序树的定义是：或者是一棵空树。或者是具有下列性质的二叉树：若它的左子树不空，则左子树上全部结点的值均小于它的根结点的值；若它的右子树不空。则右子树上全部结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

今天我们要推断两序列是否为同一二叉排序树

输入

開始一个数n，(1<=n<=20) 表示有n个须要推断，n= 0 的时候输入结束。

接下去一行是一个序列。序列长度小于10，包括(0~9)的数字，没有反复数字，依据这个序列能够构造出一颗二叉排序树。

接下去的n行有n个序列，每一个序列格式跟第一个序列一样，请推断这两个序列能否组成同一颗二叉排序树。

(数据保证不会有空树)

输出

演示样例输入

21234567899876543214321567890

演示样例输出

NONO

依然是二叉排序树。。定义都没变 然后推断两颗树是否为同一二叉排序树，我是直接dfs一种先序遍历然后看两颗树的先序遍历是否同样。。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #define ll long long#define maxn 1010#define pp pair
                   
                    #define INF 0x3f3f3f3f#define max(x,y) ( ((x) > (y)) ?

(x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; typedef struct node { char d; node *l,*r; }*p; int n,sb; void Insert(p &T,int x) { if(T==NULL) { T=new node; T->l=NULL;T->r=NULL; T->d=x; } else { if(x<T->d) Insert(T->l,x); else Insert(T->r,x); } } void dfs(p T,char *ans) { if(T) { ans[sb++]=T->d; dfs(T->l,ans); dfs(T->r,ans); } } int main() { while(~scanf("%d",&n)&&n) { p root=NULL; char tem[12],ans[12]; scanf("%s",tem); for(int i=0;i<strlen(tem);i++) Insert(root,tem[i]); sb=0;dfs(root,ans);ans[sb]='\0'; while(n--) { p troot=NULL; scanf("%s",tem); for(int i=0;i<strlen(tem);i++) Insert(troot,tem[i]); sb=0;dfs(troot,tem);tem[sb]='\0'; if(!strcmp(ans,tem)) puts("YES"); else puts("NO"); } } return 0; }

转载地址：http://axema.baihongyu.com/

你可能感兴趣的文章