1 题目描述
输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。
2 解法描述
- 遍历二叉树 A 找到与二叉树 B 根节点相同的 A 的子树 a 。
遍历子树 a 和 二叉树 B ,判断 a 和 B 是否存在一样结构的子树。
3 C 语言实现
#include<stdio.h>
// Tree
typedef char ElemType;
typedef struct node{
ElemType data;
struct node *lchild,*rchild;
}TNode,*Tree;
//创建二叉树
TNode* createTree(){
ElemType data;
scanf("%c",&data);
TNode* node;
if(data=='0') return NULL;
node=(TNode*)malloc(sizeof(TNode));
node->data=data;
node->lchild=createTree();
node->rchild=createTree();
return node;
}
/*
分两步解决问题
第一步,在待查二叉树 A 中,找到与 B 树根节点一样的节点 a
第二步,判断 a 节点下面的子树是否含有跟 B 一样的子树。
*/
int hasSubRoot(Tree tree1,Tree tree2){
int result=0;
if(tree1!=NULL&&tree2!=NULL){
if(tree1->data==tree2->data){
//进行第二步
result=tree1HasTree2(tree1,tree2);
}
if(!result){
//遍历左孩子
result=hasSubRoot(tree1->lchild,tree2);
}
if(!result){
//遍历右孩子
result=hasSubRoot(tree1->rchild,tree2);
}
}
return result;
}
//判断 a 节点下面的子树是否含有跟 B 一样的子树
int tree1HasTree2(TNode *tree1node,TNode *tree2node){
if(tree2node==NULL) return 1;
if(tree1node==NULL) return 0;
if(tree1node->data!=tree2node->data) return 0;
return(tree1HasTree2(tree1node->lchild,tree2node->lchild)&&
tree1HasTree2(tree1node->rchild,tree2node->rchild));
}
void main(){
Tree tree1;
tree1=NULL;
printf("%s:","请输入二叉树 Tree1 的元素");
tree1=createTree();
printf("\n");
getchar();
Tree tree2;
tree2=NULL;
printf("%s:","请输入二叉树 Tree2 的元素");
tree2=createTree();
if(hasSubRoot(tree1,tree2)){
printf("%s:","Tree1 是 Tree2 的一部分");
}else{
printf("%s:","Tree1 不是 Tree2 的一部分");
}
}
4 心得体会
- 关于二叉树的问题,要思考递归方式解决。