在数据结构中，完全二叉树具有独特的特点。首先，叶子节点只可能分布在最大两层，对于任意节点，如果其右分支的最大子孙层次为L，那么左分支的子孙最大层次要么是L，要么是L+1，这种特性保证了树的紧凑性</。

在存储方面，完全二叉树通常采用数组而非链表，例如，我们可以用以下数组表示：var tree:array[1..n]of longint;</ 其中n为整数，至少为1。数组的结构规则如下：

对于奇数索引i（i>1），tree的左兄弟是tree[i-1]</。

对于偶数索引i（i<n），tree的右兄弟是tree[i+1]</。

对于所有i（i>1），tree的父节点是tree[i div 2]</，即父节点的位置是子节点位置除以2向下取整。

若2*i<=n，tree的左孩子是tree[2*i]</，而2*i+1<=n时，右孩子是tree[2*i+1]</。

特别地，当i大于n除以2时，tree[i]是叶子节点</，而当i小于(n-1)除以2时，tree[i]有两个孩子</。

值得注意的是，满二叉树（每个层级都满的二叉树）必定是完全二叉树</，但反之不成立，完全二叉树不一定是满的</。在计算节点数量时，完全二叉树第i层最多有2^(i-1)个节点，整个i层的节点总数最多是2^i-1。

扩展资料

完全二叉树的定义、性质以及算法见正文，这里补充一点：完全二叉树是效率很高的数据结构，堆是一种完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

本文地址： http://www.goggeous.com/20241228/1/964556

文章来源：天狐定制

版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。