二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树 Input
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树) Output
Example Input
2 123456789 987654321 432156789 0 Example Output
NO NO Hint
Author
因为要判断是不是同一二叉排序树，所以就判断是否等于它本身。
#include<stdio.h>#include<stdlib.h>#include<string.h>struct node{ int data; struct node *l, *r;};struct node *creat(struct node *root, char number)//建树{ if(root == NULL) { root = (struct node *) malloc(sizeof(struct node)); root -> data = number; root -> l = NULL; root -> r = NULL; } else { if(root -> data > number) root -> l = creat(root -> l, number); else root -> r = creat(root -> r, number); } return root;};int x = 0;void judge(struct node *root1, struct node *root2){ if(root1 == NULL || root2 == NULL) { return; } if(root1 && root2) { if(root1 -> data != root2 -> data) return; else { x++; judge(root1 -> l, root2 -> l); judge(root1 -> r, root2 -> r); } }}int main(){ int n, len, i, j; char a[22], b[22]; while(scanf("%d", &n) != EOF) { if(n == 0) break; struct node *root1 = NULL;//划重点 scanf("%s", a); len = strlen(a); for(i = 0; i < len; i++) root1 = creat(root1, a[i]); for(i = 0; i < n; i++) { x = 0;//划重点 struct node *root2 = NULL;//划重点 scanf("%s", b); for(j = 0; j < len; j++) { root2 = creat(root2, b[j]); } judge(root1, root2); if(x == len) printf("YES/n"); else printf("NO/n"); } } return 0;}新闻热点
疑难解答
