满二叉树详解(定义特征及公式)

满二叉树详解(定义特征及公式)-mikechen

满二叉树定义

一棵树高度为h,高度为h,由2^h-1个节点构成的二叉树,就称为满二叉树。

 

满二叉树特征

满二叉树外观上是一个三角形,如下图所示:

满二叉树详解(定义特征及公式)-mikechen

所有内部节点都有两个子节点,最底一层是叶子节点。

1.满二叉树中第 i 层的节点数为 2的i-1 次方个;

2.深度为 k 的满二叉树必有 2k次方-1 个节点 ,叶子数为 2的k-1次方;

3.满二叉树中不存在度为 1 的节点,每一个分支点中都两棵深度相同的子树,且叶子节点都在最底层。

 

满二叉树节点公式

如果一颗树深度为h,最大层数为k,且深度与最大层数相同,即k=h;

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

总结点数是:2^k-1 (2的k次方减一),总节点数一定是奇数。

树高:h=log2(n+1)

 

关注「mikechen」,十余年BAT架构经验倾囊相授!

评论交流
    说说你的看法