必威体育Betway必威体育官网
当前位置:首页 > IT技术

完全二叉树,满二叉树,霍夫曼树

时间:2019-10-19 21:12:14来源:IT技术作者:seo实验室小编阅读:78次「手机版」
 

完全二叉树

霍夫曼树:每个节点要嘛没有子节点,要么有两个子节点

完全二叉树:满二叉树的一部分或者全部。

满二叉树:每个父亲都有2个叶子。

               1                                 1
            /     \                          /      \
          1        1                        1         1
       /    \    /    \                  /     \
      1     1    1     1               1         1
        满二叉树                              完全二叉树

堆的话一般都是用完全二叉树来实现的,比如大堆和小堆。一个树节点的度数就是这个树节点有多少子节点,和树的深度意义不同。

依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适

完全二叉树是效率很高的数据结构,堆是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法dijkstra算法、Prim算法等都要用堆才能优化,几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。

完全二叉树(Complete binary Tree)

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。

      完全二叉树特点编辑

叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;

出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:

var tree:array[1..n]of longint;{n:integer;n>=1}

对于tree[i],有如下特点:

(1)若i为奇数且i>1,那么tree的左兄弟为tree[i-1];

(2)若i为偶数且i<n,那么tree的右兄弟为tree[i+1];

(3)若i>1,tree的双亲为tree[i p 2];

(4)若2*i<=n,那么tree的左孩子为tree[2*i];若2*i+1<=n,那么tree的右孩子为tree[2*i+1];

(5)若i>n p 2,那么tree[i]为叶子结点(对应于(3));

(6)若i<(n-1) p 2.那么tree[i]必有两个孩子(对应于(4))。

(7)满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

完全二叉树第i层至多有2^(i-1)个节点,共i层的完全二叉树最多有2^i-1个节点。

如果一棵具有n个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应,这棵二叉树称为完全二叉树。

可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n= n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n= 2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2。

总结起来,就是 n0=[n/2],其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。

其实满二叉树是完全二叉树的特例,因为满二叉树已经满了,而完全并不代表满。所以形态你也应该想象出来了吧,满指的是出了叶子节点外每个节点都有两个孩子,而完全的含义则是最后一层没有满,并没有满。

下面贴定义:

满二叉树(Full Binary Tree):

 

除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

一颗树深度为h,最大层数为k,深度与最大层数相同,k=h;

它的叶子数是: 2^h  第k层的结点数是: 2^(k-1)  总结点数是: 2^k-1 (2的k次方减一)  总节点数一定是奇数。

完全二叉树(Complete Binary Tree)

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。  完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。  若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。

 

霍夫曼树:每个节点要嘛没有子节点,要么有两个子节点

相关阅读

平衡二叉树(树的旋转)

1.概念平衡二叉树建立在二叉排序树的基础上,目的是使二叉排序树的平均查找长度更小,即让各结点的深度尽

C语言assert函数完全攻略

断言assert函数,C语言assert函数完全攻略 对于断言,相信大家都不陌生,大多数编程语言也都有断言这一特性。简单地讲,断言就是对某种

关于如何最大化网页的价值,满足用户需求

网页的价值是满足用户需求,引起关注和保证流量。网页价值元素通常包括:访问体验,稀缺性,及时性。一,访问体验用户体验糟糕怎么造成?网页

线索二叉树原理及前序、中序线索化(Java实现)

本文转自:https://blog.csdn.net/UncleMing5371/article/details/54176252 一、线索二叉树原理  前面介绍二叉树原理及特殊二叉

联想Z5发布会总结 开售时间确定、1299元诚意满满

A5创业网(公众号:iadmin5)6月5日消息,今日联想Z5在北京正式发布。该机号称是&ldquo;一只Apple迄今为止都做不到的产品&rdquo;。据悉

分享到:

栏目导航

推荐阅读

热门阅读