第六章树

一、基本要求、重点、难点

本章目的是介绍二叉树的定义、性质、存储结构、遍历。树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树等内容。

本章重点是掌握二叉树的遍历算法及有关应用。难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。

二、考核目标、考核要求

1.树的概念，要求达到“理解”层次

1.1树的逻辑结构特征。

1.2树的不同表示方法。

1.3树的经常使用术语及含义。

2.二叉树，要求达到“简单应用”层次

2.1二叉树的递归定义及树与二叉树的区别。

2.2二叉树的性质、了解对应的证明方法。

2.3二叉树的两种存储方法、特点及适应范围。

3.二叉树的遍历，要求达到“综合应用”层次

3.1二叉树的三种遍历算法，理解其运行过程。

3.2确定三种遍历所得到的对应的结点訪问序列。

3.3以遍历算法为基础，设计有关算法解决简单的应用问题。

4.树和森林，要求达到“理解”层次

4.1树和森林与二叉树的转换方法。

4.2树的各种存储结构及其特点。

4.3树的两种遍历方法。

5.哈夫曼树及其应用，要求达到“简单应用”层次

5.1最优二叉树和最优前缀码的概念及特点。

5.2哈夫曼算法的思想。

5.3依据给定的叶结点及其权值构造出对应的最优二叉树。

5.4依据最优二叉树构造相应的哈夫曼编码。

三、练习题

1.单项选择题

1.1设深度为K的二叉树上仅仅有度为0和度为2的结点。则此类二叉树中所包括的结点数至少为（ ）

A) k+1                    B)2k+1                C) 2k-1                D) 2k

1.2按二叉树的定义，具有3个结点的二叉树有（ ）种

A) 5                 B)4                     C) 3                      D) 6

1.3深度为6的二叉树至多有（ ）个结点

A) 16               B)32                    C) 64             D)63

1.4二叉树的第6层上最多有（ ）个结点

A) 16               B)32                   C) 64             D) 63

1.5深度为6的全然二叉树至少有（ ）个结点

A) 31               B)32                   C) 63            D) 64

1.6某二叉树共同拥有4个叶结点，则其度为2的结点数共同拥有（ ）个

A) 5                 B)4                     C) 3                     D)无法计算

1.7某二叉树仅仅有度为0和度为2的结点，当中度为2结点数为8个，则该二叉树共同拥有（ ）个结点

A) 15               B)17                   C) 16                   D) 无法计算

1.8从1開始。对满二叉树从树根起，自上层到下层，每层从左到右给每一个结点顺序编号，其第8层（如果第8层存在）第一个结点的编号是（ ）

A) 256              B)255                  C) 127                 D) 128

1.9某全然二叉树共同拥有68个结点，从1開始，对其从树根起，自上层到下层，每层从左到右给每一个结点顺序编号。编号为32的结点的左孩子的编号是（ ）

A) 16               B)64                   C) 65                   D) 无左孩子

1.10某全然二叉树共同拥有92个结点，从1開始，对其从树根起，自上层到下层，每层从左到右给每一个结点顺序编号，编号为46的结点的右孩子的编号是（ ）

A) 23               B)24                   C) 92                   D) 无右孩子

1.11某全然二叉树共同拥有48个结点，从1開始，对其从树根起。自上层到下层，每层从左到右给每一个结点顺序编号。编号为15的结点的双亲结点的编号是（ ）

A) 7                 B)8                     C)30                   D)31

1.12假设T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（ ）

A)前序           B)中序               C) 后序               D)层次序

1.13假设T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）

A)前序           B)中序                 C) 后序               D)层次序

1.14树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历、后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树的相应二叉树，结论（ ）是正确的

A)树的先根遍历序列与其相应的二叉树的先序遍历序列同样

B)树的后根遍历序列与其相应的二叉树的后序遍历序列同样

C)树的先根遍历序列与其相应的二叉树的中序遍历序列同样

D)以上都不正确

1.15不论什么一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（   ）

A)不发生改变 B) 发生改变        C)不能确定        D) 都不正确

