面试题 18

1 题目描述

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

2 解法描述

1. 遍历二叉树 A 找到与二叉树 B 根节点相同的 A 的子树 a 。

2. 遍历子树 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 心得体会

1. 关于二叉树的问题，要思考递归方式解决。