本文主要是介绍题目1520：树的子结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述：
-
输入两颗二叉树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”（不包含引号）。
代码1：（用例3测试不通过：Runtime error）
#include<stdio.h>
#include<stdlib.h>typedef struct tree
{int data;struct tree *left;struct tree *right;
}Node;
Node *Atree[1099],*Btree[1099];void create(Node *node[],int a[], int n)
{int count,left,right;for(int i = 1; i <= n; i++){node[i]->data = a[i];scanf("%d",&count);if(count == 2){scanf("%d %d",&left,&right);node[i]->left = node[left];node[i]->right = node[right];}else if(count == 1){scanf("%d",&left);node[i]->left = node[left];node[i]->right = NULL; }else{node[i]->left = NULL;node[i]->right = NULL;}}
}int dif = 0;
int compare(Node *T1, Node *T2)
{if(dif == 1) return 1;if(T2->left != NULL){if(T1->left == NULL || (T1->left->data != T2->left->data)){dif = 1;return 1;}elsecompare(T1->left,T2->left);}if(T2->right != NULL){if(T1->right == NULL || (T1->right->data != T2->right->data)){dif = 1;return 1;}elsecompare(T1->right,T2->right);}return dif;
}int main()
{int n,m;while(scanf("%d %d",&n,&m) != EOF){//创建树A int a[n + 1]; for(int i = 1; i <= n; i++)Atree[i] = new Node;for(int i = 1; i <= n; i++)scanf("%d",&a[i]);create(Atree,a,n);//创建树Bint b[m + 1];for(int i = 1; i <= m; i++)Btree[i] = new Node;for(int i = 1; i <= m; i++)scanf("%d",&b[i]);create(Btree,b,m);int j;for(j = 1; j <= n; j++){if(Atree[j]->data != Btree[1]->data)continue;dif = 0;if(compare(Atree[j],Btree[1]) == 0){printf("YES\n");break;}}if(j > n)printf("NO\n");//清空for(int i = 1;i <= n;i++){delete Atree[i];Atree[i]=NULL;}for(int i=1;i<=m;i++){delete Btree[i];Btree[i]=NULL;}}
}
代码2：
#include<stdio.h>
#include<stdlib.h>typedef struct tree
{int data;struct tree *left;struct tree *right;
}Node;
Node *Atree[1099],*Btree[1099];void create(Node *node[],int a[], int n)
{int count,left,right;for(int i = 1; i <= n; i++){node[i]->data = a[i];scanf("%d",&count);if(count == 2){scanf("%d %d",&left,&right);node[i]->left = node[left];node[i]->right = node[right];}else if(count == 1){scanf("%d",&left);node[i]->left = node[left];node[i]->right = NULL; }else{node[i]->left = NULL;node[i]->right = NULL;}}
}//第二步 左右子树都判断
bool IsContain(Node* root1,Node* root2)
{if(root2==NULL) //必须先判断root2是否是nullreturn true;if(root1==NULL)return false;if(root1->data!=root2->data)return false;return IsContain(root1->left,root2->left)&& IsContain(root1->right,root2->right);
}//第一步 找到根节点相同的值
bool HasSubTree(Node* root1,Node* root2)
{bool result=false;if(root1!=NULL&&root2!=NULL){if(root1->data==root2->data){result=IsContain(root1,root2);}if(!result){result=HasSubTree(root1->left,root2);}if(!result){result=HasSubTree(root1->right,root2);}}return result;
}int main()
{int n,m;while(scanf("%d %d",&n,&m) != EOF){//创建树A int a[n + 1];for(int i = 1; i <= n; i++)Atree[i] = new Node;for(int i = 1; i <= n; i++)scanf("%d",&a[i]);create(Atree,a,n);//创建树Bint b[m + 1];for(int i = 1; i <= m; i++)Btree[i] = new Node;for(int i = 1; i <= m; i++)scanf("%d",&b[i]);create(Btree,b,m);//判断bool result=HasSubTree(Atree[1],Btree[1]);printf("%s\n",result?"YES":"NO");//清空for(int i = 1;i <= n;i++){delete Atree[i];Atree[i]=NULL;}for(int i=1;i<=m;i++){delete Btree[i];Btree[i]=NULL;}}
}
这篇关于题目1520：树的子结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
