二叉树练习题及答案

一、选择题

1．关于二叉树的下列说法正确的是（ B ）

A． 二叉树的度为2 B． 二叉树的度可以小于2

C． 每一个结点的度都为2 D ．至少有一个结点的度为2

2．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为（ C ）

A． 3 B． 4

C．5 D ．6

3．若一棵完全二叉树中某结点无左孩子，则该结点一定是（D ）

A． 度为1的结点 B． 度为2的结点

C． 分支结点 D ．叶子结点

4．深度为k的完全二叉树至多有（ C ）个结点，至少有（ B ）个结点。

A． 2k-1-1 B． 2k-1

C． 2k-1 D ．2k

5．在具有200个结点的完全二叉树中，设根结点的层次编号为 1，则层次编号为60的结点，其左孩子结点的层次编号为（ C 2i ），右孩子结点的层次编号为（ D 2i+1），双亲结点的层次编号为（ 60/2=30 A ）。

A． 30 B． 60

C． 120 D ．121

6．一棵具有124个叶子结点的完全二叉树，最多有（B ）个结点。

A． 247 B． 248

C． 249 D ．250

二、填空题

1． 树中任意结点允许有孩子结点，除根结点外，其余结点且仅有一个 双亲结点。

2．若一棵树的广义表表示法为A（B（E，F），C（G（H，I，J，K），L），D（M（N））），则该树的度为，树中叶子结点的个数为 8 。

3．若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数为 14 。

n=n0+n1+n2+n3+n4=n0+4+3+2+2=n0+11

n=1+孩子=1+4+6+6+8+25

n0+11=25

n0=14

4．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是 n-2m+1 。

5．深度为k（k>0）的二叉树至多有k 个结点，第i层上至多有i-1

6．已知二叉树有52个叶子结点，度为1的结点个数为30，则总结点个数为 。

7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是 。

8．高度为6的完全二叉树至少有 个结点。

9．一个含有68个结点的完全二叉树，它的高度是。

10．已知一棵完全二叉树的第6层上有6个结点，则总的结点个数至少是 ，其中叶子结点个数是。

解析：（1） 5：31

6：6

（2）第5层上的叶子节点为：24-3=13

第6层上的叶子节点为：6

总的叶子节点个数为：13+6=19

11．已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是 107 。

解析：由题意得：这棵二叉树最多有7层

在第6层满的情况下，有26-1=32，其中非叶子节点有32-10=22，而非叶子节点最多有两个孩子从而第七层上共有22*2=44个节点。

又前6层的节点数为：26-1=63

所以这棵二叉树的节点数最多为63+44=107个