首页 > 技术文章 > 满二叉树和完全二叉树

zhaojinxin 2017-04-21 21:04 原文

满二叉树是完全二叉树的特例!!

 

满二叉树(Full Binary Tree):所有的节点(除叶子节点)都有两个子节点,节点数达到最大值。且所有叶子结点必须在同一层上.

特点:

颗树深度为h,最大层数为k,深度与最大层数相同,k=h;

  它的叶子数是: 2^h

  第k层的结点数是: 2^(k-1)

  总结点数是: 2^k-1 (2的k次方减一)

  总节点数一定是奇数。

满二叉树

 

 

完全二叉树(Complete Binary Tree):只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上

 

完全二叉树

 

 

 

 

 

推荐阅读