树和二叉树

 树


    逻辑表示方法
        树形表示法
        文氏图表示法
        凹入表示法
        括号表示法
    性质
        树的结点数等于所有结点的度加一
        度为m的树中第i层最多有m的(i-1)次方个结点
        高度为h的m次树最多的节点数(等比数列公式求和)
        具有n个结点的m次树的最小高度
    树的遍历
        先根遍历
        后根遍历
        层次遍历
    存储结构
        双亲存储结构
            存放数据元素和双亲的位置
        孩子链存储结构
            存放数据元素和指向所有孩子结点的指针
        孩子兄弟链存储结构
            一个数据域,一个最左的孩子(长子)和下一个兄弟结点的指针域

二叉树


    二叉树与度为2的树
        度为2的树要求必须包含一个度为2的结点,而二叉树不需要
        度为2的树不区分左右子树,而二叉树严格区分
    性质
        非空二叉树的叶子节点数等于双分支节点数加1
        其他性质
          
    二叉树和树、森林的转换
        
    存储结构
        顺序存储结构
            只能存储完全二叉树或满二叉树,对于一般二叉树,可以化为完全二叉树或满二叉树
            结点编号为i,则双亲为i/2的向下取整,左孩子为2i,右孩子为2i+1
            优点
                查找一个结点的双亲结点和孩子结点方便
            缺点
                二叉树的插入和删除操作不方便
        链式存储结构
    二叉树的遍历
        先序遍历
        中序遍历
        后序遍历
        层次遍历
    二叉树的构造
        已知中序序列和先序序列
        已知中序序列和后序序列
    线索化二叉树
        先序线索二叉树
        后序线索二叉树
        中序线索二叉树

哈夫曼树


    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树
    定理:对于具有n个叶子结点的哈夫曼树,一共有2n-1个结点
    哈夫曼编码
        编码:将文字转为二进制字符串
        左分支为0,右分支为1
        实质:使频率越高的字符采用越短的编码
        在一组编码中,任一字符的编码不可能使其他字符编码的前缀

 

实现代码

数据结构与算法: 记录学习笔记,包括代码和思维导图

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/23557.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构】什么是堆,如何使用无序数组生成一个堆?

文章目录 一、堆的概念及其介绍二、如何使用无序序列构建一个堆?三、C语言实现堆的基本操作结构体创建与销毁获取堆顶数据与个数及堆的判空堆的插入与删除 源代码分享 一、堆的概念及其介绍 堆(Heap)是计算机科学中一类特殊的数据结构的统称,堆通常是一…

公网远程连接Redis数据库【内网穿透】

文章目录 1. Linux(centos8)安装redis数据库2. 配置redis数据库3. 内网穿透3.1 安装cpolar内网穿透3.2 创建隧道映射本地端口 4. 配置固定TCP端口地址4.1 保留一个固定tcp地址4.2 配置固定TCP地址4.3 使用固定的tcp地址连接 转发自cpolar内网穿透的文章:公网远程连接…

docker构建镜像上传到DockerHub

docker构建镜像上传到DockerHub DockerHub注册账号 DockerHub网址: https://hub.docker.com/ 注册 登录 安装docker docker宿主机环境 centos7 参考网址: https://yeasy.gitbook.io/docker_practice/install/centos 测试 docker 是否安装好 docker -v登录docker 登录 dock…

Chatgpt版本的opencv安装教程

文章目录 前言一、安装opencv方法一二、安装opencv方法二 前言 最近刚买了台RTX 3070的电脑,顺手刷了个ubuntu系统专门玩Carla,为了方便查资料,也顺手搭了浏览chatgpt的环境,用的clash,还挺好用的。然后刚好在看Carla…

如何使用JQuery实现Js二级联动和三级联动

前言:使用JQuery封装好的js方法来实现二级三级联动要比直接使用js来实现二级三级联动要简洁很多。所以说JQuery是个非常强大的、简单易用的、兼容性好的JavaScript库,已经成为前端开发人员不可缺少的一部分,是Web开发中最流行的JavaScript库之…

Mysql数据库对表的基本操作

