面试题 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. 关于二叉树的问题,要思考递归方式解决。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值