完全二叉树(Complete Binary Tree)

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

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

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

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

可以根据公式进行推导，假设n0是度为0的结点总数(即叶子结点数)，n1是度为1的结点总数，n2是度为2的结点总数，则 ①n= n0+n1+n2 (其中n为完全二叉树的结点总数);又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，所以②n= 1+n1+2*n2 ;由①、②两式把n2消去得:n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

简便来算，就是 n0=n/2，其中n为奇数时(n1=0)向上取整;n为偶数时(n1=1)。可根据完全二叉树的结点总数计算出叶子结点数。

完全二叉树:叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为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个

大家都知道完全二叉树的总结点数是： 2^h-1，而均衡二叉树是完全二叉树再加上几个叶结点，所以它的总结点数就是：2^（h-1）-1+m，其中h是树的深度，m是第h层叶结点个数。

下面我们来讨论左偏树的距离和节点数的关系。

[引理1] 若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。

证明:由性质2可知，当且仅当对于一棵左偏树中的每个节点i，都有dist(left(i)) =dist(right(i)) 时，该左偏树的节点数最少。显然具有这样性质的二叉树是完全二叉树。

[定理1] 若一棵左偏树的距离为k，则这棵左偏树至少有2^(k+1)-1个节点。

证明:由引理1可知，当这样的左偏树节点数最少的时候，是一棵完全二叉树。距离为k的完全二叉树高度也为k，节点数为2^(k+1)-1，所以距离为k的左偏树至少有2^(k+1)-1个节点。

作为定理1的推论，我们有:

[性质4] 一棵N个节点的左偏树距离最多为ëlog(N+1)û-1。

证明:设一棵N个节点的左偏树距离为k，由定理1可知，N ≥ 2^(k+1)-1，因此k ≤ ëlog(N+1)û-1。

标程

《数字序列》程序

1

/ \

2 3

\ /

4 5 是均衡二叉树，因为它去掉叶结点及相应的树枝后，

变成了：

1

/ \

2 3 ，这是一个二叉树。

1

/ \

2 3

而 \ / \ 则不是，因为它去掉叶结点及相应的树枝后，

4 5 6

/

7

变成了：

1

/ \

2 3

\

4

很显然，这并不是一个完全二叉树。