美文网首页
完全二叉树(Complete Binary Tree)

完全二叉树(Complete Binary Tree)

作者: Jay_星晨 | 来源:发表于2020-06-06 09:42 被阅读0次

一、定义:

    若设二叉树的深度为k,除第k层外,其他各层(1~(k-1)层)的节点数都达到最大值,且第k层所有的节点都连续集中在最左边,这样的树就是完全二叉树。如下图:
image
     完全二叉树是一种效率很高的数据结构,而堆是一种完全二叉树或者近似完全二叉树,因此堆的效率也很高;像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,二叉排序树的效率也要借助平衡性来提高,而平衡性是基于完全二叉树的。

    下图是非完全二叉树:
image

二、特点

    1) 在非空二叉树中,第k层的结点总数不超过2^(k-1),k>=1;

    2) 深度为k的二叉树最多有2k-1个结点(k>=1),最少有k个结点;

    3) 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

    4) 具有n个结点的完全二叉树的深度为log2(n+1);

    5)有n个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:

        a、若m为结点编号则 如果m>1,则其父结点的编号为m/2;

        b、如果2*m<=n,则其左儿子(即左子树的根结点)的编号为2*m;若2*m>n,则无左儿子;

        c、如果2*m+1<=n,则其右儿子的结点编号为2m+1;若2m+1>n,则无右儿子。

    6)给定n个节点,能构成h(n)种不同的二叉树,其中h(n)为卡特兰数的第n项,h(n)=C(2*n, n)/(n+1)。

    7)设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i。

相关文章

网友评论

      本文标题:完全二叉树(Complete Binary Tree)

      本文链接:https://www.haomeiwen.com/subject/ghtozhtx.html