如何判断二叉树是满二叉树

论坛 期权论坛 期权     
匿名   2018-4-26 13:46   6860   3
最好有代码,谢谢了
分享到 :
0 人收藏

3 个回复

正序浏览
4#
hhk3451  3级会员 | 2018-4-30 02:07:02 发帖IP地址来自
全二叉树(Complete Binary Tree): 若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的节点都连续集中在最左边,这就是完全二叉树。

判断很简单,广度优先搜索整个二叉树,一旦找一个不含有子节点或者只含有一个左子节点之后,那么后续的所有节点都必须是叶子节点。否则,该树就不是完全二叉树。
3#
热心网友  15级至尊 | 2018-4-30 02:07:01 发帖IP地址来自
完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。
特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l 或l+1

满二叉树:一棵深度为k,且有2的(k)次方-1个节点的二叉树
特点:每一层上的结点数都是最大结点数

最简单的就是:  求出二叉树的深度。。。和节点的总个数。。。然后满足公式就行了。。。
层次书和 节点总个数  满足 1+2+4+8+ 2的层次次方= 节点总个数。。就行了呗。。
2#
热心网友  15级至尊 | 2018-4-30 02:07:00 发帖IP地址来自
满二叉树的判断方法:
除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。








结点(如果一颗树深度为h,最大层数为k):
1、它的叶子数是: 2^(h-1);
2、第k层的结点数是: 2^(k-1);
3、总结点数是: 2^k-1 (2的k次方减一);
4、总节点数一定是奇数。



您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:58388
帖子:6688
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP