輸入兩棵二叉樹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;
}

注：我們一定要注意邊界條件的檢查，即檢查空指針。當父樹或子樹為空的時候，定義相應的輸出。如果沒有檢查并做相應的處理，程序非常容易崩潰。