面试题目：输入两颗二叉树A，B，判断B是不是A的子结构；
#include#include using namespace std;typedef struct BinaryTreeNode{ int value; BinaryTreeNode * lchild; BinaryTreeNode *rchild;}BinaryTreeNode;typedef BinaryTreeNode * BiTree;void CreateBiTreeByLevel(BiTree &t,int Array[],int i,int len){ if(Array[i]==0||i > len) return; t = new BinaryTreeNode; t->value = Array[i]; t->lchild = NULL; t->rchild = NULL; CreateBiTreeByLevel(t->lchild,Array,2*i,len); CreateBiTreeByLevel(t->rchild,Array,2*i+1,len);}void display(BiTree *t) //显示树形结构 { if(*t!=NULL) { cout<<(*t)->value; if((*t)->lchild!=NULL) { cout<<'('; display(&(*t)->lchild); } if((*t)->rchild!=NULL) { cout<<','; display(&(*t)->rchild); cout<<')'; } }}bool ifTheSameTree(BiTree &t1,BiTree &t2){ if (t2 == NULL)return true;//B树为空，肯定是相同的树 if(t1 == NULL)return false; if (t1->value!=t2->value)return false;//节点不同，不是 else { return ifTheSameTree(t1->lchild,t2->lchild) & ifTheSameTree(t1->rchild,t2->rchild);//左右均为true返回true }}bool isSubBinTree(BiTree &t1,BiTree &t2){ bool result = false; if(t1 != NULL && t2 != NULL) { if (t1->value == t2->value)//根节点相同，就判断A，B树是否一样 { result = ifTheSameTree(t1,t2); } if(!result)result = isSubBinTree(t1->lchild,t2);//判断左子树 if (!result) result = isSubBinTree(t1->rchild,t2);//判断右子树 } return result;}int main(){ BiTree A,B; //InitBiTree(&T); int a[14] = {0,1,2,3,4,5,6,0,0,0,7,0,8,9};//从下标1开始，0标识没有节点 int b[4] = {0,6,8,9}; CreateBiTreeByLevel(A,a,1,13); CreateBiTreeByLevel(B,b,1,2); display(&A); display(&B); if(isSubBinTree(A,B))cout<<"B is A subTree"; else cout<<"B is Not A subTree"; system("pause");}
来源：