输入两棵二叉树A和B，判断树B是不是A的子结构

题目描述：

题目：二叉树的结点定义如下：

struct TreeNode

{

       int m_nValue;

       TreeNode* m_pLeft;

       TreeNode* m_pRight;

};

输入两棵二叉树A和B，判断树B是不是A的子结构。

例如，下图中的两棵树A和B，由于A中有一部分子树的结构和B是一样的，因此B就是A的子结构。

                1                                                8
              /    \                                           /  \
             8      7                                          9    2
           /    \
          9       2
                /  \
               4    7

要查找树A中是否存在和树B结构一样的子树，我们可以分为两步：第一步在树A中找到和B的根结点的值一样的结点N，第二步再判断树A中以N为根结点的子树是不是包括和树B一样的结构。

第一步在树A中查找与根结点的值一样的结点。这实际上就是树的遍历。

第二步判断以树A中以N为根结点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果结点N的值和树B的根结点不相同，则以N为根结点的子树和树B肯定不具有相同的结点；如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。

#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
	int data;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
	BinaryTreeNode(int x)
		:data(x)
		, left(NULL)
		, right(NULL)
	{}
};
class BinaryTree
{
protected:
	BinaryTreeNode* _root;
	BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
	{
		BinaryTreeNode* root = NULL;
		if (index<size&&arr[index] != '#')
		{
			root = new BinaryTreeNode(arr[index]);
			root->left = _CreateBinaryTree(arr, ++index, size);
			root->right = _CreateBinaryTree(arr, ++index, size);
		}
		return root;
	}
	bool CommonRoot(BinaryTreeNode* father, BinaryTreeNode* child)
	{
		bool ret = false;
		if (father->data == child->data)
		{
			ret=HaveSub(father, child);
		}
		if (!ret&&father->left != NULL)
			ret=CommonRoot(father->left, child);
		if (!ret&&father->right != NULL)
			ret=CommonRoot(father->right, child);
		return ret;
	}
	bool HaveSub(BinaryTreeNode* father, BinaryTreeNode* child)
	{
		if (child == NULL)//子树为空
			return true;
		if (father == NULL)//子树为空，父树不为空
			return false;
		if (father->data != child->data)
			return false;
		//如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。
		//递归的终止条件是我们到达了父树或者子树的叶结点
		return HaveSub(father->left, child->left) && HaveSub(father->right, child->right);
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	BinaryTree(int *arr, int size)
	{
		int index = 0;
		_root = _CreateBinaryTree(arr, index, size);
	}
	void PreOrder_Non()
	{
		if (_root == NULL)
			return;
		BinaryTreeNode* cur = _root;
		stack<BinaryTreeNode*> s;
		s.push(_root);
		while (!s.empty())
		{
			cur = s.top();
			printf("%d ", cur->data);
			s.pop();
			if (cur->right)
				s.push(cur->right);
			if (cur->left)
				s.push(cur->left);
		}
		cout << endl;
	}
	void InOrder_Non()
	{
		if (_root == NULL)
			return;
		stack<BinaryTreeNode*> s;
		BinaryTreeNode* cur = _root;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}
			if (!s.empty())
			{
				cout << s.top()->data << " ";
				cur = s.top()->right;
				s.pop();
			}
		}
		cout << endl;
	}
	void PostOrder_Non()
	{
		if (_root == NULL)
			return;
		stack<BinaryTreeNode*> s;
		BinaryTreeNode* cur = _root;
		BinaryTreeNode* prev = NULL;
		BinaryTreeNode* top = NULL;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}
			top = s.top();
			if (top->right == NULL || top->right == prev)
			{
				cout << top->data << " ";
				s.pop();
				prev = top;
			}
			else
			{
				cur = top->right;
			}
		}
		cout << endl;
	}
	bool IsSub(BinaryTree& bt)
	{
		if ((_root == NULL&&bt._root != NULL) || (_root != NULL&&bt._root == NULL))
			return false;
		if (_root == NULL&&bt._root == NULL)
			return true;
		return CommonRoot(_root, bt._root);
	}
};


void Test1()
{
	/*int arr1[] = { 1, 8, 9, '#', '#', 2, 4, '#', '#', 7, '#', '#', 7 };
	int arr2[] = { 8, 9, '#', '#', 2 };
	BinaryTree b1(arr1, sizeof(arr1) / sizeof(arr1[0]));
	BinaryTree b2(arr2, sizeof(arr2) / sizeof(arr2[0]));
	b1.InOrder_Non();
	b2.InOrder_Non();
	//1
	cout << b1.IsSub(b2) << endl;*/
	int arr1[] = { 1, 8, 9, '#', '#', 8, 4, '#', '#', 7, '#', '#', 7 };
	int arr2[] = { 8, 4, '#', '#', 7 };
	BinaryTree b1(arr1, sizeof(arr1) / sizeof(arr1[0]));
	BinaryTree b2(arr2, sizeof(arr2) / sizeof(arr2[0]));
	b1.InOrder_Non();
	b2.InOrder_Non();
	//0
	cout << b1.IsSub(b2) << endl;//当子树不相等时，可继续向下重新寻找相同的根节点
	int arr3[] = { 2, 3, '#', '#', 6 };
	BinaryTree b3(arr3, sizeof(arr3) / sizeof(arr3[0]));
	//0
	cout << b1.IsSub(b3) << endl;
	
}
#include"Tree.h"
int main()
{
	Test1();
	system("pause");
	return 0;
}

注：我们一定要注意边界条件的检查，即检查空指针。当父树或子树为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃。