设二叉树根结点的层次为0，一棵深度(高度)为k的满二叉树和同_网易笔试题

mike_fengyb

选B

满二叉树(Full Binary Tree)：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

发表于 2015-09-02 19:49:14 回复(0)

啦啦风吹

B错误。

A正确，B中不可能。C正确，2的k+1次方再减1。D正确，意思是高度为k的完全二叉树的节点数必须多于高度为k-1的满二叉树节点数，即2的K次方减1

发表于 2015-09-02 15:00:39 回复(0)

菜鸟葫芦娃

注意不正确的是：选择B C D

有满二叉树和完全二叉树述定义可知满二叉树也是完全二叉树可以知道A正确 B错误

满二叉树 f=2^k-1 (2的k次方减一) 完全二叉树 c<=2^k-1 可知 C D错误

下面是满二叉树和完全二叉树的一些定义和特点

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。

有如下特点：

如果一颗树深度为h，最大层数为k

它的叶子数是: 2^(h-1)

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

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

总节点数一定是奇数。

完全二叉树：除最后一层外，每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。

若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

完全二叉树有如下特点：

1）在K层二叉树中，所有的叶结点都出现在第k层或k－1层。

2）对任一结点，如果其右子树的最大层次为K，则其左子树的最大层次为K或K＋1。

如下两图(高度都3的满二叉树和完全二叉树)

编辑于 2015-09-03 06:50:56 回复(0)

溜卡西

B C

首先f>=c

f = 2^(k+1)-1 2的k+1次方减1

发表于 2015-09-02 11:20:50 回复(0)

天涯过客丶

A。正确，满二叉树也是完全二叉树

B。错，理由同A

C。错，f=2（K+1）-1

D。错，可能小于或等于

发表于 2015-09-02 10:20:03 回复(0)

设二叉树根结点的层次为0，一棵深度(高度)为k的满二叉树和同