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

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

完全二叉树定义

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

 

完全二叉树的特征

完全二叉树,形态如下图所示:

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

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

完全二叉树的特征,大致分为如下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」公众号,获取更多技术干货!

评论交流
    说说你的看法