(浙大陈越版)数据结构 第三章 树(上) 3.4 小白专场:树的同构(PTA编程题讲解)

news/2024/5/19 1:22:48/

题意理解和二叉树表示

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

eg1:现请你判断如下两棵树(左侧为T1,右侧为T2)是否为同构树?

显然T1可以通过有限次左右孩子互换变成T2,因此这两棵树是同构的

eg2:同上

这两棵树BC子树的子结点完全不同,T1不能互换变成T2,所以不是同构

程序题目:输入两颗二叉树的信息,判断两棵树是否为同构。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数N (≤10),即该树的结点数(此时假设结点从0到N−1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的,输出“Yes”,否则输出“No”。

解题思路

本题需要解决三个问题:

二叉树如何表示

一般使用链表或者数组。之前的文章提到可以使用含有一个数据域和两个指针域(一个left一个right)的结构链表来表示二叉树。或者是将二叉树视为满二叉树,无结点的地方留空,用数组表示。

讲解中使用了结构数组,又称静态链表。简单来说是将基本信息存放在数组当中,左右子树用类似链表的方式来表示。例如下面的图中二叉树使用二维数组分别存储结点位置、左右子树位置

 对应结构的代码:

#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1    //传统空指针是0,而0会和下标冲突
struct TreeNode{ElementType Element;    Tree Left;Tree Right;
} T1[MaxTree], T2[MaxTree];

如何构造二叉树

如何从输入的若干数据中建立对应的二叉树?

程序框架搭建

int main()
{Tree R1, R2;R1 = BuildTree(T1);R2 = BuildTree(T2);if (Isomorphic(R1, R2)) printf("Yes\n");else printf("No\n");return 0;
}

Tree BuildTree( struct TreeNode T[] ){scanf("%d\n", &N);if (N) {//设定check来判别指向,首先都设为0for (i=0; i<N; i++){check[i] = 0;}for (i=0; i<N; i++) {//循环读入每个结点该有的三个信息scanf("%c %c %c\n", &T[i].Element, &cl, &cr);//若有结点A指向B,就将B的check设为1if (cl != '-') {//题目中设定为-的是没有左子树的T[i].Left = cl-'0';check[T[i].Left] = 1;}else T[i].Left = Null;…….. /*对cr的对应处理 */}//遍历结点找根结点,根结点是唯一一个没有被指向的结点,check值=0for (i=0; i<N; i++)if (!check[i]) break;Root = i;}return Root;
}

同构的判定

int Isomorphic ( Tree R1, Tree R2 )
{ //首先判断两棵树的边界情况/*都是空树*/if ( (R1==Null )&& (R2==Null) ) return 1;/*有一颗是空树*/if ( ((R1==Null)&&(R2!=Null)) || ((R1!=Null)&&(R2==Null)) )return 0; /*根结点不同,肯定不是同构*/if ( T1[R1].Element != T2[R2].Element )return 0;/*两棵树都没有左子树,只判断右子树*/if ( ( T1[R1].Left == Null )&&( T2[R2].Left == Null ) ) return Isomorphic( T1[R1].Right, T2[R2].Right );/*是否有一颗及以上有左子树,左子树结点数据是否一致*/if ( ((T1[R1].Left!=Null)&&(T2[R2].Left!=Null))&&((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)) ) /*判断左子树是否相等、右子树是否相等*/return ( Isomorphic( T1[R1].Left, T2[R2].Left ) &&Isomorphic( T1[R1].Right, T2[R2].Right ) );/*可能是A左和B右同构,交换左右子树后判别*/elsereturn ( Isomorphic( T1[R1].Left, T2[R2].Right) &&Isomorphic( T1[R1].Right, T2[R2].Left ) );}


http://www.ppmy.cn/news/105363.html

相关文章

nSoftware IPWorks 2022 C++ Crack

nSoftware IPWorks 2022 C最全面的互联网组件套件&#xff0c;PKI 代理远程签署代码和文档&#xff0c;无需暴露您的私钥&#xff0c;一种安全的自托管解决方案&#xff0c;可使用集中存储的密钥实现远程代码和文档签名&#xff0c;随附的 PKCS#11 驱动程序允许与 Jarsigner、S…

git的本地分支如何关联远程分支,比如github,gitlab,码云等

文章目录 1. 文章引言2. 本地分支如何关联远程分支2.1 远程有分支2.2 远程无分支 3. 总结 1. 文章引言 今天发布某版本的项目&#xff0c;准备创建个v0point1分支&#xff0c;后期如果修改该版本&#xff0c;直接在该分支上修改即可。 首先&#xff0c;使用git branch v0point…

多线程屏障CyclicBarrier

文章目录 前言一、CyclicBarrier可以做什么&#xff1f;二、使用步骤1 单参数CyclicBarrier2 多参数 CyclicBarrier3 与CyclicBarrier类似的Exchanger 总结 前言 多线程中的CyclicBarrier,同样也是juc包下的一个工具类; 一、CyclicBarrier可以做什么&#xff1f; CyclicBarri…

ajax总结

Ajax 介绍 Ajax&#xff08;Asynchronous javaScript XML&#xff09;是一种异步处理数据的技术&#xff0c;用于创建快速动态网页&#xff0c;通过在后台与服务器进行少量数据交换&#xff0c;Ajax可以使网页实现异步更新&#xff0c;这意味着可以在不重新加载整个网页的情况…

MyBatis缓存和二级缓存整合Redis

MyBatis缓存和二级缓存整合Redis ⼀级缓存缓存验证在⼀个sqlSession中&#xff0c;对user表根据username进⾏两次查询&#xff0c;查看他们发出sql语句的情况同样是对user表进⾏两次查询&#xff0c;只不过两次查询之间进⾏了⼀次update操作。总结 ⼀级缓存原理探究与源码分析 …

SeaFormer实战:使用SeaFormer实现图像分类任务(一)

文章目录 摘要安装包安装timm安装mmcv安装 grad-cam 数据增强Cutout和MixupEMA项目结构计算mean和std生成数据集 摘要 论文翻译&#xff1a;https://blog.csdn.net/m0_47867638/article/details/130437649?spm1001.2014.3001.5501 官方源码&#xff1a;https://github.com/fu…

计算机网络第一章(谢希仁第8版学习)

作者&#xff1a;爱塔居 专栏&#xff1a;计算机网络 作者简介&#xff1a;大三学生&#xff0c;希望和大家一起加油 文章目录 目录 文章目录 一、网络、互连网、互联网&#xff08;因特网&#xff09;的概念 二、因特网的组成 三、交换方式 3.1 电路交换 3.2 分组交换 3.3 电路…

C#,码海拾贝(28)——求解“对称正定方程组”的“平方根法”之C#源代码,《C#数值计算算法编程》源代码升级改进版

using System; namespace Zhou.CSharp.Algorithm { /// <summary> /// 求解线性方程组的类 LEquations /// 原作 周长发 /// 改编 深度混淆 /// </summary> public static partial class LEquations { /// <summary> /…

ARM微架构与程序编写

目录 1.流水线 2.指令流水线 3. 多核处理器​编辑 4. 工程搭建 4.1为Keil软件配置编译工具链 5.程序编写 5.1 数据处理指令 5.2 带标志位的加法ADC ADDS 5.3 跳转指令B\BL 5.4 单寄存器内存访问 5.5 批量寄存器内存访问 5.6 满减操作 1.流水线 2.指令流水线 3.…

最高减持近9%,减持公告密集来袭

5月29日&#xff0c;今日晚间&#xff0c;又一波密集减持公告来袭&#xff0c;截至发稿披露减持公告的上市公司已超十余家&#xff0c;其中不乏CPO概念大牛股。 2只CPO概念大牛股遭减持 在今日晚间的密集减持公告中&#xff0c;光库科技、天孚通信2只CPO概念大牛股在列&#…

SpringBoot中MySQL连接字符串配置

SpringBoot中MySQL连接字符串配置样例&#xff1a; spring:datasource:url: jdbc:mysql://localhost:3306/<database_name>?useSSLfalse&allowPublicKeyRetrievaltrue&serverTimezoneUTC&characterEncodingUTF-8username: rootpassword: rootdriver-class-…

【vue中路由的使用】

【vue中路由的使用】 什么是路由后端路由&#xff1a;前端路由&#xff1a; 路由的基本使用路由的跳转组件的嵌套路由重定向选中路由高亮代码解析 什么是路由 后端路由&#xff1a; 对于普通的网站&#xff0c;所有的超链接都是URL地址&#xff0c;所有的URL地址都对应服务器…

java设计模式之模板方法设计模式的前世今生

模板方法设计模式是什么&#xff1f; 模板方法设计模式是一种行为型设计模式&#xff0c;它定义一个操作中的算法的骨架&#xff0c;而将一些步骤延迟到子类中完成。这种模式将某个算法的不同部分分别定义在不同的类中&#xff0c;并且保证这些类之间协同工作来完成整个算法。…

C/S客户端核服务端-简单收发

一、程序 首先上程序 client端的程序 #include <arpa/inet.h> #include <netinet/in.h> #include <netinet/ip.h> #include <stdio.h> #include <stdlib.h> #include <strings.h> #include <sys/socket.h> #include <sys/type…

什么是死锁?互斥锁进入死锁怎么解决?

1.死锁是什么&#xff1f; &#xff08;1&#xff09;死锁是一组相互竞争资源的线程因为他们之间得到互相等待导致“永久“阻塞的现象&#xff1b; &#xff08;你等我 我等你 你不放我也不放 就导致“永久“阻塞的现象&#xff09; &#xff08;2&#xff09;死锁是指两个或…

python:绘制GAM非线性回归散点图和拟合曲线

作者&#xff1a;CSDN _养乐多_ 本文将介绍使用python语言绘制广义线性模型&#xff08;Generalized Additive Model&#xff0c;GAM&#xff09;非线性回归散点图和拟合曲线。并记录了计算RMSE、ubRMSE、R2、Bias的代码。 文章目录 一、GAM非线性回归详解二、代码三、计算RM…

【IIS建站教程】windows本地搭建web服务,内网穿透发布公网访问

文章目录 1.前言2.Windows网页设置2.1 Windows IIS功能设置2.2 IIS网页访问测试 3. Cpolar内网穿透3.1 下载安装Cpolar3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5.结语 转载自远程源码文章&#xff1a;【IIS搭建网站】本地电脑做服务器搭建web站点并公网访问「内网…

数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)

目录 题目描述 输入示例 输出示例 解题思路 解题方法&#xff08;C语言&#xff09; 解析 题目描述 有序的二叉树遍历可以用堆栈以非递归的方式实现。 例如&#xff1a; 假设遍历一个节点数为6的二叉树&#xff08;节点数据分别为1到6&#xff09;时&#xff0c; 堆…

剑指 Offer 25. 合并两个排序的链表

&#x1f680; 作者简介&#xff1a;一名在后端领域学习&#xff0c;并渴望能够学有所成的追梦人。 &#x1f681; 个人主页&#xff1a;不 良 &#x1f525; 系列专栏&#xff1a;&#x1f6f8;剑指 Offer &#x1f4d5; 学习格言&#xff1a;博观而约取&#xff0c;厚积而薄…

vite构建的项目如何修改element Plus的主题样式

安装element plus 安装icon pnpm install element-plus pnpm install element-plus/icons-vue main.ts配置 icon的使用https://element-plus.gitee.io/zh-CN/component/icon.html#%E7%BB%93%E5%90%88-el-icon-%E4%BD%BF%E7%94%A8 import { createApp } from vue import ./sty…