二叉树的子结构

题目：

输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节点定义如下：

struct BinaryTreeNode
{
    int           m_nValue;
   BinaryTreeNode* m_pLeft;
   BInaryTreeNode* m_pRight;
}

思路：首先在树A中找到和B的根结点的值一样的结点R，然后再判断树A中以R为根的子树是否包含树B一样的结构。

递归代码：

#include<stdio.h>
#include<stdlib.h>

struct BinaryTreeNode
{
	int         m_nValue;
	BinaryTreeNode*  m_pLeft;
	BinaryTreeNode*  m_pRight; 
};
bool doseTree1HaveTree2(BinaryTreeNode*,BinaryTreeNode*);
bool hasSubtree(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2)
{
	bool result=false;
	if(pRoot1!=NULL&&pRoot2!=NULL)
	{
		if(pRoot1->m_nValue==pRoot2->m_nValue)
			result=doseTree1HaveTree2(pRoot1,pRoot2);
			
		if(!result)
			result=hasSubtree(pRoot1->m_pLeft,pRoot2);
		if(!result)
			result=hasSubtree(pRoot1->m_pRight,pRoot2);
	}
	
	return result;
}
bool doseTree1HaveTree2(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2)
{
	if(pRoot2==NULL)
		return true;
	if(pRoot1==NULL)
		return false;
	
	if(pRoot1->m_nValue!=pRoot2->m_nValue)
		return false;
	
	
	return doseTree1HaveTree2(pRoot1->m_pLeft,pRoot2->m_pLeft)&&
		doseTree1HaveTree2(pRoot1->m_pRight,pRoot2->m_pRight);
} 
BinaryTreeNode* createTree(BinaryTreeNode* pRoot)
{
	int data;
	scanf("%d",&data);
	if(data!=-1)
	{
		pRoot=(BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
		if(pRoot==NULL)
			exit(0);
		pRoot->m_nValue=data;
		
		pRoot->m_pLeft=createTree(pRoot->m_pLeft); 
		pRoot->m_pRight=createTree(pRoot->m_pRight);
		
		return pRoot;
	}
	return NULL;		
}
int main()
{
	BinaryTreeNode* pRoot1,*head1;
	BinaryTreeNode* pRoot2,*head2;
	head1 =createTree(pRoot1);
	
	head2 =createTree(pRoot2);
	
	bool result =hasSubtree(head1,head2);
	if(result)
		printf("true");
	else
		printf("false");

	
	return 0;	
}

结果：