完全二叉树详解(定义特点及高度节点公式)

完全二叉树定义

完全二叉树是由满二叉树而引出来的，假如：二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

 

完全二叉树的特征

完全二叉树，形态如下图所示：

完全二叉树除最后一层，其他层都是满结点的。

完全二叉树的特征，大致分为如下4点：

1. 所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；
2. 第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边；
3. 任何一个节点不能只有右子树没有左子树；
4. 叶子节点出现在最后一层或者倒数第二层，不能再往上。

 

完全二叉树的高度公式

就是求log以2为底的结点数的对数下取整+1，所以树高h=log2n + 1。

比如一颗完全二叉树的结点数为2000，则log以2为底2000的对数的下取整等于10，然后+1，就等于11。

 

 

完全二叉树使用场景

我们了解到完全二叉树的特点是：“叶子节点的位置比较规律”，因此在对数据进行排序或者查找时可以用到它，比如堆排序就使用了它。

 

 

 

陈睿mikechen

10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》