企业官网建设流程全解析

第6章 树和二叉树 例题精讲

1. 一棵二叉树的叶结点（终端结点）数为5，单分支结点数为2，该树共有11个结点。

解析：

叶结点数为5 => 双分支结点数为4

单分支结点数为2

共有5+4+2=11个结点。

2. 设一棵哈夫曼树共有11个非叶结点，则该树有（D）个叶结点。

A. 22

B. 10

C. 11

D. 12

解析：哈夫曼树除叶结点外全为双分支结点。二叉树中叶结点比双分支结点数多1。

11个非叶结点 => 双分支结点数11 => 叶结点数12

3. 设一棵哈夫曼树共有18个叶结点，则该树共有（C）个结点。

A. 37

B. 19

C. 35

D. 17

4. 一棵具有38个结点的完全二叉树，最后一层有（A）个结点。

A. 7

B. 5

C. 6

D. 8

解析：

在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者在最右边缺少连续若干个结点，则此树为完全二叉树。而满二叉树是完全二叉树的特例。

前5层：1+2+4+8+16=31

第6层：38-31=7

5. 一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（D）个结点。

A. 38

B. 72

C. 31

D. 37

解析：

前5层：1+2+4+8+16=31

第6层：6

总共：31+6=37

6. 在一棵二叉树中，编号为13的结点的双亲结点的顺序编号为（D）。

A. 34

B. 7

C. 9

D. 6

解析：二叉树的编号按完全二叉树的编号分准。若父节点编号为i，则子结点编号为2i和2i+1。

2i+1=13 => i=6

7. 在一棵二叉树中，编号为3的结点的右孩子的结点的顺序编号为（B）。

A. 5

B. 7

C. 8

D. 6

8. 一棵有20个结点的二叉树，采用链式存储，其中共有（A）个指针域为空。

A. 21

B. 20

C. 19

D. 18

解析：

n个结点 => 有2n个指针域。

除根结点外，每个结点前有一个指针。=> 共有n-1个指针。

空指针域为2n-(n-1)=n+1

9. 设有一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空，则该树有（D）个叶结点。

A. 21

B. 22

C. 9

D. 10

解析：

20个指针域为空 => 共有19个结点。

除叶结点外每个结点度数都为2 => 叶结点以外的结点都为双分支节点。

理论：“叶结点比双分支节点多1。”=> 设叶结点数为n，则总结点数=n+（n-1）=2n-1=19 => n=10。

10. 设有一棵采用链式存储的哈夫曼树，该树的结点中共有20个指针域为空，则该树共有（C）个非叶子结点。

A. 21

B. 22

C. 9

D. 10

解析：

哈夫曼树只有叶子结点和双分支节点。

20个指针域为空 => 共有19个结点。

由“叶结点比双分支节点多1”，设双分支节点数为n，则叶结点数为n+1，总结点数=n+n+1=19 => n=9

11. 一棵采用链式存储的二叉树中，共有n个指针域被有效使用（即指针域为非空）。该二叉树有（A）个结点。

A. n+1

B. n

C. n-1

D. n-2

解析：除根结点外，每个结点对应一个指针。

12. 设有一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有2n个指针域为空。则该树有（D）个叶结点。

A. 2n

B. 2n+1

C. 2n+2

D. n

解析:

有2n个指针域为空 => 有2n-1个结点。

除叶结点外每个结点度数都为2 => 除叶结点外，全是双分支结点。

“叶结点比双分支节点多1” => 设叶结点数为x，则总结点数=x+(x-1)=2x-1=2n-1

所以x=n。

13. 设有一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有10个指针域为空。则该树有（D）个非叶结点。

A. 11

B. 10

C. 9

D. 4

解析:

有10个指针域为空 => 有9个结点。

除叶结点外每个结点度数都为2 => 除叶结点外，全是双分支结点。

“叶结点比双分支节点多1” => 设非叶结点数为x，则总结点数=x+(x+1)=2x+1=2x+1=9

所以x=4

14. 先序遍历下述二叉树，将结果填入下表中

解析：

先序：访问根节点 → 遍历左子树 → 遍历右子树

15. 中序遍历下述二叉树，将结果填入下表中

解析：

中序：遍历左子树→ 访问根节点→ 遍历右子树

16. 后序遍历下述二叉树，将结果填入下表中

解析：

后序：遍历左子树 → 遍历右子树 → 访问根节点

17. 已知权重：

a, b, c, d, e

3, 5, 6, 7, 9

构造Huffman树。求该树的Huffman编码和带权路径长度。

解：

构造Huffman树：

Huffman编码：

a:000

b:001

c:10

d:11

e:01

带权路径长度=3*3+5*3+9*2+6*2+7*2=9+15+18+12+14=68

18. 以1，2，3，3为叶结点的权，构造两棵不同高度的哈夫曼树，分别求它们的带权路径长度。

解：两棵不同高度的哈夫曼树如下：

左边的带权路径长度为：1*3+2*3+3*2+3*1=18

右边的带权路径长度为：1*2+2*2+3*2+3*2=18

19. 已知一棵有15个结点的二叉树，根结点的右子树有6个结点，对其进行先序遍历的第一个结点是7，问在中序遍历该二叉树的结果序列中，7处于第几个位置。

答：7处于第8个位置.

解析：

根结点的右子树有6个结点 => 根结点的左子树有8个结点（6+8+1=15）。

先序遍历的第一个结点是7 => 7一定是根结点。

因为，中序遍历时，先访问根结点的左子树，再访问根结点，最后访问根结点的右子树。

所以，中序遍历时，根结点处于第8+1=9的位置。

20. 先序遍历时序列为stuwvh，中序遍历序列为uwtvsh，求二叉树。

答：二叉树如下：

解析：

由先序：stuwvh => s是根

由中序：uwtvsh=> h是根s的右子树

由先序：tuwv => t是左子树的根

由中序：uwtv => v是t的右子树，uw是t的左子树

由先序：uw => u是左子树根

由中序：uw => 左子树空，右子树w

21. 后序遍历：efcdb，中序ecfbd，求该二叉树及先序遍历序列。

答：二叉树如下：

先序遍历序列为：bcefd

解析：

由后序：efcdb => b为根

由中序：ecfbd => d为右子树，ecf为左子树

由后序：efc => c为根

由中序：ecf => e为左子树，f为右子树

22. 以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

void Postorder(struct BTreeNode *BT){

if(BT!=NULL){

Postorder(BT->left);

Postorder(BT->right);

printf(“%c”,BT->data);

}

}

23. 以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

void Postorder(struct BTreeNode *BT){

if(BT!=NULL){

printf(“%c”,BT->data);

Postorder(BT->left);

Postorder(BT->right);

}

}

24.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

void Postorder(struct BTreeNode *BT){

if(BT!=NULL){

Postorder(BT->left);

printf(“%c”,BT->data);

Postorder(BT->right);

}

}