完全二叉树和优异二叉树的区别是什么?
一、完全二叉树和优异二叉树的区别
完全二叉树
完全二叉树是指除了最后一层外，其他每一层都必须填满节点，并且最后一层的节点都必须靠左排列的二叉树。也就是说，如果一个完全二叉树的深度为h，则除了第h层外，其它各层节点数都达到最大值，第h层所有节点都连续集中在最左边。
优异二叉树
优异二叉树，也叫哈夫曼树，是指带权路径长度最小的二叉树。在哈夫曼树中，带权路径长度等于树中所有叶子节点的权值乘以它们到根节点的路径长度之和。在构造哈夫曼树的过程中，节点的权值越大，它距离根节点就越近。
区别
完全二叉树的形态比较固定，每一层的节点数是确定的；而优异二叉树的形态可以根据节点权值的不同而有所不同，节点数也没有固定的限制。完全二叉树的构造不需要根据节点权值来确定，而是按照深度优先的原则，一层一层从左到右地填充节点。优异二叉树的构造则是基于贪心算法，按照节点权值从小到大的顺序来构造。完全二叉树中，任何一个节点的左右子节点，如果存在，一定是连续的；而优异二叉树中，同一个节点的左右子节点可能会不连续。总的来说，完全二叉树更多地用于数据结构和算法中的一些具体实现，比如堆排序、优先队列等；而优异二叉树则更多地用于信息编码和压缩等领域，比如哈夫曼编码。
延伸阅读：
二、树的概念以及相关概念
树是一种非线性数据结构，由（n>0)个节点组成的一个具有层次关系的集合。
根节点：没有父节点的节点
叶子结点：没有子节点的节点,即度为0的节点
节点的度:一个节点含有的子节点的个数称为该节点的度
树的度：一个树中最大的节点的度为该树的度
相关公式：
节点数=分支数+1
节点数=度为0的节点+度为1的节点+度为2的节点
分支数=度为1的节点+2*度为2的节点
猜你喜欢LIKE
相关推荐HOT
更多>>
RESTful API的命名有什么讲究?
一、RESTful API的命名有什么讲究和目录没关系，通常是框架路由接管的 request uri解析出来的（v1、v2有可能是实际的目录）restful规范/资源名/...详情>>
2023-10-18 23:56:05
文件系统和数据库是由于什么原因才选择B树或B+树建立?
一、文件系统和数据库是由于什么原因才选择B树或B+树建立索引的索引的目标是要找到数据所在的物理位置，因此用树去实现搜索数据所在物理位置，...详情>>
2023-10-18 22:55:19
mysql如果单表数据量过千万怎么办?
一、mysql如果单表数据量过千万怎么办方案概述方案一：优化现有mysql数据库。优点：不影响现有业务，源程序不需要修改代码，成本最低。缺点：有...详情>>
2023-10-18 22:33:40
数据库表名、字段名用中文有什么问题?
一、数据库表名、字段名用中文的问题1、兼容性问题某些数据库管理系统（DBMS）可能不支持使用中文作为表名和字段名，或者对于中文的支持有限。...详情>>
2023-10-18 21:09:43热门推荐
RESTful API的命名有什么讲究?
沸KEGG 怎么用?
热文件系统和数据库是由于什么原因才选择B树或B+树建立?
热mysql如果单表数据量过千万怎么办?
新什么情况下需要使用分布式数据库?
为什么Cassandra的写速度比MySQL快?
数据库表名、字段名用中文有什么问题?
数据库文件存放在NAS中，会有什么问题吗?
多线程并发访问数据库中不同记录时应该采用什么办法?
为什么mysql要额外加入一个utf8mb4数据类型，而不是原地升级utf8?
PolarDB-X与PolarDB的关键区别是什么?
Mysql、SQLite、Mongo的区别?
为什么用Go语言做Web应用开发框架?
什么是i.MXRT11xx上的串行NOR Flash双程序可交替启动?
技术干货
京公网安备 11010802030320号