题目1520：树的子结构
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：1933
解决：463
题目描述：
输入两颗二叉树A，B，判断B是不是A的子结构。
输入：
输入可能包含多个测试样例，输入以EOF结束。 对于每个测试案例，输入的第一行一个整数n,m(1<=n<=1000,1<=m<=1000)：n代表将要输入的二叉树A的节点个数（节点从1开始计数），m代表将要输入的二叉树B的节点个数（节点从1开始计数）。接下来一行有n个数，每个数代表A树中第i个元素的数值，接下来有n行，第一个数Ki代表第i个节点的子孩子个数，接下来有Ki个树，代表节点i子孩子节点标号。接下来m+1行，与树A描述相同。
输出：
对应每个测试案例， 若B是A的子树输出”YES”(不包含引号)。否则，输出“NO”（不包含引号）。
样例输入：
7 3
8 8 7 9 2 4 7
2 2 3
2 4 5
0
0
2 6 7
0
0
8 9 2
2 2 3
0
0
1 1
2
0
3
0
样例输出：
YES
NO
提示：
B为空树时不是任何树的子树。
不怎么会这道题，参考了好多前辈们写的代码， 不知怎么回事，那些带代码提交后都显示编译错误。
主要需要解决数据的输入（采用指针数组，此处参考http://blog.csdn.net/wenlovingliu/article/details/11749447?utm_source=jiancool）
还要解决验证B树是否为A树的子树， 第一步要在A中找到和B树根节点数据一样的节点， 然后不断比对左孩子右孩子---递归查找验证（此处参考 http://blog.csdn.net/chilseasai/article/details/45788109）
下面附上我的代码， 在九度OJ上提交也是显示编译错误。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX 1000
typedef struct node
{
int data;
struct node *left, *right;
}node ,*tree;
void init(tree A[])
{
int i;
for (i = 1; i < MAX; i++)
{
A[i] = NULL;
}
return;
}
bool findtree(tree A, tree B)
{
if (B == NULL)
return true;
if (A == NULL)
return false;
if (A->data == B->data)
return findtree(A->left, B->left) && findtree(A->right, B->right);
return false;
}
bool compare(tree A, tree B)
{
bool result = false;
if (A != NULL&&B != NULL)
{
if (A->data == B->data)
result = findtree(A, B);
if (!result)
result = compare(A->left, B);
if (!result)
result = compare(A->right, B);
}
return result;
}
int main()
{
int n, m, i;
while (scanf("%d%d", &n, &m) != EOF)
{
tree A[MAX], B[MAX];
init(A);
init(B);
int cnt;
tree p;
for (i = 1; i <= n; i++)
{
p = (tree)malloc(sizeof(node));
scanf("%d", &p->data);
p->left = NULL;
p->right = NULL;
A[i] = p;
}
for (i = 1; i <= n; i++)
{
int a, b;
scanf("%d", &cnt);
switch (cnt)
{
case 2:
scanf("%d%d", &a, &b);
A[i]->left = A[a];
A[i]->right = A[b];
break;
case 1:
scanf("%d", &a);
A[i]->left = A[a];
break;
case 0:
break;
}
}
for (i = 1; i <= m; i++)
{
p = (tree)malloc(sizeof(node));
scanf("%d", &p->data);
p->left = NULL;
p->right = NULL;
B[i] = p;
}
for (i = 1; i <= m; i++)
{
int a, b;
scanf("%d", &cnt);
switch (cnt)
{
case 2:
scanf("%d%d", &a, &b);
B[i]->left = B[a];
B[i]->right = B[b];
break;
case 1:
scanf("%d", &a);
B[i]->left = B[a];
break;
case 0:
break;
}
}
if (compare(A[1], B[1]))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
