当前位置: 首页 > news >正文

【王道数据结构】【chapter5树与二叉树】【P159t16】

试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似,指的是T1和T2都是空的二叉树或都只有一个根节点;或者T1的左子树和T2的左子树是相似的,且T1的右子树和T2的右子树是相似的

#include <iostream>
#include <stack>
#include <queue>
typedef struct treenode{char data;struct treenode *left;struct treenode *right;
}treenode,*ptreenode;ptreenode buytreenode(char x)
{ptreenode n=(ptreenode) malloc(sizeof (treenode));n->data=x;n->left= nullptr,n->right= nullptr;return n;
}
ptreenode build_tree1()
{ptreenode root= buytreenode('A');root->left= buytreenode('B');root->right= buytreenode('C');root->left->left= buytreenode('D');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');return root;
}ptreenode build_tree2()
{ptreenode root= buytreenode('A');root->left= buytreenode('B');root->right= buytreenode('C');root->left->left= buytreenode('D');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');root->left->right->left= buytreenode('J');root->left->right->right= buytreenode('K');root->right->left->left= buytreenode('L');root->right->left->right= buytreenode('M');root->right->right->left= buytreenode('N');root->right->right->right= buytreenode('O');return root;
}ptreenode build_tree3()
{ptreenode root= buytreenode('Z');root->left= buytreenode('Y');root->right= buytreenode('W');root->left->left= buytreenode('X');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');root->left->right->left= buytreenode('J');root->left->right->right= buytreenode('K');root->right->left->left= buytreenode('L');root->right->left->right= buytreenode('M');root->right->right->left= buytreenode('N');root->right->right->right= buytreenode('O');return root;
}
void print_tree(ptreenode root) {std::queue<ptreenode> tmp;tmp.push(root);int s = tmp.size();while (!tmp.empty()) {ptreenode t = tmp.front();tmp.pop();s--;printf("%3c", t->data);if (t->left) tmp.push(t->left);if (t->right) tmp.push(t->right);if (s == 0) puts(""), s = tmp.size();}
}bool isSimilar(ptreenode root1,ptreenode root2)
{if(root1== nullptr&&root2== nullptr) return true;if(root1== nullptr||root2== nullptr) return false;return isSimilar(root1->left,root2->left)&& isSimilar(root1->right,root2->right);
}
int main() {ptreenode root1=build_tree1();ptreenode root2=build_tree2();ptreenode root3=build_tree3();printf("tree1:\n");print_tree(root1);printf("tree2:\n");print_tree(root2);printf("tree3:\n");print_tree(root3);if(isSimilar(root1,root2)) printf("tree1 and tree2 are similar");else printf("tree1 and tree2 are different\n");if(isSimilar(root2,root3)) printf("tree2 and tree3 are similar");else printf("tree2 and tree3 are different");return 0;
}

相关文章:

【王道数据结构】【chapter5树与二叉树】【P159t16】

试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似&#xff0c;指的是T1和T2都是空的二叉树或都只有一个根节点&#xff1b;或者T1的左子树和T2的左子树是相似的&#xff0c;且T1的右子树和T2的右子树是相似的 #include <iostream> #include <stack> #inc…...

代码随想录算法训练营第51天 | 139.单词拆分 多重背包理论基础

单词拆分 这道题最后是判断能否组成&#xff0c;很像回溯法的问题形式&#xff0c;和分割回文串那道题比较类似&#xff0c;所以是可以用回溯法解决的&#xff0c;但是回溯法需要使用记忆化递归来避免超时。 class Solution{ public:bool backtracking(const string s, const …...

weilai8游戏爬虫

#!/usr/bin/python # -*- coding: UTF-8 -*- #!/usr/bin/python # -*- coding: UTF-8 -*- import os,csv import re import random import time import requests from lxml import etreefrom urllib.parse import quote, unquotepage98 sess requests.Session()#创建一个sessi…...

【Java程序设计】【C00261】基于Springboot的休闲娱乐代理售票系统(有论文)

基于Springboot的休闲娱乐代理售票系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的休闲娱乐代理售票系统 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块&#xff1a;休闲娱乐代理…...

【Linux】学习-基础IO拓展篇

Linux基础IO拓展篇—详解文件系统 理解文件系统 在Linux基础IO篇中&#xff0c;我们站在用户的视角对文件进行了理解&#xff0c;主要是针对被打开的文件&#xff0c;那么有没有没有被打开的文件呢&#xff1f;当然有&#xff01;今天我们换个视角&#xff0c;来站在系统的角…...

算法详解(力扣141——环形链表系列)

博主ID&#xff1a;代码小豪 文章目录 环形链表环形链表的性质分析快慢指针法指针的追及相遇问题 环形链表&#xff08;2&#xff09; 环形链表 先来看看环形链表的原题&#xff1a; 中间的部分叙述有点繁杂&#xff0c;简单来概括就是&#xff0c;假如有一个节点&#xff0c…...

浅谈路由器交换结构

一、路由器技术概述 路由器&#xff08;Router&#xff09;是连接两个或多个网络的硬件设备&#xff0c;在网络间起网关的作用&#xff0c;是读取每一个数据包中的地址然后决定如何传送的专用智能性的网络设备。它能够理解不同的协议&#xff0c;例如某个局域网使用的以太网协议…...

