树的同构

树的同构同构的定义:给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。更加具体的理解为:两棵树中的每两个对应结点的孩子必须相同,左右位置可不一样。树的存储结构

大家好,又见面了,我是你们的朋友全栈君。

同构的定义:给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。

更加具体的理解为:两棵树中的每两个对应结点的孩子必须相同,左右位置可不一样。

树的存储结构:结构数组。链表在对输入进行存储时没有数组方便。

如:输入如下样例后结构数组内容

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -

<span role="heading" aria-level="2">树的同构

要注意第一个输入的不一定是根结点,没有父亲的结点才是根结点。

定义:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxTree 10
#define ElementType char
#define Tree int 
#define Null -1

struct TreeNode {
    ElementType Data;
    Tree left;
    Tree right;
}T1[MaxTree],T2[MaxTree];

Tree Initial(struct TreeNode T1[]);
int Judge(Tree rt1, Tree rt2);

T1,T2为全局数组。

建立二叉树:

Tree Initial(struct TreeNode T[]) {
    int N;
    if(scanf("%d",&N)==1){}
    if (N == 0) {
        return -1;
    }
    int i;
    char c1, c2;
    int flag[MaxTree];
    memset(flag, 0, sizeof(int) * MaxTree);
    getchar();
    for (i = 0;i < N;i ++ ) {
        /*cin >> T[i].Data;
        cin >> c1 >> c2;*/
        if(scanf("%c %c %c",&T[i].Data,&c1,&c2)==3){}
        //T[i].Data=getchar();
        getchar();
        /*c1= getchar();
        getchar();
        c2= getchar();
        getchar();*/
        if (c1 == '-')
            T[i].left = Null;
        else {
            T[i].left = c1 - '0';
            flag[T[i].left] = 1;
        }
        if (c2 == '-')
            T[i].right = Null;
        else {
            T[i].right = c2 - '0';
            flag[T[i].right] = 1;
        }
    }
    for (i = 0;i < N;i++) {
        if (flag[i] == 0)
            break;
    }
    Tree root = i;
    return root;
}

判断是否同构,这里很绕:

int Judge(Tree rt1, Tree rt2) {
    if (rt1 == Null && rt2 == Null)
        return 1;
    if ((rt1 == Null && rt2 != Null) || (rt1 != Null && rt2 == Null))
        return 0;
    if (T1[rt1].Data != T2[rt2].Data)
        return 0;
    if (T1[rt1].left == Null && T2[rt2].left == Null)
        return Judge(T1[rt1].right, T2[rt2].right);
    if (T1[rt1].left != Null && T2[rt2].left != Null && T1[T1[rt1].left].Data == T2[T2[rt2].left].Data)
        return (Judge(T1[rt1].left, T2[rt2].left) && Judge(T1[rt1].right, T2[rt2].right));
    else
        return (Judge(T1[rt1].left, T2[rt2].right) && Judge(T1[rt1].right, T2[rt2].left));
}

前三个if是递归到最简的情况,可以直接判断返回,后面则需要递归。

main:

int main() {
    Tree t1 = Initial(T1);
    Tree t2 = Initial(T2);
    //test(t1);
    if (Judge(t1, t2))
        printf("Yes");
    else
        printf("No");
    return 0;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155138.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • LLDP协议原理

    LLDP协议原理目录LLDP概念LLDP报文LLDP工作原理1、LLDP概念LLDP(LinkLayerDiscoveryProtocol,链路层发现协议)。LLDP定义在802.1ab中,它是一个二层协议,它提供了一种标准的链路层发现方式。LLDP协议使得接入网络的一台设备可以将其主要的能力,管理地址,设备标识,接口标识等信息发送给接入同一个局域网络的其它设备。当一个设备从网络中接收到其它设备的这些信息时,它就将这些信息以MIB的形式存储起来。 这些MIB信息可用于发现设备的物理拓扑结构以及管理配置信息。

  • pycharm add configuration怎么配置_pycharm配置教程

    pycharm add configuration怎么配置_pycharm配置教程一、虚拟环境的配置1、进入Pycharm的设置页面,找到自己的项目,点击右上侧的‘Add’按钮,进行添加。2、进入添加页面,选择已存在的虚拟环境,点击右侧按钮进行添加3、选择你所需要的虚拟环境,进行添加,最后点击‘OK’。4、添加成功之后,会生成如图所示的地址,点击‘Apply’,再点击‘OK’即可。二、配置所需环境变量1、点击‘Run’,找到‘EditConfigurati…

  • 用C#编程的建议建议收藏

    1.如果可能尽量使用接口来编程.NET框架包括类和接口,在编写程序的时候,你可能知道正在用.NET的哪个类。然而,在这种情况下如果你用.NET支持的接口而不是它的类来编程时,代码会变得更加稳定、可用

    2021年12月21日
  • Pytest(1)安装与入门[通俗易懂]

    Pytest(1)安装与入门[通俗易懂]pytest介绍pytest是python的一种单元测试框架,与python自带的unittest测试框架类似,但是比unittest框架使用起来更简洁,效率更高。根据pytest的官方网站介绍,它

  • Tomcat下的appBase和docBase[通俗易懂]

    我们先看appBase,这个目录表示:1这个目录下面的子目录将自动被部署为应用。2这个目录下面的.war文件将被自动解压缩并部署为应用而docBase只是指向了你某个应用的目录,这个可以和appBase没有任何关系。总结:如果你想自己指定路径,那么应该在docBase里面如果你想简单,那么直接把他们复制到appBase下面就行了如果你把他们弄重复了,也就是2个指向了

  • datagrid激活码_在线激活

    (datagrid激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/ide…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号