二叉树（四）

一、二叉树的性质

二、练习

1.某二叉树共有399个节点，其中有199个度为2的节点，则二叉树中的叶子节点数为（ ）。

A.不存在这样的树      B.200      C.198      D.199

答案：B      参考二叉树的性质第三条

2.在具有2n个节点的完全二叉树中，叶子节点个数为（ ）。

A.n      B.n+1      C.n-1      D.n/2

答案：A

3.一棵完全二叉树的结点数为531个，那么这棵树的高度为（ ）。

A.11      B.10      C.8      D.12

答案：B

设完全二叉树有h层，满二叉树的结点为2^h-1个，因为满二叉树最后一层是满的，所以当完全二叉树是满二叉树时，结点数最多；当最后一层只有一个结点时，结点数最少，即2^(h-1)个。

2^10=1024，2^9=512

4.一个具有767个结点的完全二叉树，其叶子结点个数为（ ）。

A.383      B.384      C.385      D.386

答案：B

5.给一个前序遍历和中序遍历，还原二叉树：

前序遍历：1 2 3 4 5 7 6

中序遍历：3 2 1 5 7 4 6