Linux第51步_移植ST公司的linux内核第3步_添加修改设备树

1、设备树文件的路径 1)、创建linux中的设备树头文件 在“my_linux/linux-5.4.31/arch/arm/boot/dts/”目录中&#xff0c;以“stm32mp15xx-edx.dtsi”为蓝本&#xff0c;复制一份&#xff0c;并命名为 “stm32mp157d-atk.dtsi”&#xff0c;这就是我们开发板的设备树头文件。…...

【PyTorch】PyTorch中张量(Tensor)统计操作

PyTorch深度学习总结 第五章 PyTorch中张量(Tensor)统计操作 文章目录 PyTorch深度学习总结前言一、最值查找二、特殊值查询 前言 上文介绍了PyTorch中张量(Tensor)的计算操作&#xff0c;本文将介绍张量的统计操作。 一、最值查找 函数描述torch.max()找出张量中的最大值to…...

安卓游戏开发框架应用场景以及优劣分析

一、引言 在移动游戏开发领域&#xff0c;选择合适的开发框架是项目成功的关键因素之一。特别是对于安卓平台&#xff0c;由于其开放性和庞大的用户基础&#xff0c;不同的游戏开发框架应运而生&#xff0c;旨在帮助开发者高效地构建游戏应用。以下是一些流行的安卓游戏开发框架…...

单片机学习笔记---LCD1602

LCD1602介绍 LCD1602&#xff08;Liquid Crystal Display&#xff09;液晶显示屏是一种字符型液晶显示模块&#xff0c;可以显示ASCII码的标准字符和其它的一些内置特殊字符&#xff08;比如日文的片假名&#xff09;&#xff0c;还可以有8个自定义字符 显示容量&#xff1a;…...

django中实现适配器模式

在Django中实现适配器模式&#xff08;Adapter Pattern&#xff09;涉及到创建一个适配器类&#xff0c;它允许不兼容的接口之间进行交互。适配器模式通常用于将一个类的接口转换为另一个客户端期望的接口。 一&#xff1a;实现例子 下面是一个简单的例子&#xff0c;演示如何…...

题记(42)--EXCEL排序

目录 一、题目内容 二、输入描述 三、输出描述 四、输入输出示例 五、完整C语言代码 一、题目内容 Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 对每个测试用例&#xff0c;首先输出1行“Case i:”&#xff0c;其中 i 是测试用例的编号&#…...

【学网攻】 第(28)节 -- OSPF虚链路

系列文章目录 目录 系列文章目录 文章目录 前言 一、什么是OSPF虚链路&#xff1f; 二、实验 1.引入 实验目标 实验背景 技术原理 实验步骤 实验设备 实验拓扑图 实验配置 扩展 实验拓扑图 实验配置 实验验证 文章目录 【学网攻】 第(1)节 -- 认识网络【学网攻…...

百面嵌入式专栏(面试题)驱动开发面试题汇总1.0

沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇我们将介绍驱动开发面试题 。 1、Linux驱动程序的功能是什么? 对设备初始化和释放。进行内核与硬件的数据交互。检测和处理设备出现的错误。2、内核程序中申请内存使用什么函数? 答案:kmalloc()、kzalloc()、vm…...

Starknet 的 JavaScript 库:Starknet.js、get-starknet和starknet-react

文章目录 Starknet 的 JavaScript 库Starknet.jsget-starknetstarknet-reactStarknet 的 JavaScript 库Starknet.js 官方:https://www.starknetjs.com/ Starknet.js 是一个与 Starknet 交互的 JavaScript 库,通常以脚本或去中心化形式进行交互应用程序。 Starknet.js 的灵感…...

debian11 安装 k8s,containerd ,阿里云镜像(已成功)

1. 环境准备 系统要求&#xff1a;至少 2GB RAM&#xff08;建议 4GB 或更多&#xff09;&#xff0c;网络连接。 节点准备&#xff1a;至少 3 台机器&#xff0c;1 台作为 Master 节点&#xff0c;2 台作为 Worker 节点。 安装sudo apt update apt install sudo设置主机名&a…...

Spring Task定时任务

目录 1、介绍 2、cron表达式 2.1、在线生成器 2.2、通配符 3、代码示例 3.1、使用步骤 3.2、 代码开发 3.3、测试 &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;专注于Java领域学习&#xff0c;擅长web应用开发…...

【设计模式】23中设计模式笔记

设计模式分类 模板方法模式 核心就是设计一个部分抽象类。 这个类具有少量具体的方法&#xff0c;和大量抽象的方法&#xff0c;具体的方法是为外界提供服务的点&#xff0c;具体方法中定义了抽象方法的执行序列 装饰器模式 现在有一个对象A&#xff0c;希望A的a方法被修饰 …...

类加载过程介绍

一、类的生命周期 类被加载到jvm虚拟机内存开始&#xff0c;到卸载出内存为止&#xff0c;他的生命周期可以分为&#xff1a;加载->验证->准备->解析->初始化->使用->卸载。 其中验证、准备、解析统一称为链接阶段 1、加载 将类的字节码载入方法区中&#xf…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...