题目链接地址：
九度OJ-题目1520：树的子结构
题目描述：
输入两颗二叉树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
2 6 7
8 9 2
2 2 3
1 1
2
3
样例输出：
YES
NO
提示：
B为空树时不是任何树的子树。
解题思路:
（1）先构造二叉树A和二叉树B，因为二叉树是一种递归的数据结构，也就是说二叉树的子树也是二叉树，利用二叉树的这个性质。先将二叉树的每个结点都看成是只有根结点没有左右子树的二叉树，然后根据每个结点的左右孩子得出各个结点之间的父子关系，构造出二叉树的结构，再将没有父结点的结点挑出来做为二叉树的根结点，这样就完成了二叉树的构造；（需要注意的是题目并没有说明如何处理一个孩子结点的情况。我上网搜了一下，网上的说法是当输入1时，认为该结点只有一个左孩子结点，我想测试数据中可能没有孩子个数为1的数据吧）
（2）依次遍历二叉树A的每个结点rootA；（二叉树遍历的本质是将树形结构转化为线性结构，二叉树有前序遍历，中序遍历，后序遍历3种遍历方式。因为题目已经给出了二叉树A的结点数值数组，而在构造二叉树的过程中会用到结点数组，所以我采用遍历结点数组的办法来遍历二叉树A，具体请参看代码）
（3）将当前正在被遍历的二叉树A的结点rootA与二叉树B的根结点rootB进行比较，如果二者相等则同时前序遍历以rootA为根结点的二叉树subA和二叉树B。在前序遍历的过程中如果发现B树中的某些结点在subA树中不存在（如图1所示）或者B树中某个结点值与subA树中位置相同的结点值不相等（如图2所示），则可以断定B树不是subA树的子树，提前终止本次前序遍历过程，跳转到步骤（2）继续遍历二叉树A的下一个结点，直至二叉树A中的所有结点被遍历完为止。
图1 B树的结点2在subA树中不存在，可以断定B不是subA的子树
图2 B树的结点3与subA树中同位置的结点2不相等，可以断定B不是subA的子树
AC代码如下：
#include<stdio.h>
#define MAX 1002
// 定义二叉树的结点结构
typedef struct Node
{
bool isRootNode; // 标记结点是否为根结点
int data; // 数据域
Node * lChild; // 左孩子
Node * rChild; // 右孩子
}BinaryTreeNode;
BinaryTreeNode biTree[2][MAX]; // 定义二叉树的结点数组,BiTree[0][]表示二叉树A,BiTree[1][]表示二叉树B
bool ifBTreeIsSubOfATree; // 标记二叉树B是否为二叉树A的子树
/**
* 初始化二叉树的各个结点的关系，将每个结点都看成是一棵只包含根结点而没有左右子树的二叉树
* @param int numberOfNode 表示二叉树的结点个数
* @param int index index为0时，表示初始化的是二叉树A,index为1时，表示初始化的是二叉树B
* @return void
*/
void initBinaryTree(int numberOfNode,int index)
{
int i;
// 初始状态下认为每个结点都是一颗只包含根结点的二叉树
for(i = 1;i <= numberOfNode;i++)
{
scanf("%d",&biTree[index][i].data);
biTree[index][i].lChild = NULL;
biTree[index][i].rChild = NULL;
biTree[index][i].isRootNode = true;
}
}
/**
* 构造二叉树
* @param int numberOfNode 表示二叉树的结点个数
* @param int index index为0时，表示构造的是二叉树A,index为1时，表示构造的是二叉树B
* @return BinaryTreeNode * 返回二叉树的根结点
*/
BinaryTreeNode * createBinaryTree(int numberOfNode,int index)
{
BinaryTreeNode * root = NULL;
int i;
int numberOfChild; // 标记结点的孩子的个数
int lChild,rChild; // lChild为左孩子的结点编号，rChild为右孩子的结点编号
initBinaryTree(numberOfNode,index); // 初始化二叉树中的各个结点之间的关系
for(i = 1;i <= numberOfNode;i++)
{
scanf("%d",&numberOfChild);
switch(numberOfChild)
{
case 0:
break;
case 1: // 当输入1时，认为结点只有一个左孩子结点，网上搜来的，测试数据中没有孩子个数为1的情况
scanf("%d",&lChild);
biTree[index][i].lChild = &biTree[index][lChild];
biTree[index][lChild].isRootNode = false;
break;
case 2:
scanf("%d%d",&lChild,&rChild);
biTree[index][i].lChild = &biTree[index][lChild];
biTree[index][lChild].isRootNode = false;
biTree[index][i].rChild = &biTree[index][rChild];
biTree[index][rChild].isRootNode = false;
break;
default:
break;
}
}
// 寻找二叉树的根结点
for(i = 1;i <= numberOfNode;i++)
{
if(true == biTree[index][i].isRootNode)
{
root = &biTree[index][i];
break;
}
}
return root;
}
/**
* 先序遍历二叉树
* @param BinaryTreeNode * rootA 二叉树A的根结点
* @param BinaryTreeNode * rootB 二叉树B的根结点
* @return void
*/
void preOrderBinaryTree(BinaryTreeNode * rootA,BinaryTreeNode * rootB)
{
if(NULL == rootA || NULL == rootB)
{
//当B树中的结点不为空，而A树的结点为NULL时，表示B树中的部分结点不在A树中，所以可以认为B不是A的子树
if(NULL == rootA && NULL != rootB)
ifBTreeIsSubOfATree = false;
return;
}
else
{
if(rootA -> data == rootB -> data)
{
preOrderBinaryTree(rootA -> lChild,rootB -> lChild); // 先序遍历左子树
preOrderBinaryTree(rootA -> rChild,rootB -> rChild); // 先序遍历右子树
}
else
{
ifBTreeIsSubOfATree = false;
return; // 如果两个值不相同的结点，则立即返回，无需再进行后面的遍历操作
}
}
}
/**
* 判断二叉树B是否为二叉树A的子树
* @param BinaryTreeNode * rootA 二叉树A的根结点
* @param BinaryTreeNode * rootB 二叉树B的根结点
* @param int n 二叉树A的结点个数
* @param int m 二叉树B的结点个数
* @return 如果二叉树B是二叉树A的子树，则返回true;否则返回false
*/
bool isBTreeIsSubOfATree(BinaryTreeNode * rootA,BinaryTreeNode * rootB,int n,int m)
{
int i;
ifBTreeIsSubOfATree = false;
// 遍历A树中的每一个结点，如果结点值与B树根结点的值相等则采用先序遍历进行比较
for(i = 1;i <= n;i++)
{
if(biTree[0][i].data == rootB -> data)
{
ifBTreeIsSubOfATree = true;
preOrderBinaryTree(&biTree[0][i],rootB);
if(true == ifBTreeIsSubOfATree)
{
return true;
}
}
}
return ifBTreeIsSubOfATree;
}
int main()
{
int n,m;
BinaryTreeNode * rootA; // 二叉树A的根结点
BinaryTreeNode * rootB; // 二叉树B的根结点
while(EOF != scanf("%d%d",&n,&m))
{
rootA = createBinaryTree(n,0);
rootB = createBinaryTree(m,1);
if(NULL == rootA || NULL == rootB)
{
printf("NO\n");
}
else
{
ifBTreeIsSubOfATree = isBTreeIsSubOfATree(rootA,rootB,n,m);
if(true == ifBTreeIsSubOfATree)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
return 0;
}
/**************************************************************
Problem: 1520
User: blueshell
Language: C++
Result: Accepted
Time:10 ms
Memory:1068 kb
****************************************************************/