满二叉树和完全二叉树

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

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

特点:

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

  它的叶子数是: 2^h

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

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

  总节点数一定是奇数。

满二叉树

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

完全二叉树

 

原文地址:https://www.cnblogs.com/zhaojinxin/p/6745526.html