完全二叉树和优异二叉树的区别是什么?
来源:千锋教育
发布人:xqq
2023-10-18
推荐
在线提问>>
一、完全二叉树和优异二叉树的区别
完全二叉树
完全二叉树是指除了最后一层外，其他每一层都必须填满节点，并且最后一层的节点都必须靠左排列的二叉树。也就是说，如果一个完全二叉树的深度为h，则除了第h层外，其它各层节点数都达到最大值，第h层所有节点都连续集中在最左边。
优异二叉树
优异二叉树，也叫哈夫曼树，是指带权路径长度最小的二叉树。在哈夫曼树中，带权路径长度等于树中所有叶子节点的权值乘以它们到根节点的路径长度之和。在构造哈夫曼树的过程中，节点的权值越大，它距离根节点就越近。
区别
完全二叉树的形态比较固定，每一层的节点数是确定的；而优异二叉树的形态可以根据节点权值的不同而有所不同，节点数也没有固定的限制。完全二叉树的构造不需要根据节点权值来确定，而是按照深度优先的原则，一层一层从左到右地填充节点。优异二叉树的构造则是基于贪心算法，按照节点权值从小到大的顺序来构造。完全二叉树中，任何一个节点的左右子节点，如果存在，一定是连续的；而优异二叉树中，同一个节点的左右子节点可能会不连续。总的来说，完全二叉树更多地用于数据结构和算法中的一些具体实现，比如堆排序、优先队列等；而优异二叉树则更多地用于信息编码和压缩等领域，比如哈夫曼编码。
延伸阅读：
二、树的概念以及相关概念
树是一种非线性数据结构，由（n>0)个节点组成的一个具有层次关系的集合。
根节点：没有父节点的节点
叶子结点：没有子节点的节点,即度为0的节点
节点的度:一个节点含有的子节点的个数称为该节点的度
树的度：一个树中最大的节点的度为该树的度
相关公式：
节点数=分支数+1
节点数=度为0的节点+度为1的节点+度为2的节点
分支数=度为1的节点+2*度为2的节点
