首页 > 其他分享 >【PTA】树的同构

【PTA】树的同构

时间:2024-10-27 15:17:22浏览次数:5  
标签:lchild 同构 结点 PTA 两棵树 root1 root2

题目描述

给定两棵树 T1​ 和 T2​。如果 T1​ 可以通过若干次左右孩子互换就变成 T2​,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。

fig1.jpg

图1

图2

现给定两棵树,请你判断它们是否是同构的。

输入格式

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

输出格式

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

输入样例1(对应图1)

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

输出样例1

Yes

输入样例2(对应图2)

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

输出样例2

No

代码长度限制:16 KB

时间限制:400 ms

内存限制:64 MB

栈限制:8192 KB

分析

        如果两棵树是同构的,可以通过若干次左右孩子互换将其中一棵树变成另一棵树。主要思想是通过递归比较两棵树的结构和节点数据来判断它们是否同构。

代码结构和思想

  1. 定义数据结构

    • 定义了一个 TreeNode 结构体,用于表示二叉树的节点。每个节点包含数据、左孩子和右孩子的索引。
    • 使用两个数组 tree1 和 tree2 分别存储两棵树的节点信息。
  2. 创建二叉树

    • CreatTree 函数读取输入数据并构建二叉树,返回根节点的索引。
    • 使用 check 数组记录每个节点是否是其他节点的孩子节点,以找到根节点。
  3. 判断同构性

    • Isomorphic 函数递归判断两棵树是否是同构的。
    • 通过比较根节点数据、左孩子和右孩子的数据来判断两棵树是否同构。

Isomorphic 函数递归判断两棵树是否是同构

  • 递归终止条件
    • 如果两棵树都为空,返回 true
    • 如果一棵树为空而另一棵树不为空,返回 false
    • 如果根节点数据不同,返回 false
  • 递归判断
    • 如果两棵树都没有左孩子,递归判断右子树是否同构。
    • 如果两棵树的左孩子数据相同,递归判断左子树和右子树是否同构。
    • 如果两棵树的左孩子数据不同,递归判断左右子树是否同构。

代码实现 

// Creator: Bonong
// Create Time: 2024/10/27 11:30
// Description: 树的同构

#include <iostream>
using namespace std;

#define maxSize 10

// 二叉树的结点
struct TreeNode{
    char data;
    int lchild, rchild;
} tree1[maxSize], tree2[maxSize];

// 创建二叉树
int CreateTree(TreeNode tree[]) {
    int n;
    cin >> n;
    if (n == 0) {
        return -1;
    }
    int root = -1; // 根结点
    int check[maxSize] = {0}; // 标记结点是否为根结点
    for (int i = 0; i < n; ++i) {
        char l, r;
        cin >> tree[i].data >> l >> r;
        if (l != '-') {
            tree[i].lchild = l - '0'; // 将字符转换为数字
            check[tree[i].lchild] = 1; // 标记结点lchild为非根结点
        } else {
            tree[i].lchild = -1; // 无左孩子
        }
        if (r != '-') {
            tree[i].rchild = r - '0'; // 将字符转换为数字
            check[tree[i].rchild] = 1; // 标记结点rchild为非根结点
        } else {
            tree[i].rchild = -1; // 无右孩子
        }
    }
    for (int i = 0; i < n; ++i) { // 找到根结点
        if (check[i] == 0) { 
            root = i; 
            break;
        }
    }
    return root;
}

// 判断两棵树是否同构
bool Isomorphic(int root1, int root2) {
    if (root1 == -1 && root2 == -1) { // 两棵树都为空
        return true;
    }
    if ((root1 == -1 && root2 != -1) || (root1 != -1 && root2 == -1)) { // 一棵树为空,另一棵树不为空
        return false;
    }
    if (tree1[root1].data != tree2[root2].data) { // 根结点数据不同
        return false;
    }
    if (tree1[root1].lchild == -1 && tree2[root2].lchild == -1) { // 两棵树都没有左孩子
        return Isomorphic(tree1[root1].rchild, tree2[root2].rchild); 
    }
    if ((tree1[root1].lchild != -1 && tree2[root2].lchild != -1) && 
        (tree1[tree1[root1].lchild].data == tree2[tree2[root2].lchild].data)) { // 左孩子的数据相同
        return Isomorphic(tree1[root1].lchild, tree2[root2].lchild) &&  // 递归判断左子树
               Isomorphic(tree1[root1].rchild, tree2[root2].rchild);
    } else { // 左右孩子的数据不同
        return Isomorphic(tree1[root1].lchild, tree2[root2].rchild) &&  // 递归判断左右子树
               Isomorphic(tree1[root1].rchild, tree2[root2].lchild);
    }
}