一.表基本操作 1.当前数据库内创建表 2.查看表 3.删除表 4.修改表结构 5.复制表(结构) 二.表约束创建 1.约束的作用 2.约束的类型 3.演示 一.表基本操作 1.当前数据库内创建表 CREATE TABLE 表名( 列名 列数据类型, 列名 列…

小兔鲜--项目总结3

目录 结算模块-地址切换交互实现 地址切换交互需求分析 打开弹框交互实现 地址激活交互实现 订单模块-生成订单功能实现 支付模块-实现支付功能 支付业务流程 支付模块-支付结果展示 支付模块-封装倒计时函数 理解需求 实现思路分析 会员中心-个人中心信息渲染 分页…

solr快速上手:managed-schema标签详解(三)

0. 引言 core核心是solr中的重中之重,类似数据库中的表,在搜索引擎中也叫做索引,在solr中索引的建立,要先创建基础的数据结构,即schema的相关配置,今天继续来学习solr的核心知识: solr快速上手…

OpenCV——最小外接矩形

目录 一、主要函数二、代码实现三、结果展示 一、主要函数 cv::RotatedRect cv::minAreaRect(const cv::Mat& points );emspminAreaRect 函数用于计算给定点集的最小外接矩形。该矩形的长和宽是可以任意旋转的,因此被称为旋转矩形。 points :是一个…

article-码垛机器人admas仿真

按照运动学仿真的类似步骤为机器人添加材料、运动副和关节驱动,给机器人手腕末端施加50N最大负载,仿真模型如图5-17。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AXYQVZPq-1684936426972)(data:image/svgxml;utf8, )] 图…

Python实现ACO蚁群优化算法优化BP神经网络回归模型(BP神经网络回归算法)项目实战

说明:这是一个机器学习实战项目(附带数据代码文档视频讲解),如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 蚁群优化算法(Ant Colony Optimization, ACO)是一种源于大自然生物世界的新的仿生进化算法&#xff0c…

Qt自定义的ColorDialog--仿QColorDialog

Qt已经有了色板选择,但是它使用QDialog形成的,每次调用基本上都成了点一个按钮,谈一个模态框,选择好颜色之后再关掉模态框。 但是,如果想将颜色选择板放在窗口上,并不会有模态的功能就会比较麻烦&#xff…

docker安装mysql8.0.33

1 从docker仓库中拉去mysql 8.0 docker pull mysql:8.0如果使用 docker pull mysql 默认拉取的是最新版本的mysql 上面我拉去的是8.0的版本,最后拉取过来的是8.0.33 如果有想要指定的版本,可以直接写指定版本,如: docker pull my…

pytorch:nn.ModuleList和nn.Sequential、list的用法以及区别

文章目录 在构建网络的时候,pytorch有一些基础概念很重要,比如nn.Module,nn.ModuleList,nn.Sequential,这些类我们称为为容器(containers),可参考containers。本文中我们主要学习nn.…

【Python】正则表达式应用

知识目录 一、写在前面✨二、姓名检查三、解析电影排行榜四、总结撒花😊 一、写在前面✨ 大家好!我是初心,希望我们一路走来能坚守初心! 今天跟大家分享的文章是 正则表达式的应用 ,希望能帮助到大家!本篇…

把字节大佬花3个月时间整理的软件测试面经偷偷给室友,差点被他开除了···

写在前面 “这份软件测试面经看起来不错,等会一起发给他吧”,我看着面前的面试笔记自言自语道。 就在这时,背后传来了leder“阴森森”的声音:“不错吧,我可是足足花了三个月整理的” 始末 刚入职字节的我收到了大学室…

Windows 10 X64 内核对象句柄表解析

fweWindows 很多API函数都会创建和使用句柄(传入参数),句柄代表一个内核对象的内存地址,每个进程都有一个句柄表,它保存着进程拥有的句柄,内核也有一个句柄表 PspCidTable,它保存着整个系统的句柄。 ExpLookupHandleTa…

DNS风险分析及安全防护研究(一):DNS自身风险分析(中科三方)

作为互联网上的一项基础服务,DNS在网站运行中起到了至关重要的作用,然而其安全性在很长一段时间内都没有得到足够的重视。DNS采用不可靠的UDP协议,安全性具有较大的漏洞,攻击者很容易利用这些漏洞发动攻击,从而引起一些…

华为设备这14个广域网命令,值得每位做广域网业务的网工收藏!

你好,这里是网络技术联盟站。 华为设备广域网命令是网络管理员在运维过程中常用的一类命令。该命令集涵盖了DCC配置命令、PPP配置命令、MP配置命令、PPPoE命令、ATM配置命令、帧中继配置命令、HDLC配置命令、LAPB配置命令、X.25配置命令、IP-Trunk配置命令、ISDN配…

Java 与数据结构(6):快速排序

ChatGPT 中文指南(大全) 内容包含:如何开通chatgpt、chatgpt的同类站点、prompts 、AI绘图、ChatGPT 工具、相关报告论文、ChatGPT应用项目等 链接:ChatGPT 中文指南(大全) 指令指南,精选资源清单,更好的使用 chatGPT 让你的生产力…