数据结构实验之查找一：二叉排序树
Time Limit: 400 ms Memory Limit: 65536 KiB
Problem Description
对应给定的一个序列可以唯一确定一棵二叉排序树。然而，一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树，都得到一样的结果。你的任务书对于输入的各种序列，判断它们是否能生成一样的二叉排序树。
Input
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (n < = 10)和L，分别是输入序列的元素个数和需要比较的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列生成一颗二叉排序树。随后L行，每行给出N个元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
Output
对每一组需要检查的序列，如果其生成的二叉排序树跟初始序列生成的二叉排序树一样，则输出"Yes"，否则输出"No"。
Sample Input
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
Sample Output
Yes
No
No
Hint
Source
xam
思路：套模板建立二叉排序树，输出前序遍历，比较相不相同。
#include <stdio.h> #include <stdlib.h> #include <string.h> struct node { int data; struct node *lc; struct node *rc; }; int k, l, a[1100], b[1100]; struct node *creat(struct node *root, int x) { if(root == NULL) { root = (struct node *)malloc(sizeof(struct node)); root->data = x; root->lc = NULL; root->rc = NULL; } else { if(x < root->data) { root->lc = creat(root->lc, x); } else { root->rc = creat(root->rc, x); } } return root; }; void str1(struct node *root) { if(root) { a[k++] = root->data; str1(root->lc); str1(root->rc); } } void str2(struct node *root) { if(root) { b[l++] = root->data; str2(root->lc); str2(root->rc); } } int main() { int n, m, x, i; struct node *root, *root1; while(scanf("%d%d", &n, &m) != EOF) { if(n == 0) { break; } else { root = NULL; for(i = 0; i < n; i++) { scanf("%d", &x); root = creat(root, x); } k = 0; memset(a, 0, sizeof(a)); str1(root); while(m--) { l = 0; root1 = NULL; for(i = 0; i < n; i++) { scanf("%d", &x); root1 = creat(root1, x); } memset(b, 0, sizeof(b)); str2(root1); for(i = 0; i < n; i++) { if(a[i] != b[i]) { break; } } if(i == n) { printf("Yes\n"); } else { printf("No\n"); } } } } return 0; }
个人感觉这种办法并不是最好的，最好的办法应该直接比较树的子树的大小。代码的意思如下
#include <stdio.h> #include <stdlib.h> #include <string.h> struct node { char data; struct node *lc; struct node *rc; }; struct node *creat(struct node *root, int x) { if(root == NULL) { root = (struct node *)malloc(sizeof(struct node)); root->lc = NULL; root->rc = NULL; root->data = x; } else { if(x > root->data) { root->rc = creat(root->rc, x); } else { root->lc = creat(root->lc, x); } } return root; }; int flag; void bijiao(struct node *root, struct node *root1) { if(root != 0 && root1 != 0) { if(root->data != root1->data) { flag = 1; return; } bijiao(root->lc, root1->lc); bijiao(root->rc, root1->rc); } } int main() { int n, i, len1, len2; char a[11], b[11]; struct node *root; struct node *root1; while(scanf("%d", &n) != EOF) { if(n == 0) { break; } else { scanf("%s", a); len1 = strlen(a); root = NULL; for(i = 0; i < len1; i++) { root = creat(root, a[i]); } while(n--) { flag = 0; scanf("%s", b); len2 = strlen(b); root1 = NULL; for(i = 0; i < len2; i++) { root1 = creat(root1, b[i]); } bijiao(root, root1); if(flag == 0) { printf("YES\n"); } else { printf("NO\n"); } } } } return 0; }
