首页 > 其他 > 详细

树的子结构

时间:2014-08-01 16:14:31      阅读:369      评论:0      收藏:0      [点我收藏+]
 
题目描述:

输入两颗二叉树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为空树时不是任何树的子树。

---------------------------------------
第一步:在树A中查找与树B根节点值一样的结点;
第二步:找到后,判断树A中以R为根结点的子树是否和B树结点完全一致。
这两步都可以使用递归来完成。

代码:

#include<iostream>
using namespace std;
typedef struct _BNOODE_
{
	int data;
	struct _BNOODE_ *lChild;
	struct _BNOODE_ *rChild;
}BNode,*pTree;
//判断pTree1和pTree2是否相同
bool isSubTree(pTree pTree1,pTree pTree2)
{
	if(pTree2 == NULL)
	{
		return true;
	}
	if(pTree1 == NULL)
	{
		return false;
	}
	if(pTree1->data != pTree2->data)
	{
		return false;
	}
	return isSubTree(pTree1->lChild,pTree2->lChild) && isSubTree(pTree1->rChild,pTree2->rChild);
}
//判断pTree1中是否包含pTree2
bool isConstansTree(pTree pTree1,pTree pTree2)
{
	if(pTree1 == NULL || pTree2 == NULL)
	{
		return false;
	}
	bool result = false;
	if(pTree1->data == pTree2->data)
	{
		result = isSubTree(pTree1,pTree2);
	}
	if(!result)
	{
		result = isConstansTree(pTree1->lChild,pTree2);
	}
	if(!result)
	{
		result = isConstansTree(pTree1->rChild,pTree2);
	}
	return result;
}
void create(pTree *ppTree)
{
	int data = 0;
	cin>>data;
	if(data != -1)
	{
		*ppTree = (pTree)malloc(sizeof(BNode));
		if(*ppTree == NULL)
		{
			exit(-1);
		}
		(*ppTree)->data = data;
		(*ppTree)->lChild = NULL;
		(*ppTree)->rChild = NULL;
		create(&(*ppTree)->lChild);
		create(&(*ppTree)->rChild);
	}
}
int main()
{
	pTree pa,pb;
	cout<<"input tree A"<<endl;
	create(&pa);
	cout<<"input tree B:"<<endl;
	create(&pb);
	cout<<"result is:";
	if(isConstansTree(pa,pb))
	{
		cout<<"YES\n";
	}else
	{
		cout<<"NO\n";
	}
	return 0;
}

当然,这个代码AC不了,因为测试方法不正确。
测试代码比较麻烦,应该使用数组作为存储结构.
AC代码:

/*
树的子树结构
by Rowandjj
2014/8/1
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct _BNODE_
{
	int data;
	int lChild;
	int rChild;
}BNode;
bool isSubTree(BNode *pTree1,int index1,BNode *pTree2,int index2)
{//递归依次比较每个结点的值
	if(index2 == -1)
	{
		return true;
	}
	if(index1 == -1)
	{
		return false;
	}
	if(pTree1[index1].data != pTree2[index2].data)
	{
		return false;
	}
	else
		return isSubTree(pTree1,pTree1[index1].lChild,pTree2,pTree2[index2].lChild)&&
			   isSubTree(pTree1,pTree1[index1].rChild,pTree2,pTree2[index2].rChild);
}
bool isContainsTree(BNode *pTree1,int index1,BNode *pTree2,int index2)
{	
	if(pTree1 == NULL || pTree2 == NULL || index1 == -1 || index2 == -1)
	{
		return false;
	}
	bool result = false;
	//找到一个结点使得这个结点和待比较树的根结点值相同
	if(pTree1[index1].data == pTree2[index2].data)
	{
		result = isSubTree(pTree1,index1,pTree2,index2);
	}
	//否则递归左子树和右子树
	if(!result)
	{
		result = isContainsTree(pTree1,pTree1[index1].lChild,pTree2,index2);
	}
	if(!result)
	{	
		result = isContainsTree(pTree1,pTree1[index1].rChild,pTree2,index2);
	}
	return result;
}
int main()
{
	int m,n;
	while(scanf("%d %d",&n,&m) != EOF)
	{
		BNode *pTree1 = NULL;
		if(n > 0)
		{
			pTree1 = (BNode *)malloc(sizeof(BNode) * n);
			if(!pTree1)
			{
				exit(-1);
			}
			int i,data;
			for(i = 0; i < n; i++)
			{
				scanf("%d",&data);
				pTree1[i].data = data;
				pTree1[i].lChild = -1;
				pTree1[i].rChild = -1;
			}
			
			for(i = 0; i < n; i++)
			{
				int ki;
				scanf("%d",&ki);
				if(ki == 0)
				{
					continue;
				}else if(ki == 1)
				{
					int l;
					scanf("%d",&l);
					pTree1[i].lChild = l-1;
				}else if(ki == 2)
				{
					int r,l;
					scanf("%d %d",&l,&r);
					pTree1[i].lChild = l-1;
					pTree1[i].rChild = r-1;
				}
			}
		}
		BNode *pTree2 = NULL;
		if(m > 0)
		{
			pTree2 = (BNode *)malloc(sizeof(BNode) * m);
			if(pTree2 == NULL)
			{
				exit(-1);
			}
			int i,data;
			for(i = 0; i < m; i++)
			{
				scanf("%d",&data);
				pTree2[i].data = data;
				pTree2[i].lChild = -1;
				pTree2[i].rChild = -1;
			}
			
			for(i = 0; i < m; i++)
			{
				int ki;
				scanf("%d",&ki);
				if(ki == 0)
				{
					continue;
				}else if(ki == 1)
				{
					int l;
					scanf("%d",&l);
					pTree2[i].lChild = l-1;
				}else if(ki == 2)
				{
					int r,l;
					scanf("%d %d",&l,&r);
					pTree2[i].lChild = l-1;
					pTree2[i].rChild = r-1;
				}
			}
		}
		if(isContainsTree(pTree1,0,pTree2,0))  
            printf("YES\n");  
        else  
            printf("NO\n");  
	}
	return 0;
}






树的子结构,布布扣,bubuko.com

树的子结构

原文:http://blog.csdn.net/chdjj/article/details/38336003

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!