二叉排序树

me Limit: 1000 ms  Memory Limit: 65536 KiB

Submit Statistic

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 node//结构体 { int data; struct node*l,*r; }tree; int flag; tree *insert(tree*t,int x)//建立排序二叉树（比较大小，进行递归建树） { if(t==NULL) { t=(tree*)malloc(sizeof(tree)); t->data=x; t->l=NULL; t->r=NULL; } else if(x<t->data) { t->l=insert(t->l,x); } else { t->r=insert(t->r,x); } return t; } tree*creat(char a[],int n) { int j=0; tree*t=NULL;//开始时根节点为空 while(j<n) { t=insert(t,a[j++]-'0');//建树 } return t; } int Is_equit(tree *t1,tree *t2) { if(t1==NULL&&t2==NULL)//如果同时为空，说明递归完成，这两颗树相等 { return 1; } else if(t1==NULL||t2==NULL)//如果进行到有一颗树空了，就说明不是相等的 { flag=0; return 0; } else if(t1->data!=t2->data)//节点不相等 { flag=0; return 0; } else return Is_equit(t1->l,t2->l)&&Is_equit(t1->r,t2->r); } int main() { int n,len; char a[30],b[30]; tree *t1,*t2; while(scanf("%d",&n)!=EOF&&n) { scanf("%s",a); len=strlen(a); t1=creat(a,len); while(n--) { scanf("%s",b); t2=creat(b,len); flag=1; Is_equit(t1,t2); if(flag==1) printf("YES\n"); else printf("NO\n"); } } return 0; }