数据结构:完全二叉树 gaunthan Posted on Jan 5 2017 ? Data Structures ? ## 定义 **完全二叉树**(complete binary tree)是除最后一层外,每一层上的节点数均达到最大值,在最后一层上只缺少右边的若干结点(即底层上的元素从左到右填入)的二叉树。 示例如下:  ## 性质 对于完全二叉树,因其节点分布的规律性,可以用数组表示它而不需要使用指针。用这种实现方法的唯一问题是树的最大大小需要事先估计。 对于数组中任一位置$i$的元素,其有如下性质: * 左儿子在位置$2 * i$上 * 右儿子在左儿子后的单元 $2 * i + 1$中 * 父亲在位置$\lfloor i / 2 \rfloor$上 ## 应用 完全二叉树最常见的一个应用是用于实现二叉堆。 赏 Wechat Pay Alipay 数据结构:二叉树 数据结构:AVL树