挑战30天C++基本入门(DAY8--树)[part 3](速通哦~)
#上一章我们把搜索二叉树的知识给传授完毕,如果认真的看下去并且手打了几遍,基本上内部的逻辑还是可以理解的,那我们现在就截至继续学习树的一些重要知识啦~~
树高怎么求呀?如果用上一次学的层次遍历来求树高,有点小题大做了,这章我们就教大家如何用递归来求树高。
如何查找树里的元素呢??
哈夫曼树是个啥子??
在这一章节我都会很细致的给大家说明啦~
树高咋求???
🤔我们现在掌握的方法只有层次遍历来求树高,那我们怎么用递归来求树高呢???
我们现在先拿最极端情况来说明,如果一棵树没有一个元素,那我们的树高是不是为0,这样来看,我们的终止条件就找到啦!,没错就是当根节点为空的是后,我们就返回0;
我们的树高应该看最长的一部分,那我们就应该先定义两个高度,一个是左子树高度,另一个是右子树高度,之后我们比较左子树高度和右子树高度哪个高,哪个高哪个就决定了树高,因为左子树和右子树都是从第二层开始才有的,所以我们最后返回的树高应该让左右子树+1。
这样来看我们大概的逻辑不就出来了嘛?
先写一个极端判断条件,然后比较左右子树高度即可。
int treeheight(treenode* root)
{if(root==NULL)return 0;int lh=treeheight(root->lchild);int rh=treeheight(root->rchild);return lh>rh?lh+1:rh+1;
}
这样看来是不是还挺简单嘞,嘿嘿。
那我们接着来下面的知识,如何查找元素嘞?
怎么查找树里面的元素???
查找的话,我们大概想一下就知道要用bool函数来判断啦,在这个结构中,我们首先要把根节点和查找的元素定义起来。
我们怎么查找呢?肯定也是一层一层查找,如果一棵树都查完了也没找的这个元素,那我们就可以说这棵树没有这个元素。
由此我们可以得到我们判断结束的条件,当树不为空时候,我们就循环;如果为空,我们就结束判断。
代码部分也是很简单,如下:
bool find(treenode* root,int target)
{while(root){if(root->value==target)return 1;if(root->value<target)root=root->lchild;if(root->value>target)root=root->rchild;}
}
由以上内容,和之前的文章,我们现在掌握了如何构建查找二叉树,如何前中后序遍历,如何层次遍历,如何求树高,如何查找元素,二叉树中基本的知识,我们大概已经学完啦,下面我们来认识一个重要的树,哈夫曼树。
哈夫曼树
定义:
我们首先了解哈夫曼树的定义:
对于哈夫曼树,我们的权值只有叶子结点!!
性质:
1.权值越大的叶子节点越靠近根节点
2.权值越小的叶子节点越远离根节点
3.哈夫曼树并不唯一
4.哈夫曼树的子树也是哈夫曼树
5.哈夫曼树无度为1的结点
这些性质也是比较好看出来的,在这里就不多余赘述啦~
哈夫曼树的构建:
结点的不同:
在我们构建搜索二叉树时候,我们初始将左右子树设置为空,但是在我们的哈夫曼树的初始化时,我们应该将左右子树保留。
如下:
struct treenode{int weight;treenode* lchild;treenode* rchild;treenode(int v,treenode* l,treenode* r){weight=v,lchild=l,rchild=r;}
};
因为我们左右孩子会构造出来我们的根节点,所以左右孩子这里不为空。
构建过程:
1.我们首先要把每个节点初始化,之后push进我们的vector里面
2.定义左孩子,右孩子,根节点三个变量
3.对元素进行降序排列,之后再弹出最后两个元素,同时利用最后两个元素构建出我们的父节点。
(此时的父节点需要new来开辟空间)。
过程也相对容易,接下来是代码部分:
void build(vector<int> a){vector<treenode*>b;for(int i=0;i<a.size();i++){treenode* tmp=new treenode(a[i],NULL,NULL);b.push_back(tmp);}treenode* l=NULL,*r=NULL,*p=NULL;while(b.size()>1){sort(b.begin(),b.end(),[=](treenode* a,treendoe* b){return a->weight>b.weight;});l=b[b.size()-1];b.pop_back();r=b[b.size()-1];b.pop_back();p=new treenode(l->weight+r->weight,l,r);}return p;
}
求WPL
怎么求wpl呢?这里就用到了我们之前学的层次遍历啦。
我们首先层次遍历,判断结点是否没有左右孩子,这样就能找到我们的叶子节点,然后乘以我们的层次-1,如此加和进去就可以得到我们的wpl啦
void layersearch(treenode* root)
{queue<treenode*>q;q.push(root);treenode* last=root;treenode* nlast=NULL;while(!q.empty()){treenode* tmp=q.front();cout<<tmp->weight;if(tmp->lchild==NULL&&tmp->rchild==NULL){wpl+=tmp->weight*L;}q.pop();if(tmp->lchild==NULL){q.push(tmp->lchild);nlast=tmp->lchild;}if(tmp->rchild==NULL){q.push(tmp->rchild);nlast=tmp->rchild;}if(tmp==last){cout<<endl;L++;last=nlast;}}}
//以上就是我们树里面残留的问题啦,一些基本的原理和代码部分我都有提到,在这里还得看大家自己下去的实践能力,多打代码,才能更透彻的了解,理解底层逻辑。
如果我的文章对对大家有帮助的作用,希望大家多多支持哦~~(谢谢大家的点赞关注啦~)
阿里嘎多everybody~
相关文章:
挑战30天C++基本入门(DAY8--树)[part 3](速通哦~)
#上一章我们把搜索二叉树的知识给传授完毕,如果认真的看下去并且手打了几遍,基本上内部的逻辑还是可以理解的,那我们现在就截至继续学习树的一些重要知识啦~~ 树高怎么求呀?如果用上一次学的层次遍历来求树高,有点小题…...
在虚拟机尝试一次用启动盘重装系统
在虚拟机尝试一次用启动盘重装系统 没有自己重装过系统,也不敢对自己的笔记本下手,用虚拟机重装玩玩试试。 先设置成u盘启动 从boot中选择相应的创建的硬盘即可(刚刚突然发现图片不能上传了,经过乱七八糟的尝试后,开一…...
力扣347. 前 K 个高频元素
思路:记录元素出现的次数用map; 要维护前k个元素,不至于把所有元素都排序再取前k个,而是新建一个堆,用小根堆存放前k个最大的数。 为什么是小根堆?因为堆每次出数据时只出堆顶,每次把当前最小的…...
SCP 从Linux快速下载文件到Windows本地
需求:通过mobaxterm将大文件拖动到windows本地速度太慢。 环境:本地是Windows,安装了Git。 操作:进入文件夹内,鼠标右键,点击Git Bash here,然后输入命令即可。这样的话,其实自己本…...
plasmo内容UI组件层级过高导致页面展示错乱
我使用plasmo写了一个行内样式的UI组件,但是放到页面上之后,会和下拉组件出现层级错乱,看了一下样式,吓我一跳:层级竟然设置的如此之高 所以就需要将层级设置低一点: #plasmo-shadow-container {z-index: …...
《QT实用小工具·十一》Echart图表JS交互之仪表盘
1、概述 源码放在文章末尾 该项目为Echart图表JS交互之炫酷的仪表盘,可以用鼠标实时改变仪表盘的读数。 下面为demo演示: 该项目部分代码如下: #include "widget.h" #include "ui_widget.h" #include "qurl.h&q…...
深入浅出理解ArrayBuffer对象TypedArray和DataView视图
目录 举例理解 1. ArrayBuffer对象 2. TypedArray 3. DataView 总结 具体讲解 1. ArrayBuffer对象 2. TypedArray 3. DataView 注意事项 举例理解 先举个简单的例子理解ArrayBuffer对象TypedArray和DataView视图的概念和之间的关系 1. ArrayBuffer对象 想象一个场景…...
人工智能 - 服务于谁?
人工智能服务于谁? 人工智能服务于生存,其最终就是服务于战争(热战、技术战、经济战) 反正就是为了活着而战的决策。 既然人工智能所有结果,来自大数据的分挖掘(分析)也就是数据的应用&#x…...
软考高级架构师:嵌入式系统的内核架构
作者:明明如月学长, CSDN 博客专家,大厂高级 Java 工程师,《性能优化方法论》作者、《解锁大厂思维:剖析《阿里巴巴Java开发手册》》、《再学经典:《Effective Java》独家解析》专栏作者。 热门文章推荐&am…...
分布式锁实战
4、分布式锁 4.1 、基本原理和实现方式对比 分布式锁:满足分布式系统或集群模式下多进程可见并且互斥的锁。 分布式锁的核心思想就是让大家都使用同一把锁,只要大家使用的是同一把锁,那么我们就能锁住线程,不让线程进行&#x…...
【VMware Workstation】启动虚拟机报错“此主机支持 AMD-V,但 AMD-V 处于禁用状态”
问题出现步骤: 打开虚拟机: 然后报错: “此主机支持 AMD-V,但 AMD-V 处于禁用状态。 如果已在 BIOS/固件设置中禁用 AMD-V,或主机自更改此设置后从未重新启动,则 AMD-V 可能被禁用。 (1) 确认 BIOS/固件设…...
非关系型数据库(缓存数据库)redis的基础认知与安装
目录 一.关系型数据库和非关系型数据库 关系型数据库 非关系型数据库 关系数据库与非关系型数据库的区别 ①非关系数据 关系型数据库 非关系型数据库产生背景 数据存储流向 非关系型数据库 关系数据库 二.redis的简介 1.概念 2.Redis 具有以下几个优点: 3.Redi…...
Go语言如何处理文件
1.文件的重要性 文件不过是硬盘中的数据,看起来好像没什么了不起,但实际上,文件能够让程序员管理配置、存储程序的状态乃至从底层操作系统中读取数据。 UNIX型操作系统的一个重要特征是,将一切都视为文件。这意味着在操作系统看来,从键盘到打印机的所有东西都可像文件那样…...
Java基础知识总结(42)
(1)Java关键字的相关知识进行了复习 考试过程中“main”是主方法名,而不是Java关键字 (2)类型转换 当一个算术表达式中包含多个基本类型的值时,整个算术表达式的数据类型将发生自动提升,所有的b…...
C++ | Leetcode C++题解之第6题Z字形变换
题目: 题解: class Solution { public:string convert(string s, int numRows) {int n s.length(), r numRows;if (r 1 || r > n) {return s;}string ans;int t r * 2 - 2;for (int i 0; i < r; i) { // 枚举矩阵的行for (int j 0; j i &l…...
JavaEE——手把手教你实现简单的 servlet 项目
文章目录 一、什么是 Servlet二、创建一个简单的 Servlet 程序1. 创建项目2.引入依赖3. 创建目录4.编写代码5. 打包程序6. 部署7.验证整体过程总结 三、使用 Smart Tomcat 插件简化项目创建四、创建项目时可能遇到的几个问题。 一、什么是 Servlet Servlet 是一种实现 动态页面…...
X年后,ChatGPT会替代底层程序员吗?
能不能替代,真的很难说,因为机器换掉人,这其实是一个伦理问题。 其实说白了,任何行业在未来都会被AI或多或少的冲击到,因为ChatGPT做为一个可以持续提升智能的AI,在某些方面的智能程度超过人类并不是什么难…...
OpenAI 推出新网络爬虫GPTBot,为GPT-5做准备
目录 一、GPTBot是什么?它是如何工作的?二、GPTBot 与 Google Bot 等搜索引擎网络爬虫有何不同?三、GPTBot 与 Perplexity AI 的网络爬虫有何不同?四、允许 GPTBot 爬取有哪些风险和好处?4.1 允许 GPTBot 的好处4.2 允…...
【Easy云盘 | 第二篇】后端统一设计思想
文章目录 4.1后端统一设计思想4.1.1后端统一返回格式对象4.1.2后端统一响应状态码4.1.3后端统一异常处理类4.1.4StringUtils类4.1.5 RedisUtils类 4.1后端统一设计思想 4.1.1后端统一返回格式对象 com.easypan.entity.vo.ResponseVO Data public class ResponseVO<T> …...
c语言:模拟字符串拷贝功能(strcpy),面试题
面试题:优化中的优化(10分满分) 字符串拷贝:是将一个字符串的内容复制到另一个字符串中的操作。 运用函数模拟字符串拷贝:(5分) 模拟字符串拷贝 #include <stdio.h> void my_strcpy(char* dest, c…...
信创环境ES索引管理脚本:close, delete
背景 elastic-curator在信创环境无现成安装包,且现成一般无法联网,此时通过脚本管理es索引是最佳选择。 1, 脚本内容: es-close-del.sh [rootmyprojtest001 ]# cat es-close-del.sh #/bin/bash#elastic地址 ELASTIC_URL127.0.0.1:9200 #默认的删除时间…...
torch-v1.3.1-build
编译pytorch-v1.3.1 python版本>3.8会收到报错 error: cannot convert ‘std::nullptr_t’ to ‘Py_ssize_t’ {aka ‘long int’} in initialization, 参见: https://github.com/pytorch/pytorch/issues/28060 简单办法是用python3.7 wget https://mirrors.tuna.tsingh…...
C语言宏定义笔记
把宏名全部大写,函数名不要全部大写。注意宏定义表示数据类型和用 typedef 定义数据说明符的区别。宏定义只是简单的字符串替换,由预处理器来处理; typedef 是在编译阶段由编译器处理的,它并不是简单的字符串替换,而给…...
设计模式:生活中的观察者模式
想象你在社交媒体上关注(订阅)了一个名人或新闻频道(主题)。一旦他们发布新内容,所有关注者(观察者)都会收到通知。这个过程就很像观察者模式的工作原理。 生活场景类比 主题(Subj…...
Qt实现Kermit协议(四)
3 实现 3.3 KermitRecvFile 该模块实现了Kermit接收文件功能。 序列图如下: 3.3.1 KermitRecvFile定义 class QSerialPort; class KermitRecvFile : public QObject, public Kermit {Q_OBJECT public:explicit KermitRecvFile(QSerialPort *serial, QObject *…...
苏州金龙助力旅游客运加速蜕变
近日,北京铭悦旅游客运有限公司又迎来一批苏州金龙海格纯电动客车。(以下简称北京铭悦旅游)总经理郭保生在车辆交付时说到,“为迎接强劲复苏的旅游市场,要求旅游客运向绿色客运转型,以及人民对品质生活、美…...
头盔检测 | 基于Caffe-SSD目标检测算法实现的建筑工地头盔检测
项目应用场景 面向建筑工地头盔检测场景,使用深度学习 Caffe SSD 目标检测算法,基于 C 实现。 项目效果 项目细节 > 具体参见项目 README.md (1) 安装 Caffe SSD(2) 执行训练 sh examples/Hardhat/SSD300/train_SSD300.sh (3) 部署算法 项目获取 h…...
Stable diffusion 加载扩展列表报错解决方法
项目场景: 在使用Stable diffusion webui时,使用扩展列表出现错误 问题描述 点击loadfrom后,出现加载扩展列表报错 原因分析: 下载的扩展的时候,都是github 的url,需要科学上网,如果不能科学…...
Git(8)之分支间同步特定提交
Git(8)之分支间同步特定提交 Author:Once Day Date:2024年4月7日 漫漫长路有人对你微笑过嘛… 全系列文章可查看专栏: Git使用记录_Once_day的博客-CSDN博客 文章目录 Git(8)之分支间同步特定提交1. 分支间同步提交2. cherry-pick同步分支间的特定提交…...
万得AI算法工程师一面面试题6道|含解析
节前,我们星球组织了一场算法岗技术&面试讨论会,邀请了一些互联网大厂朋友、参加社招和校招面试的同学,针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。 今天…...
免费解析网站制作/兰州网络推广关键词优化
Fortify漏洞之 Privacy Violation(隐私泄露)和 Null Dereference(空指针异常)参考文章: (1)Fortify漏洞之 Privacy Violation(隐私泄露)和 Null Dereference(…...
网站建设的图片怎么加水印/嘉兴seo外包公司
在文章的开头,首先要向一直关注我的人说声抱歉!因为原本是打算在前端框架5.0发布之后,就立马完成 PHP 模板引擎的初版。但我没能做到,而且一直拖到了15年元旦才完成,有很严重的拖延症我很惭愧,再次抱歉&…...
内部网站 备案/上海百度推广优化公司
1 item方法 想对比__getattr__(), __setattr__() 和 __deltattr__()这三个通过属性的方式的三个方法 还有__getitem__(), __setitem__() 和 __delitem__()这三个函数, 是通过字典形式来处理属性 字典形式使用中括号的方式获取值 在实现__setitem__()的时候仍然需要使用__dict__…...
wordpress 远程图片/如何搭建企业网站
(一)什么是SAS SAS(Serial Attached SCSI)即串行SCSI技术,是一种磁盘连接技术,它综合了并行SCSI和串行连接技术(如FC、SSA、IEEE1394等)的优势,以串行通讯协议为协议基础…...
沈阳三好街做网站公司/semiconductor是什么意思
三种方法 1.常规指针类(浅复制) 缺点:野指针 2.智能指针类(计数类) 避免野指针(悬垂指针) 3.值型类(深复制) class AHasPtr { public: AHasPtr(int *p,int i):ptr(p…...
微信公众号小说网站怎么做/网站排行榜前十名
Angular服务是一个由服务工厂创建的单例对象。这些服务工厂是由 service provider 依次创建的。而service providers是构造函数。它们必须包含一个$get属性用于在实例化的时候返回服务工厂。 当你请求一个服务,$injector负责找到正确的service provider,…...