1.16一棵哈夫曼树，共同拥有13个叶结点。则该哈夫曼树的结点总数为（   ）

A) 25               B) 26                    C) 27                   D) 无法计算

1.17一棵非空的二叉树的前序遍历序列和后序遍历序列正好相反。则该二叉树一定满足（   ）

A)当中随意一个结点均无左孩子

B)当中随意一个结点均无右孩子

C)当中仅仅有一个叶子结点

D)是随意一棵二叉树

1.18将一棵有100个结点的全然二叉树从根这一层開始，每一层从左至右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子编号为（   ）

A) 98               B)99                   C) 50                   D) 48

1.19有64个结点的全然二叉树（根的层次为1）的深度为（   ）

A) 8                 B)7                     C)6                     D)5

1.20一棵深度为k的二叉树全然二叉树至少有（   ）个结点

A) 2^k                B)2^k-1                  C)2^k+1                 D) 2^k-1

2.填空

2.1深度为K的全然二叉树上至多有[   ]个结点。

2.2深度为K的全然二叉树上至少有[   ]个结点。

2.3在一棵二叉树中，度为0的结点数为n₀。度为2的结点数为[   ]。

2.4一棵二叉树的第i（i≥1）层最多有[   ]个子结点。

2.5一棵全然二叉树共同拥有25个结点，其深度为[   ]。

2.6深度为5的满二叉树中共同拥有[   ]个度为1的结点。

2.7在具有n个结点的二叉树的二叉链表中。共同拥有[   ]个空链域。

2.8有n个叶结点的哈夫曼树共同拥有[   ]个结点。

2.9树的后根遍历序列与其相应二叉树的[   ]遍历序列同样。

2.10树的三种经常使用表示法中方便于求双亲或祖先结点，但求指定结点的孩子或其后代则可能要遍历整个树的表示法是[   ]。

2.11树的三种经常使用表示法中方便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算的表示法是[   ]。

2.12二叉树的顺序存储结构中，一棵仅仅有k个结点的二叉树最多需[   ]个结点的存储空间。

2.13对不论什么一个二叉树，假设其终端结点数8个。则其度为2的结点数为[   ]个。

2.14一棵哈夫曼树。假设其非叶结点数17个，则该二叉树共同拥有[   ]个结点。

3.简答

3.1树

3.2二叉树

3.3遍历

3.4哈夫曼树

4.应用

4.1已知一棵二叉树的中序遍历序列为dgbaechf。前序遍历序列abdgcefh，画出该二叉树，并求出该二叉树的后序遍历序列。

4.2已知一棵二叉树的中序遍历序列为cbafehgd，后序遍历序列cbfhgeda。画出该二叉树，并求出该二叉树的先序遍历序列。

4.3已知森林F如图6.1所看到的。请画出其相应的二叉树BT

图6.1

4.4给出一棵树T。如图6.2，画出它的孩子链表表示法的表示。

      图6.2

4.5给出一棵树T，如图6.3所看到的。分别使用双亲表示法的表示。

               图6.3

4.6给出一棵树T。如图6.3所看到的，画出用孩子兄弟表示法的表示。

        图6.4

4.7请用分别以8，11，13。5。17，25。21作为权值的叶结点，构造一棵哈夫曼树，并求该二叉树的带权路径长度。

5.算法

5.1 void CreateHuffmanTree(HuffmanTree  T)

{//构造哈夫曼树，T[m-1]为其根结点

int i,p1,p2;

InitHuffmanTree(T); //将T初始化

InputWeight(T);     //输入叶子权值至T[0..n-1]的weight域

for (             ) { //共进行n-1次合并，新结点依次存于T[i]中

Select(T,i-1,&p1,&p2);

//在T[0. .i-1]选择两个权值最小的根结点。其序号分别为s1和s2

                   ;

T[i].lchild=p1;            //最小权值的根结点是新结点的左孩子

T[i].rchild=p2;                    //最小权值的根结点是新结点的右孩子

T[i].weight=T[p1].weight+T[p2]. weight;

 }

}