完全二叉树

编辑:香料网互动百科 时间:2020-05-29 12:49:00
编辑 锁定
完全二叉树的定义、性质以及算法见正文。这里补充一点:完全二叉树是效率很高的数据结构,是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。
中文名
完全二叉树
外文名
Complete Binary Tree
日    语
完全二進法の木
德    语
Komplett - baum

完全二叉树判断完全二叉树

编辑
完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点

完全二叉树完全二叉树定义

编辑
完全二叉树(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 div 2];
(4)若2*i<=n,那么tree的左孩子为tree[2*i];若2*i+1<=n,那么tree的右孩子为tree[2*i+1];
(5)若i>n div 2,那么tree[i]为叶子结点(对应于(3));
(6)若i<(n-1) div 2.那么tree[i]必有两个孩子(对应于(4))。
(7)满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
完全二叉树第i层至多有2^(i-1)个节点,共i层的完全二叉树最多有2^i-1个节点。
完全二叉树的特点是:
1)只允许最后一层有空缺结点且空缺在右边,即叶子结点只能在层次最大的两层上出现;
2)对任一结点,如果其右子树的深度为j,则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

完全二叉树算法

编辑
如果一棵具有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],其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。
词条标签:
计算机术语 计算机学 科技