int main() {
    int root1 = CreateTree(tree1);
    int root2 = CreateTree(tree2);
    if (Isomorphic(root1, root2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

标签:lchild,同构,结点,PTA,两棵树,root1,root2
From: https://blog.csdn.net/2301_80216181/article/details/143269188

相关文章

  • PTA题目集1-3总结(22207331-张博文)
    总体情况预览:第一次:第二次:第三次:(1)前言:前三次作业题量适中,但是难度较大!题目集作业主要考察了以下知识点:一、基础语法1. 变量与数据类型:包括整型(int、long等)、浮点型(float、double)、字符型(char)、布尔型(boolean)等数据类型的定义和使用。2. 运算符:算术运算符(+、-、*、/、%......
  • 22207223-王颖对于编写pta答题判题程序的总结
    目录一、前言1.1知识点1.2题量1.3难度二、答题判题程序12.1设计与分析2.2踩坑心得2.3改进建议三、答题判题程序23.1设计与分析3.2踩坑心得3.3改进建议四、答题判题程序34.1设计与分析4.2踩坑心得4.3......
  • 南昌航空大学-软件学院-22207112-卢翔-JAVAPTA(1-3)博客
    目录前言PTA第一次作业(7-5答题判题程序-1)设计与分析题目分析知识点解析调试过程时序图,耦合度改进建议PTA第二次作业设计与分析题目分析知识点解析(不重复)调试过程类图,耦合度改进建议PTA第三次作业设计与分析题目分析知识点解析调试过程类图,耦合度改进建议踩坑心得总结前言本次的......
  • 在K8S中,Iptables 四表五链有哪些?
    在K8S中,iptables四表五链具体如下:四表:filter表:主要用于过滤数据包。它根据系统管理员预定义的一组规则对进入和离开系统的网络流量进行过滤。对于防火墙而言,主要利用在filter表中指定的规则来实现对数据包的过滤。Filter表是默认的表,如果没有指定哪个表,iptables就默认使......
  • pta答题判断程序总结blog
    一、前言本次blog是针对发布题目集1~3的的最后一题的总结。三次大作业都是模拟一个小型的在线测试系统,先由大作业1完成基本功能,后面进行迭代,不断增加功能,丰富功能。下面具体分析这三次大作业的关键点和区别。1、答题程序-11)输入:题目数量:首先输入题目数量。题目信息:按指定格式输......
  • PTA题目集1~3的总结
    一、前言7-1答题判题程序-1(1)知识点:字符串解析:使用正则表达式或字符串分割来解析输入的题目信息和答案。控制结构:使用循环结构来处理多个输入行。条件判断:根据标准答案判断答题结果。数据结构:使用数组或集合来存储题目信息和答案。(2)题量:输入题目数量。输入题目内容(包括题......
  • OO_PTA题目集1-3总结
    (1)前言前三次作业算是让我走上了写JAVA的正轨,题目小多,难度还可。初步学会了如何去写了类。题目内容主要涉及无参有参构造,排序查找,类的设计,常用系统类方法的使用等等,以及主要的答题判题程序的编写与迭代。在这三次作业里也算是初窥门槛了罢。(2)设计与分析第一次作业答题判题程序......
  • JAVA-PTA题目集总结
    一、 前言    经过Java题目集1-3的练习,我对Java编程有了更加深入的理解和掌握。题目集涵盖了Java基础语法、面向对象编程、集合框架等多个方面,题量适中,难度逐步上升,让我在挑战中不断成长。    三次训练的知识点涉及Java的基本语法,包括变量、数据类型、运算符、......
  • 中间人攻击(https降级攻击)和iptables命令分析
    中间人攻击以下是一个简单的中间人攻击示例,结合ARP欺骗和流量修改:1.进行ARP欺骗首先,使用 arpspoof 进行ARP欺骗,将受害者的流量重定向到攻击者的机器上:sudoarpspoof-ieth0-t172.29.144.50172.29.144.12.启用IP转发确保IP转发已启用,以便攻击者可以将......
  • Java复习16(PTA)
    快递计价器分数20全屏浏览切换布局作者 大数据2021单位 山东科技大学现需要编写一个简易快递计价程序。具体来说:1、抽象快递类Express,其包含一个属性intweight表示快递重量(单位为kg),一个方法getWeight()用于返回快递重量和一个抽象方法getTotal()用于计算快递运费......