树的子结构

#include<stdio.h>

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

BinaryTreeNode* createBinaryTreeNode(int value)
{
	BinaryTreeNode* pNewNode = new BinaryTreeNode();
	pNewNode->m_nValue = value;
	pNewNode->m_pLeft = NULL;
	pNewNode->m_pRight = NULL;
	return pNewNode;
}
void connectBinaryTreeNode(BinaryTreeNode* pParent,BinaryTreeNode* pLeftChild,
						   BinaryTreeNode* pRightChild)
{
	if(!pParent)
		return;

	pParent->m_pLeft = pLeftChild;
	pParent->m_pRight = pRightChild;
}
/*
bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree);
//判断pSmallTree是不是pBigTree的子树
bool isSubtreeInBinaryTree(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree)
{
	if(pSmallTree == NULL || pBigTree == NULL)
		return false;

	bool result = false;
	bool result1 = false;
	bool result2 = false;
	result = hasTheSubTeeWithRoot(pBigTree,pSmallTree);
	if(pBigTree->m_pLeft)
		result1 = isSubtreeInBinaryTree(pBigTree->m_pLeft,pSmallTree);
	if(pBigTree->m_pRight)
		result2 = isSubtreeInBinaryTree(pBigTree->m_pRight,pSmallTree);
	
	return	(result || result1 || result2);
}
//两棵树已包含根节点为条件，判断是否为子树
bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree)
{
	if(pSmallTree == NULL)
		return true;
	if(pBigTree == NULL)
		return false;

	bool result = false;
	bool result1 = false;
	bool result2 = false;
	if(pBigTree->m_nValue == pSmallTree->m_nValue)
	{
		result = true;
		result1 = hasTheSubTeeWithRoot(pBigTree->m_pLeft,pSmallTree->m_pLeft);
		result2 = hasTheSubTeeWithRoot(pBigTree->m_pRight,pSmallTree->m_pRight);
	}
	return result && result1 && result2;
}
*/

//以上注释的代码能实现基本功能，但效率很差,原因是上述方法即使一开始确定
//是子树，也会继续遍历较大树下面的每个节点。
//下面方法可以避免这个问题
bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree);
bool isSubtreeInBinaryTree(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree)
{ 
	bool result = false;
	if(pBigTree != NULL && pSmallTree != NULL)
	{
		if(pBigTree->m_nValue == pSmallTree->m_nValue)
			result = hasTheSubTeeWithRoot(pBigTree,pSmallTree);
		if(!result)	//如果查找出子树就停止往下查找
			result = isSubtreeInBinaryTree(pBigTree->m_pLeft,pSmallTree);
		if(!result)
			result = isSubtreeInBinaryTree(pBigTree->m_pRight,pSmallTree);
	}
	return result;
}

bool hasTheSubTeeWithRoot(BinaryTreeNode* pBigTree, BinaryTreeNode* pSmallTree)
{
	if(pSmallTree == NULL)
		return true;
	if(pBigTree == NULL)
		return false;

	if(pBigTree->m_nValue != pSmallTree->m_nValue)
		return false;
	//用return语句递归
	return hasTheSubTeeWithRoot(pBigTree->m_pLeft,pSmallTree->m_pLeft) && hasTheSubTeeWithRoot(pBigTree->m_pRight,pSmallTree->m_pRight);
}


//单元测试
void test1()
{
	BinaryTreeNode* pNode1 = createBinaryTreeNode(8);
	BinaryTreeNode* pNode2 = createBinaryTreeNode(8);
	BinaryTreeNode* pNode3 = createBinaryTreeNode(7);
	BinaryTreeNode* pNode4 = createBinaryTreeNode(9);
	BinaryTreeNode* pNode5 = createBinaryTreeNode(2);
	BinaryTreeNode* pNode6 = createBinaryTreeNode(4);
	BinaryTreeNode* pNode7 = createBinaryTreeNode(7);

	connectBinaryTreeNode(pNode1,pNode2,pNode3);
	connectBinaryTreeNode(pNode2,pNode4,pNode5);
	connectBinaryTreeNode(pNode5,pNode6,pNode7);

	BinaryTreeNode* pNode21 = createBinaryTreeNode(8);
	BinaryTreeNode* pNode22 = createBinaryTreeNode(9);
	BinaryTreeNode* pNode23 = createBinaryTreeNode(2);
	connectBinaryTreeNode(pNode21,pNode22,pNode23);

	if(isSubtreeInBinaryTree(pNode1,pNode21))
		printf("the smalltree is a subtree in bigtree");
	else
		printf("not subtree");
}
void test2()
{
	BinaryTreeNode* pNode1 = createBinaryTreeNode(8);
	BinaryTreeNode* pNode2 = createBinaryTreeNode(8);
	BinaryTreeNode* pNode3 = createBinaryTreeNode(7);
	BinaryTreeNode* pNode4 = createBinaryTreeNode(9);
	BinaryTreeNode* pNode5 = createBinaryTreeNode(2);
	BinaryTreeNode* pNode6 = createBinaryTreeNode(4);
	BinaryTreeNode* pNode7 = createBinaryTreeNode(7);

	connectBinaryTreeNode(pNode1,pNode2,pNode3);
	connectBinaryTreeNode(pNode2,pNode4,pNode5);
	connectBinaryTreeNode(pNode5,pNode6,pNode7);

	BinaryTreeNode* pNode21 = createBinaryTreeNode(8);
	BinaryTreeNode* pNode22 = createBinaryTreeNode(9);
	BinaryTreeNode* pNode23 = createBinaryTreeNode(2);
	BinaryTreeNode* pNode24 = createBinaryTreeNode(1);
	BinaryTreeNode* pNode25 = createBinaryTreeNode(2);
	connectBinaryTreeNode(pNode21,pNode22,pNode23);
	connectBinaryTreeNode(pNode22,pNode24,pNode25);

	if(isSubtreeInBinaryTree(pNode1,pNode21))
		printf("the smalltree is a subtree in bigtree");
	else
		printf("not subtree");
}
int main()
{
	test1();
	printf("\n\n");
	test2();
	return 0;
}

二叉树相关的代码有大量的指针操作，每一次使用指针的时候，我们都要问自己这个

指针有没有可能是NULL，如果是NULL该怎么处理。

==参考剑指offer