二叉树的细分及五大性质

二叉树细分了两种类型的二叉树,一种叫做“满二叉树”,就是每一层都挂满了节点,没有空位。另一种叫做“完全二叉树”,完全二叉树假设有n层,那么n-1层和满二叉树是一样的,但是第n层最后一个节点前边都挂满了节点。这是它们两个概念的唯一具体区别。表示图如下:

【满二叉树】

2015-06-01_223256

【完全二叉树】

2015-06-01_223801

上面的树符合最后一个节点(F节点)前都挂满了节点的规则,所以它属于一个完全二叉树。下面重点来了,二叉树具有5大性质,如下介绍。

【二叉树的五大性质】

  • 性质1: 在二叉树的第i层上至多有2i-1个结点(i>0)。
    比如第3层,那么就是 23-1 = 4,第3层最多有4个节点

 

  • 性质2: 深度为k的二叉树至多有2k-1个结点(k>0)。
    比如第3层,最多有 23 -1 = 7 个节点

 

  • 性质3: 对于任何一棵二叉树,若2度的结点数有n2个,则叶子数(n0)必定为n2+1 (即n0=n2+1)
    度为2的节点有3个(A B C),那么 n2 = 3
    叶子数 = n2 + 1,那么就是 3 + 1 = 4 个

 

  • 性质4: 具有n个结点的完全二叉树的深度必为log2n(向下取整)+1
    log2n + 1 转换为公式是
    2x = n,此时 n 为 7 ,所以 x 约等于 2.几次方,向下取整后得 2
    深度 = x + 1,2 + 1 = 3,所以深度结果就是3

 

  • 性质5: 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)。
    如下图:编号为3的节点是C,其左子节点的编号是2*3=6就是F,右子节点的编号是2*3+1=7就是G,双亲的编号是 3/2=1就是A

2015-06-01_224246

最后我们做一下总结,讲了这么多,无非我们就是希望引出二叉树是有规则的,我们将二叉树存入一个数组后,是可以恢复回来的,不像多叉树那样无法恢复。根据第五条的性质,我们很轻松就可以在一个存放在数组中的二叉树数据恢复为一个二叉树模型。

而如果是一个非满二叉树怎么办呢?我们如何把非满二叉树存放到一个数组里面呢?其实思路非常简单,我们只需把哪些缺少一个子节点的节点给他填充一个空就可以了。如下图:

2015-06-03_232545

说说你的想法