輸入兩顆二叉樹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為空樹時不是任何樹的子樹。
這道題有個坑，首先題目要求n與m的范圍不能為0，但是測試用例中第三個和第四個有可能分別是第一個樹空和第二個數空的特殊情況。因此，要特別注意這裡，在scanf("%d %d",&n,&m)的時候對mn注意限制的范圍。
另外用例並沒有給出單個葉子的情況，這時注意，當輸入為1時，只有一個節點，並且是左子樹節點。
例如當只有一個孩子時輸入的是
孩子節點的數目 左邊孩子的編號
另外就是這個題目的主要思想了。首先我們采用的仍然是上次題目使用的結構的樹，主要思想就是遍歷左邊這顆樹的沒個元素，與右邊的樹進行比較。如果不同，就再比較左邊的孩子節點。一直到遍歷完所有的樹。
在進行比較時，判斷右邊的樹是否為空，以及左邊的判斷頂點是否為空，一旦發現比較的元素不同，就證明比較失敗。
主要的代碼，模仿書上代碼進行，自己寫的總出BUG，哎。
int testForCompare(TreeArr *t1,int t1i,TreeArr *t2){
int result = 0;
if(t1i != 0 && t2->arr[0].num != 0){
if(t1->arr[t1i].num == t2->arr[1].num)
result = compare(t1,t1i,t2,1);
if(!result)
result = testForCompare(t1,t1->arr[t1i].lchild,t2);
if(!result)
result = testForCompare(t1,t1->arr[t1i].rchild,t2);
}
return result;
};
int compare(TreeArr *t1,int t1i,TreeArr *t2,int t2i){
if(t2i == 0)
return 1;
if(t1i == 0)
return 0;
if(t1->arr[t1i].num != t2->arr[t2i].num)
return 0;
return compare(t1,t1->arr[t1i].lchild,t2,t2->arr[t2i].lchild)&&compare(t1,t1->arr[t1i].rchild,t2,t2->arr[t2i].rchild);
}
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1005
typedef struct treeelement{
int num;
int lchild;
int rchild;
}TreeElement;
typedef struct treearr{
TreeElement arr[MAXSIZE];
}TreeArr;
int testForCompare(TreeArr *t1,int t1i,TreeArr *t2);
int compare(TreeArr *t1,int t1i,TreeArr *t2,int t2i);
int main(void){
int n,m,i,nchild,n1,n2;
TreeArr *t1 = (TreeArr *)malloc(sizeof(TreeArr));
TreeArr *t2 = (TreeArr *)malloc(sizeof(TreeArr));
while(scanf("%d %d",&n,&m) != EOF){
//....initialize the tree
for(i=0;i<1000;i++){
t1->arr[i].num = 0;
t1->arr[i].lchild = 0;
t1->arr[i].rchild = 0;
t2->arr[i].num = 0;
t2->arr[i].lchild = 0;
t2->arr[i].rchild = 0;
}
t1->arr[0].num = n;
t2->arr[0].num = m;
//.....input the first tree
for(i=1;i<=n;i++){
scanf("%d",&t1->arr[i].num);
}
for(i=1;i<=n;i++){
scanf("%d",&nchild);
if(nchild == 2){
scanf("%d %d",&n1,&n2);
t1->arr[i].lchild = n1;
t1->arr[i].rchild = n2;
}else if(nchild == 1){//不確定是怎麼輸入的？樣例中沒有這項
scanf("%d",&n1);
t1->arr[i].lchild = n1;
}else if(nchild == 0){
}
}
//........input the second tree
for(i=1;i<=m;i++){
scanf("%d",&t2->arr[i].num);
}
for(i=1;i<=m;i++){
scanf("%d",&nchild);
if(nchild == 2){
scanf("%d %d",&n1,&n2);
t2->arr[i].lchild = n1;
t2->arr[i].rchild = n2;
}else if(nchild == 1){//不確定是怎麼輸入的？樣例中沒有這項
scanf("%d",&n1);
t2->arr[i].lchild = n1;
}else if(nchild == 0){
}
}
//testing for compare
if(testForCompare(t1,1,t2))
printf("YES\n");
else
printf("NO\n");
}
return 0;
};
int testForCompare(TreeArr *t1,int t1i,TreeArr *t2){
int result = 0;
if(t1i != 0 && t2->arr[0].num != 0){
if(t1->arr[t1i].num == t2->arr[1].num)
result = compare(t1,t1i,t2,1);
if(!result)
result = testForCompare(t1,t1->arr[t1i].lchild,t2);
if(!result)
result = testForCompare(t1,t1->arr[t1i].rchild,t2);
}
return result;
};
int compare(TreeArr *t1,int t1i,TreeArr *t2,int t2i){
if(t2i == 0)
return 1;
if(t1i == 0)
return 0;
if(t1->arr[t1i].num != t2->arr[t2i].num)
return 0;
return compare(t1,t1->arr[t1i].lchild,t2,t2->arr[t2i].lchild)&&compare(t1,t1->arr[t1i].rchild,t2,t2->arr[t2i].rchild);
}
/**************************************************************
Problem: 1520
User: xhalo
Language: C
Result: Accepted
Time:10 ms
Memory:912 kb
****************************************************************/
