二叉排序树
Time Limit: 1000MS Memory limit: 65536K
题目描述
二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树
输入
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。 接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉排序树。 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)
输出
示例输入
2
123456789
987654321
432156789
0
示例输出
NO
NO
提示
来源
示例程序
建立二叉排序树,然后比较两个的先序遍历
#include
#include
#include
struct node { int data; struct node *l,*r; }; int cnt; struct node *creat(struct node *&root,int a) { if(root==NULL) { root=(struct node *)malloc(sizeof(struct node)); root->l=NULL; root->r=NULL; root->data=a; } else { if(a
data) creat(root->l,a); else creat(root->r,a); } }; void qianxu(struct node *root,char *str) { if(root) { str[cnt++]=root->data; qianxu(root->l,str); qianxu(root->r,str); } } int main() { int n,i; char str1[20],str2[20]; while(~scanf("%d",&n)) { if(n==0) break; scanf("%s",str1); int len=strlen(str1); struct node *root=NULL; cnt=0; for(i=0;i