首页 > 代码库 > 树的子结构

树的子结构

2024-07-15 07:09:36   221人阅读

 
题目描述：

输入两颗二叉树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 =http://www.mamicode.com/= pTree2->data)>
当然，这个代码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 =http://www.mamicode.com/= pTree2[index2].data)>


联系
我们