数据结构学习指导第5章树

本章要点

一、树的概念

1. 树（树型结构的简称）的定义

树是n≥0个有限元素的集合T，当n=0时，称为空树。在一棵非空树中， 1) 有且仅有一个特殊结点称为树的根（root）。

2) 若n>0，除根结点外的其余元素可分成m个不相交的子树，T1、T2 „„Tm。

3) 每棵子树又同样是一棵树。

4) 由此，树的定义是递归的，所以树是一种递归的数据结构。 5) 树的二元组定义：tree=（K，R） K={kI|1≤i≤n，n≥0，ki∈ElemType} R={r}其中r满足下列条件：

(1) 有且仅有一个结点没有前驱，该结点为树的根； (2) 除根结点之外，每个结点只有一个前驱结点； (3) 每个结点可以有多个后继结点。 2. 树的表示方法

树形表示法、集合表示法、凹入表示法、广义表表示法 3. 树的基本术语

1) 结点的度和树的度

每个结点具有的子树数或者说后继结点数被定义为结点的度（degree）。所有结点的度的最大值定义为树的度。

2) 分支结点和叶子结点

度大于0的结点称为分支结点或非终端结点； 度等于0的结点称为叶子结点或终端结点；

在分支结点中，又把度为1的结点称为单分支接点；度为2的结点称为双分支结点。

3) 孩子结点、双亲结点和兄弟结点 4) 结点的层数和树的深度

结点的层数（level）从树根开始定义： 树的根结点的层数为1。

其余结点的层数=其双亲层数+1

树中结点的最大层数称为树的深度（depth）或高度（height） 5) 森林

M（M≥0）棵互不相交的树的集合。 6) 有序树和无序树

一般情况下认为树是有序的。 4. 树的性质(P182) 二、二叉树的定义

1. 二叉树(binary tree)

二叉树是一种特殊的树型结构，树中的每个结点至多有两棵子树（左子树和右子树，即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。 2. 二叉树分类

二叉树的性质的特征值的不同，可将二叉树分为以下几种基本形态： 1) 满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树的称为满二叉树。

特点：第i层的结点数为2i-1：P184图5－7(a)。 2) 完全二叉树：除最后一层外其余层都是满的，并且最后一层是在右侧缺少连续若干个结点：P184图5－7 (b)。

一棵深度为K的有N个结点的二叉树，对树中的结点按从上至下、从左至右顺序进行编号，如果编号 i的结点与满二叉树编号i 的结点在二叉树中位置相同，则称这棵树为完全二叉树。其特点如下：  叶子结点只能在层数最大的两层上出现。  对任一结点，若其右子树的最大层次为L，则其左子树的最大层次为L或L+1。  完全二叉树除最后一层外，各层都充满了结点，每一层的结点个数恰好是上一层结点个数的2倍。

3) 理想平衡树：除最后一层外其余层都是满的，并且最后一层的结点可以任意分布：P186图5－8(a)。

4) 普通二叉树：不受以上各条件约束：P186图5－8 (b)。 三、二叉树的性质(P184)

性质1：二叉树第i层上的结点数目最多为2i-1。（i≥1） 性质2：深度为K的二叉树至多有2K-1。

性质3：对于任意一棵非空的二叉树，如果叶子结点数为n0，度为2的结点数为n2，则有：n0= n2+1。

性质4：具有n个结点的完全二叉树其深度为 log2n +1或 log2 (n+1)。 性质5：在具有n个结点的完全二叉树中，设ki是编号为i的结点 1) 若i>1，则ki的双亲编号为i/2；若i=1，则无双亲。

2) 若2i≤n，则ki的左孩子编号是2i，否则无左孩子。因此，完全二叉树中编号i>n/2的结点必定是叶结点。

3) 若2i+1≤n，则ki的右孩子编号是2i+1，否则无右孩子。

4) 若i为奇数且不为1，则ki的左兄弟编号为i-1，否则无左兄弟。 5) 若i为偶数且小于n，则ki的右兄弟编号为i+1，否则无右兄弟。 四、二叉树的存储结构 1. 顺序存储结构

顺序存储结构即用一组连续的存储单元存放二叉树中的结点。

例，对满二叉树和完全二叉树，树中结点的序号可以唯一地反映出结点之间的逻辑关系，所以可用一维数组按从上至下、从左至右的顺序存储。但是，对于一般二叉树，则需对之进行改造，增添一些不存在的空结点，使之成为一棵完全二叉树形式。

此种存储结构适用于理想二叉树，定义略。 2. 链接存储结构

类型定义

1) 定义数据域的数据类型；

2) 定义数据为通用数据类型(ElemType)； 3) 定义每个结点类型 struct BtreeNode{ ElemType data; BTreeNode *left; BTreeNode *right; };

4) 定义树根指针：BT

五、二叉树的抽象数据类型: P186 六、二叉树的运算（BTree.h）

1. 初始化

2. 二叉树的建立

二叉树的输入格式不同，建立二叉树的算法也不同，我们采用广义表方式输入：

树的输入规则：

1) 每棵树的根结点作为由子树构成的表的名字放在表的前面。 2) 若一棵树只有右子树无左子树，则右子树前面的逗号不能省略。 3) 在整个广义表的结尾加上结束标志’@’。 基本思路： A. 读入字母； B. 读入‘（’； C. 读入‘）’ D. 读入‘，’； E. 读入’@’。

3. 检查二叉树是否为空 4. 二叉树的遍历

二叉树的遍历是指沿某条路径周游二叉树，对树中每个结点访问一次且仅访问一次。

设L、D、R分别表示遍历二叉树的左子树、根结点、右子树，则有6种遍历顺序：DLR、LDR、LRD；DRL、RDL、RLD

前序遍历（DLR） 1) 访问根结点 2) 前序遍历左子树 3) 前序遍历右子树 中序遍历（LDR） 1) 中序遍历左子树 2) 访问根结点 3) 中序遍历右子树 后序遍历（LRD） 1) 后序遍历左子树 2) 后序遍历右子树 3) 访问根结点

按层遍历：非递归算法

结论：

 前序和中序序列相同的二叉树或者为空，或者是任一结点均无左子树的非空二叉树。

 后序和中序序列相同的二叉树或者为空，或者是任一结点均无右子树的非空二叉树。

 后序和前序序列相同的二叉树或者为空，或者是只有一个结点。  已知二叉树的前序和中序序列，可以唯一地确定一棵二叉树。  已知二叉树的后序和中序序列，也可以唯一地确定一棵二叉树。  已知二叉树的前序和后序序列，不能唯一确定这棵二叉树。

还有一种被成为“层次遍历”的访问方式。 5. 求二叉树深度

6. 输出二叉树（广义表形式） 7. 清除二叉树

例：P197－5－1.cpp 七、树的存储结构和运算

树是指度大于等于3的多叉树。 1. 树的存储结构

1) 标准形式：以子树个数定义指针域的个数，如P200图5－15（b）。 struct GTreeNode

{

ElemType data; //结点数据

GtreeNode *t[3]; //假定有三个指针域分别为*t[0]; *t[1]; *t[2];

};

2) 孩子表示法

typedef struct cnode {

int child;

struct cnode *next; }childnode; typedef strcut {

datatype data;

childnode *headptr; }tnode;

typedef struct {

tnode node[MAXNODE];

int n; }ctree; ctree *T;

3) 孩子兄弟表示法（二叉链表示法） 将树转换为二叉树的规则是：P201。

也就是说：只保留与长子的连线；兄弟之间用横线相连；顺时针转45度。 用语句实现如下：

fch: 指向该结点的第一个孩子。 nsib: 指向该结点的下一个兄弟。 Typedef struct csnode {

datatype data;

struct csnode *fch,*nsib; }fnode;

fnode *T;

2. 树的运算（Tree.h）

1) 建立树的存储结构； 2) 树的遍历；

3) 从树中找出结点值； 4) 树的输出； 5) 求树的深度；

6) 清除树中所有结点，使之变为一棵空树； 八、二叉搜索树

1. 二叉搜索树的定义

1) 若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；

2) 若它的右子树非空，则右子树上所有结点的关键字均大于根结点的关键字；

3) 左右子树本身又各是一棵二叉搜索树；

4) 二叉搜索树与中序遍历得到的结点序列相同。 2. 二叉搜索树的抽象数据类型 3. 二叉搜索树的运算

1) 查找； 2) 更新； 3) 插入； 4) 删除；

4. 二叉搜索树的程序举例及问题

1) 查找算法中对于是否找到没有交代。改后的程序为：P219－6－1-1.cpp。 2) 对于插入算法中如果插入的关键字是重复值应有所。改后的程序为：P219－6－1-2.cpp。

3) 插入的非递归算法的使用。改后的程序为：P219－6－1-3.cpp。 4) 以上问题中都要注意头文件的改动。 九、堆（heap） 1. 堆的定义

堆分为小根堆和大根堆，对于一个小根堆，它是有如下特性的一棵完全二叉树：

若树根结点存在左孩子，则根结点的值小于等于左孩子结点的值； 若树根结点存在右孩子，则根结点的值小于等于右孩子结点的值； 以左、右孩子为根的子树又各是一个堆。

大根堆的定义与上类似，只要把“小于等于”改为“大于等于”即可。 例：

18267348(a)60183525225336744235(b)20

2. 堆的抽象数据类型 3. 堆的存储结构

由于堆是完全二叉树，适合用顺序存储，见P222图6－5，按层遍历即可得到与数组下标相对应的结点值。 0 18 122635

354607348

0 1 2 3 4 5 6 7 8 9

18 26 35 73 48 60

当一个堆采用顺序存储结构时，需要定义一个元素类型为ElemType、长度为MaxSize的一个数组来存储堆中的所有元素，还需要定义一个整型变量，用以存储堆的长度，即堆中当前包含的结点数。假定存储堆元素的数组名用heap表示，存储堆长度的变量名用len表示，并且把它们连同存储空间大小MaxSize一起定义在一个结构类型中，结构类型名用Heap表示，则该类型定义为：

struct Heap { //定义堆的顺序存储类型

ElemType* heap; //定义指向动态数组空间的指针 int len; //定义保存堆长度的变量

int MaxSize; //用于保存初始化时所给的动态数组空间的大小 };

堆存储结构的定义与一般线性表相类似： 如果采用动态分配数组空间： 1)定义结点元素类型；

2)定义结点为通用元素类型； 3)定义堆 struct Heap{ ElemType *heap; int len;

int MaxSize; };

4. 堆的运算（heap.h）

1) 初始化堆

2) 清除堆

3) 检查一个堆是否为空 4) 向堆中插入一个元素 5) 从堆中删除元素

6) 构成初始堆与堆排序（P348） 例：P226－6－2.cpp 十、哈夫曼（Huffman）树

哈夫曼树又称最优树，它是带权路径长度最短的树。 1. 基本术语

1) 路径和路径长度

若在一棵树中存在着一个结点序列k1, k2, k3….. kj，使得ki是kI+1的双亲，则此结点序列是k1到kj的路径。（也是唯一路径）

从k1到kj所经过的分支数称这两点之间的路径长度，它等于路径上的结点数减一。

2) 结点的权和带权路径长度

若将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的权。 结点的带权路径长度：从树根结点到该结点之间的路径长度与该结点上权的乘积。

3) 树的路径长度

从树根到树中每个结点之间路径长度之和。 路径长度最短的二叉树是完全二叉树。 4) 树的带权路径长度

树中所有叶子结点的带权路径长度之和。通常记为：

WPL=WiLi

i1n例如，给出权是｛2，3，4，11｝，我们可以构造出不同的扩充二叉树，下页图中所示为其中三种。它们的带权外部路径长度分别为

(a) WPL = 1×11 + 2×4 + 3×2 + 3×3 = 34 (b) WPL = 2×3 + 3×4 + 3×11 + 1×2 = 53 (c) WPL = 2×2 + 2×11 + 2×3 + 2×4 = 40

5) Huffman树

它是N个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。 例：P228图6－8。

2. 构造Huffman树

1)根据给定的N个权值{ W1„Wn},构成N棵二叉树的集合F={ T1„Tn}，其中，每棵二叉树Ti中只有一个权值为Wi的根结点，其左右孩子为空。

2)在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新二叉树根结点的权值为左右子树上根结点的权值之和。

3)在F中删除这两棵树，同时将新得到的二叉树加入到F中。 重复（2）、（3）步，直到F中只含有一棵树为止，这棵树便是Huffman树。 例：

3. Huffman编码

若想产生哈夫曼编码要分二步：构造Huffman树；在哈夫曼树上求叶结点的编码。

哈夫曼树的构造算法：P229：CreateHuffman( ) 求哈夫曼编码:P232:Huffmancoding( )。 例P232－6－3.cpp。 十一、线索二叉树 1. 什么是线索二叉树

1) 线索化的目的：

二叉树中按某种遍历得到的结点序列，可以看作一个线性表。为区分这种不同的前驱结点和后继结点,我们将为其冠以序列名称“中序前驱”、“中序后继”。

2) 线索化二叉树的种类

规定：当某结点的左指针为空时，令其指向依某种方式遍历时所得到的该结点的前趋结点，否则指向它的左孩子；当某结点的右指针为空时，令其指向依某种方式遍历时所得到的该结点的后趋结点，否则指向它的右孩子。把指向前趋或后继结点的指针称为线索，加上了线索的二叉树称为线索二叉树。

线索二叉树可分为前序线索二叉树、中序线索二叉树（我们只讨论此类）、后序线索二叉树。

3) 线索二叉树的结点结构（主要是标志域的应用） 如图： Left ltag data rtag right struct TTreeNode {

ElemType data

int ltag,rtag;

TTreeNode *left,*right; };

ltag =0 lchild指向结点的左孩子结点；

ltag =1 lchild指向结点的前趋结点； ltag =0 rchild指向结点的右孩子结点； ltag =1 rchild指向结点的后继结点。 4) 二叉树的线索化过程（算法）（以P234图6-12为例） (1) A与D的关系 (2) E与A的关系 (3) 如D

(4) pre为当前结点变量

2. 线索二叉树的运算（利用线索进行遍历）

1) 查找某结点*p在指定次序下的后继

(1) 若p->rtag=1，则p->rchild为右线索，它指向p的后继；

(2) 若p->rtag=0，则p->rchild指向右孩子，其后继是其右子树中第一个遍历的结点。

2) 遍历线索二叉树（从根起不断查找后继）

(1) 从根结点开始沿左指针往下查找，直到一个左线索ltag=0的结点； (2) 该结点必是整个中序列的第一个结点； (3) 访问该结点；

(4) 用求后继的算法访问其后继。

本章重点

树和二叉树的基本概念；二叉树的存储结构；二叉树的运算。二叉排序树的定义；二叉排序树的运算。堆的定义和运算；构造Huffman树。

本章难点

二叉树的部分算法；线索二叉树；二叉排序树的部分算法；堆的部分算法。

本章习题

一、填空

1、二叉树的度为：________。

2、在定义各种数据结构的存储实现时，为增强其数据类型的通用性，应将其定义为________类型。如果是定义树的链接存储结构，除了定义数据类型，还应定义链接孩子结点的________和________。

3、二叉树的度为2，当深度h=4时，其满二叉树的结点数为：________。 4、同一棵树中的数据元素必须是________的。

5、由3个结点所构成的二叉树有________种形态。

6、对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子，则左孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双亲，则双亲结点的编号为________。

7、在一棵高度为5的理想平衡树中，最少含有________个结点，最多含有________个结点。

8、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为________个，树的深度为________，树的度为________。

9、若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶子结点的个数为K，则左、右子树皆非空的结点个数是________。

10、在树中，一个结点的直接后继结点的个数称为该结点的________。

11、排序二叉树是指树上所有________结点均大于________左右子树所有结点，同时左右子树又各是一棵排序二叉树。 12、在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为________。WPL称为________。

13、对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个________。 14、当向一个小根堆插入一个具有最小值的元素时，需要逐层________调整，直到被调整到________位置为止。

15、在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左孩子元素的下标为________，右孩子元素的下标为________。

16、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是________。

17、向二叉搜索树中插入一个元素时，其时间复杂度大致为________。 18、从堆中插入一个元素的时间复杂度为________。

19、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明________，若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的值，则继续向________查找。 20、在一个小根堆中，堆顶结点的值是所有结点中的________，在一个大根堆中，堆顶结点的值是所有结点中的________。

二、选择题

1、一个广义表形式的二叉树A（B,C（，D）），此二叉树的深度为( )。

A. 1 B. 2 C. 3 D. 4

2、如果有一棵完全二叉树上的结点数是9，那么这棵二叉树的最大深度是( )。 A. 2 B. 3 C. 4 D. 5 3、下列关于二叉树遍历的叙述中，正确的是( )。

A. 若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点

B. 若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点

C. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点

D. 若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点

4、高度k的二叉树的最大结点数为( )。

A. 2k-1 B. 2K+1 C. 2K-1 D. 2k-1 5、树最适合用来表示( )。 A. 有序数据元素 B. 无序数据元素

C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据

6、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为( )个。

A. 15 B. 16 C. 17 D. 47

7、假定一棵三叉树的结点数为50，则它的最小高度为( )。 A. 3 B. 4 C. 5 D. 6

8、在一棵二叉树上第5层的结点数最多为( )。 A. 8 B. 16 C. 15 D. 32

9、用顺序存储方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有子树，则左子树是结点( )。

A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 10、在一棵具有k层的满三叉树中，结点总数为( )。 A. (3k-1)/2 B. 3k-1 C. (3k-1)/3 D. 3k

11、从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 12、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

A. 24 B. 48 C. 72 D. 53 13、以下说法中错误的是( )。

A. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近

B. 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点

C. 已知二叉树的前序遍历和后序遍历并不能惟一地确定这棵树，因为不知道树的根结点是哪一个

D. 在前序遍历二叉树的序列中任何结点其子树的结点都是直接跟在该结点之后的

14、对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的排序序列。 A. 先序 B. 中序 C. 后序 D. 按层次 15、从堆中删除一个元素的时间复杂度为( )。

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)

16、利用n个值作为叶结点的权生成的哈夫曼树包含有( )个结点。 A. n B. n+1 C. 2*n D. 2*n-1 17、在线索二叉树中，每个结点包含有( )个域。 A. 3 B. 4 C. 5 D. 6

18、利用3、6、8、12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( )。

A. 18 B. 16 C. 12 D. 30

19、在一棵具有n个结点的线索二叉树中，共有( )个指针域保存线索。 A. n B. n-1 C. n+1 D. n+2

20、根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为( )。 A. O(n) B. O(log2n) C. O(n2) D. O(nlog2n) 21、下面叙述正确的是( )。

A. 二叉树的第i层最多有2i-1个结点 B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树

D. 二叉树的左右子树有次序之分

22、已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为( )。 A. 1 B. 2 C. 3 D. 4 23、从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为( )。 A. O(n) B. O(1)

C. O(logn/log2) D. O(n*n)

24、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个。 A. 4 B. 5 C. 6 D. 7

25、假定一棵三叉树的结点数为50，则它的最小高度为( )。 A. 3 B. 4 C. 5 D. 6

26、根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树( )。 A. 是完全二叉树

B. 不是完全二叉树 C. 是满二叉树 D. 不是满二叉树

27、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明查找成功，若元素的值( )根结点的值，则继续向左子树查找。 A. 大于

B. 大于等于 C. 小于

D. 小于等于

28、向一棵二叉搜索树中插入一个元素时，若元素的值( )根结点的值，则接着向根结点的右子树插入 A. 大于

B. 大于等于 C. 小于

D. 小于等于

29、在一棵二叉树上第4层的结点数最多为( )。 A. 2 B. 4 C. 6 D. 8

30、设n和m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是( )。

A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙 31、如果F是由有序树T转换而来的二叉树，那么T中结点的后序就是F中结点的( )。 A. 中序 B. 前序 C. 后序 D. 层次序

32、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( )。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对

33、在一棵二叉搜索树中，每个分支结点的右子树上所有结点的值一定( )该结点的值。 A. 大于

B. 大于等于 C. 小于 D. 小于等于

34、用整数1,2,3,4,5作为五个树叶的权值，可构造一棵带树路径长度值为( )

的哈夫曼树。

A. 33 B. 15 C. 34 D. 54

35、在下列存储形式中，( )不是树的存储结构。 A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法

36、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是( )。 A. EGFACDB B. EACBDGF C. EAGCFBD D. 上面都不对

37、二叉树若用顺序方法存储，则下列四种运算中的( )最容易实现。 A. 前序遍历二叉树

B. 判断两个指定结点是不是在同一层上 C. 层次遍历二叉树

D. 根据结点的值查找其存储位置

38、在高度为h的完全二叉树中，( )。 A. 度为0的结点都在第h层上

B. 第i(1≤i39、利用二叉链表存储树，则根结点的右指针是( )。 A. 指向最左孩子 B. 指向最右孩子 C. 空 D. 非空

40、把一棵树转换为二叉树后，这棵二叉树的形态是( )。 A. 唯一的 B. 有多种

C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子

三、能力测试题

1. 有一棵树，以图形表示法如下：

B A D C 要求：

1) 以广义表表示： A（B，C（，D））。 2) 求出此树的深度。 3) 写出中序遍历的结果。 4) 画出链接存储方式。

5) 如果以C结点为根（不考虑A、B），开始代入求深度的算法，写出递归过程。

2. 已知一棵二叉树如下，要求

1) 写出递归的中序遍历算法；

2) 根据以上算法写出应打印输出值。

A

B D C F E 3. 假定一棵二叉树广义表表示为a(b(c,d),e(f(,g)))，分别写出对它进行先序、中序和后序遍历的结果。

4. 给定二叉树的两种遍历序列，前序遍历序列：DACEBHFGI；中序遍历序列：DCBEHAGIF。试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

5. 如图所示，一棵二叉树的结点数据采用顺序存储结构存储于数组中，请画出该二叉树的链式存储表示。

1 e 2 a 3 f 4 5 d 6 7 g 8 9 10 11 12 13 14 15 16 17 18 19 20 21 c j i h b 6. 试写出下图所示二叉树的“先序、中序、后序”遍历时得到的结点序列。

7. 假定一棵二叉树广义表表示为A(B(,D),C(E(G),F))，分别写出对它进行先序、中序、按层遍历的结果。

8. 有5个带权结点，其权值分别为3,7,2,6,14，以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度和树的高度。

9. 若以数据集{4,5,6,7,10,12,18}为结点的权值构造huffman树，试画出该huffman树，并计算带权路径长度WPL。 10. 把下图所示的树转换成二叉树。

11. 画出和下列二叉树相应的森林。

12. 将一组元素37,56,23,65,22,10,29依次插入一棵空二叉搜索树中，请画出该二叉搜索树。

13. 用关键字值存于A[ ] ={24 , 38, 11, 77 , 94, 26 , 44, 68，55 }的完全二叉树建大根堆。

要求1：画出建初始化大根堆的“筛”运算过程中二叉树的图形变化过程。 要求2：给出排序结果，并画出排序过程中堆的变化。

14. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。

15．已知一棵二叉搜索树的广义表表示为：28(12(,16),49(34(30),72(63)))，求出从中依次删除72,12,49,28结点后，得到的二叉搜索树的广义表表示。

四、算法填空

1．向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。 void Insert(BtreeNode*& BST, const ElemType& item) {

if(BST==NULL)

{ BtreeNode* p=new BtreeNode; p->data=item;

_______________________; BST=p; }

else if(itemdata) ___________________; else ________________________; }

2.下面算法中的BT指向一棵具有n个元素的二叉树的根结点。

void preserve(BTreeNode* BT, ElemType a[], int n) {

static int i=0; if(BT!=NULL) {

preserve(BT->left, a, n);

a[i++]=BT->data;

preserve(BT->right, a, n); } }

说明该算法功能_____;。 3. 下面算法的功能为：根据BT所指的二叉树生成一棵新的二叉树并返回树根指针，新二叉树是已知二叉树BT中所有结点的左、右子树交换的结果。 BTreeNode* BTreeSwopX(BTreeNode* BT) {

if(BT==NULL) return ________; else {

BTreeNode* pt=new BTreeNode; pt->data=______________;

pt->right=______________________; pt->left=BTreeSwopX(BT->right); return pt; } }

4. 该函数的功能是统计出BT所指向的二叉树中大于给定值x的结点个数并返回 int BTreeCount(BTreeNode* BT, ElemType x) {

if(BT==NULL) ______________; else if( ______________)

return BTreeCount(BT->left,x)+BTreeCount(BT->right, x)+1; else

return BTreeCount(BT->left,x)+ _____;

}

5. 下面函数的功能是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。

BinTreeNode* BTF(BinTreeNode* BT, ElemType x) {

if(BT==NULL) _______________; else {

if( BT->data==x) ______________; else {

BinTreeNode* t;

if(t=BTF(BT->left, x)) return t;

if(t=______________________) return t; return NULL;

} }

}

6. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedef struct node {

int data;

struct node *lchild; ________________; }bitree;

void createbitree(bitree *&bt) {

scanf(“%c”,&ch);

if(ch=='#') ___________; else {

bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;

createbitree(bt->rchild); } }

7. 下面算法中的BST为指向二叉搜索树的树根指针。 ElemType FindMax(BTreeNode* BST) {

if(BST==NULL){

cerr<<\"不能在空树上查找最大值!\"<BTreeNode* t=BST; while(t->right!=NULL) t=t->right; return t->data; }

说明该算法功能_____;

8. 下面函数的功能是求一棵二叉搜索树中单分支节点数。，请在下划线处填上正确的内容。

int Count(BTreeNode* BST) {

if(BST==NULL) _______________; //二叉树为空，返回 else if(BST->left==NULL && BST->right!=NULL) return Count(BST->right)+1; else if _______________;

return Count(BST->left)+1;

else return _______________;

9.下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。

int NodeLevel(BTreeNode * BT, char X) {

if(BT==NULL) return 0; /*空树的层号为0*/

else if(BT->data==X) return 1; /*根结点的层号为1*/ /*向子树中查找X结点*/ else{

int c1=NodeLevel(BT->left,X); if(c1>=1)________（1）__________; int c2=________（2）__________; if________（3）__________; /*若树中不存在X结点则返回0*/ else return 0; } }

10. 分析下列函数的功能。 void BTC(BTreeNode* BT) {

if(BT!=NULL){

if(BT->left!=NULL && BT->right!=NULL)

if(BT->left->data > BT->right->data){

BTreeNode *t=BT->left; BT->left=BT->right; BT->right=t;

}

BTC(BT->left); BTC(BT->right); }

五、算法设计

1. 已知某二叉搜索树的结点的数据域为记录类型，定义为worker，其数据域由3个值域组成，含义分别为编号code、姓名name、年龄age。其中编号code为关键值域（查找字段域）。此二叉搜索树采用链接存储。 以下要求用C++实现：

1）定义二叉树结点（包括对数据域的定义）；

2）假设已有一棵二叉搜索树，写出将值为item的元素插入树中的算法。 3）以下两个要求中，可任选一题

(1)写出生成二叉搜索树的算法，并将排序结果存储于一维数组中；

(2)对要求2的算法用框图表示。

2. 根据下面函数原型，编写一个递归算法，统计并返回以BT为树根指针的二叉树中所有叶子结点的个数。

int Count(BTreeNode* BT);

3. 编写递归算法，计算二叉树中所有结点的数目，其值由函数返回。

int BTreeCount(BTreeNode* BT);

4. 编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。 5. 编写一算法，求出一棵二叉树中所有结点数和叶子结点，假定分别用变参C1和C2统计所有结点数和叶子结点数，初值均为0。

6. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A的A[1]～A[n] 中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。 7. 设计一个求结点x在二叉树中的双亲结点算法。

8. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 9. 设计判断两个二叉树是否相同的算法。 10. 写出对二叉树进行中序遍历的非递归算法。

本章实验及实验指导

一、二叉树及应用

◆实验目的

1、掌握二叉树的存储结构

2、理解二叉树操作实现的头文件（btree.h）和其应用 3、理解二叉树的递归结构及递归算法

◆实验内容

1、编写二叉树操作实现的头文件btree.h。 2、编写一个程序P197－5－1.cpp，要求如下： 1）建立一棵二叉树的存储结构（数据类型为字符） 2）按广义表形式输出

3）分别用前序、中序、后序、按层遍历算法输出所有结点 4）查找字符

5）求此二叉树深度 6）清除此二叉树

二、树及应用 ◆实验目的

1、掌握树的存储结构

2、理解树操作实现的头文件（tree.h）和其应用 3、理解树的递归结构及递归算法

◆实验内容

1、编写树操作实现的头文件tree.h。

2、编写一个程序P206－5－2.cpp，要求如下： 1）建立一棵树的存储结构（数据类型为字符）

2）分别用先根遍历、后根遍历、按层遍历算法输出所有结点 3）按广义表形式输出 4）查找字符 5）求此树深度 6）清除此树

三、二叉搜索树及应用 ◆实验目的

1、掌握二叉搜索树的定义、存储结构及原理 2、掌握二叉搜索树的操作实现

3、理解二叉搜索树的更新和删除操作实现 ◆实验内容

1、编写二叉搜索树的操作实现的头文件BSTree.h 2、编写一个程序P219－6－1.cpp，要求如下： 1）建立一棵二叉搜索树（数据类型为正整数） 2）按广义表输出此二叉搜索树 3）输出此二叉搜索树的深度 4）在二叉搜索树上进行查找操作 5）向此二叉搜索树中插入一个结点

6）删除二叉搜索树上的某个结点，删除成功后重新输出此二叉搜索树

四、堆和哈夫曼树

◆实验目的

1、掌握堆的定义、存储结构及原理 2、掌握堆的运算

3、掌握哈夫曼树的定义 4、掌握构造哈夫曼树的方法 ◆实验内容

1、编写堆运算实现的头文件heap.h

2、编写一个程序P226－6－2.cpp，要求如下： 1）建立一个小根堆（数据类型为正整数） 2）按下标位置依次输出堆中的每个元素 3）依次删除堆顶元素并输出，直到堆空 3、（选作）用P229－P230的CreateHuffman()和WeightPathLength()构造一个哈夫曼树，求出此哈夫曼树的带权路径长度，元素类型为正整数。

本章拓展性训练

1、组织机构问题

问题描述：以物资学院为例，实现对我校组织结构的管理。要求把我校的组织结构以树型结构存储，实现要求：

（1）树中每个结点保存部门名称；

（2）假定处级部门（含院系）在树中第二层，科级部门在第三层（即最后一层），软件应该能计算出处级部门有几个，有哪几个？ （3）软件可以查询某部门下面的具体编制？ 2、文件压缩解压

利用Huffman树实现文件的压缩和解压。

问题描述：假定待压缩的文本以数组方式存储。 实现要求：

（1）具备提示输入待压缩字符串、输出字符串的功能。

（2）首先对待压缩字符串进行文本分析，得到文本的组成字符包含在数组

ch[]中，以及字符的出现频度在数组pin[]中。

（3）压缩文本，输出压缩结果。并将压缩后的字符串保存在另外的数组中。 （4）文本解压。

本章习题答案

一．填空 1、2

2、通用数据（ElemType） 左指针域(left) 右指针域(right) 3、15

4、同质（或同类型） 5、5

6、2i 2i+1 i/2（或i/2） 7、16 31 8、10 4 3 9、k-1 10、度

11、右 根节点

12、哈夫曼树 带权路径长度 13、有（或升）序序列 14、向上 根 15、2i+1 2i+2 16、33

17、O(log2n) 18、O(log2n)

19、查找成功 左子树 右子树 20、最小值 最大值

二、选择

1、C 2、C 3、D 4、A 5、C 6、B 7、C 8、B 9、B 10、A 11、C 12、D 13、A 14、B 15、B 16、D 17、C 18、A 19、C 20、D 21、D 22、B 23、A 24、C 25、C 26、A 27、C 28、A 29、D 30、B 31、A 32、A 33、A 34、A 35、D 36、B 37、C 38、C 39、C 40、A

三、能力测试题 1. 答：

1）以广义表表示： A（B，C（，D））。 2）此树的深度是： 3 。

3）写出中序遍历的结果： BADC 。 4）画出链接存储方式。略

5）如果以C结点为根（不考虑A、B），开始代入求深度的算法，写出递归过程。略

2. 答：

1）void Inorder(BtreeNode* BT)

}

{

if(BT!=NULL){ }

Inorder(BT->left); Cout<data<<‟ „; Inorder(BT->right);

2）BDACFE 3. 答：

先序： a,b,c,d,e,f,g 中序： c,b,d,a,f,g,e 后序： c,d,b,g,f,e,a 4. 答：

由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 5. 答：

6. 答：

先序：A B D F J G K C E H I L M 中序：B F J D G K A C H E L I M 后序：J F K G D B H L M I E C A 7. 答：

先序：A,B,D,C,E,G,F; 中序：B,D,A,G,E,C,F; 按层：A,B,C,D,E,F,G 8. 答：

带权路径长度：66 高度：5 9. 答

WPL=(4+5)*4+(6+7+10)*3+(12+18)*2=36+69+60=165 10. 答：

11. 答：

12. 答：

构造的二叉搜索树如下图所示：

37 23 56 22 29 65 10 13. 答：

（1）完全二叉树（初始）：

68 55 38 11 44 24 77 94 26 （2）筛77（不动）： （3）筛11（下移一层）： （4）筛38（下移一层）： 68 55 94 44 11 24 68 55 38 44 11 24 68 55 38 11 44 24 77 94 26 77 94 26 77 38 26 （5）筛24（下移三层）： 第一次下移： 第二次下移： 第三次下移： 24 55 77 44 11 94 68 55 77 44 11 94 68 55 24 44 11 94 77 38 26 24 38 26 68 38 26 答2：排序结果：11，24，26，38，55，68，77，94 过程1：94与55 对调 筛55 ，下移二层 24 94 68 44 11 77 24 94 77 44 11 55 24 94 77 44 11 55 68 38 26 68 38 26 55 38 26 过程2：77与24对调 筛24 ，下移二层 过程3：68与11对调 77

94

55 44 68

11 77

94

55 44 11

68 77

94

68 44 11

24 55 38 26 24 38 26 24 38 26 筛11 ，下移一层 过程4：55与26对调 筛26 ，下移一层 77

94

11 26 55 68

44 77

94

11 44 55 68

26 77

94

11 44 68

55 24 38 26 24 38 24 38 过程4：44与38对调 筛38，不动 过程5：38与24对调 筛24 ，下移一层 77

94

38

44

55

68

11 24

26 77

94

38

44

55

68

11 26

24 77

94

11 44 55 68 26

38 24 过程6：26与24对调 筛24，不动

过程7：24与11对调 77

94

38

44

55

68

24

11 26 77

94

38

44

55

68

11 26

24 输出数组得到排序结果：11，24，26，38，55，68，77，94 14. 答： 哈夫曼树

哈夫曼编码 字母编对应编码 出现频号 率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 11111 0.03 7 01 0.21 8 1101 0.10 WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 15. 答： 图形略。

对应的广义表表示如下，其中(0)行代表已知二叉搜索树. (0) 28(12(,16),49(34(30),72(63))) (1)28(12(,16),49(34(30),63)) (2)28(16,49(34(30),63)) (3) 28(16,34(30,63)) (4)16(,34(30,63)) 四、算法填空 1．答：

p->left=p->right=NULL Insert(BST->left, item) Insert(BST->right, item) 2. 答：

算法功能：对具有n个结点的由BT指针所指向的二叉树进行中序遍历，把得到的结点值序列保存到数组a中。 3. 答：

NULL BT->data BTreeSwopX(BT->left) 4. 答：

return 0 BT->data>x BTreeCount( BT->right, x) 5. 答：

return NULL return BT BTF(BT->right, x) 6. 答：

struct node *rchild，bt=0，createbitree(bt->lchild) 7. 答： 算法功能：非递归算法求出二叉排序树中的关键字最大的元素，即从二叉排序树中返回关键字最大的元素 8. 答：

return 0;

(BST->left!=NULL && BST->right==NULL) Count(BST->left)+Count(BST->right); 9. 答：

(1) return c1+1

(2)NodeLevel(BT->right,X) (3)(c2>=1)return c2+! 10. 答：

算法功能：当BT中每个结点的左孩子的值大于右孩子的值则交换左右子树。 五、算法设计 1.答：

1） struct worker{ char code[4]; char name[10]; int age; };

typedef worker ElemType; struct BTreeNode{ ElemType data; BTreeNode* left; BTreeNode* right; };

2) void Insert(BtreeNode *&BST,ElemType &item) {

if(BST==NULL){

BtreeNode *p=new BtreeNode; p->data=item;

p->left=p->right=NULL; BST=p; }

else if(item.keydata.key)

Insert(BST->left,item); Else Insert(BST->right,item) }； 3) (1)

void CreateBSTree(BtreeNode*&BST,ElemType a[],int n) {

BST=NULL;

For(int I=0;IInsert(BST,a[I]); BtreeNode*p=BST; If(p!=NULL){ Inorder (p->left); A[I]=p->data; Inorder(p->right);

} }

2. 答：

int Count(BTreeNode* BT)

{ //统计出二叉树中所有叶子结点数 if(BT==NULL) return 0;

else if(BT->left==NULL && BT->right==NULL) return 1; else return Count(BT->left)+Count(BT->right); }

3. 答：

int BTreeCount ( BinTreeNode* BT ) { if ( BT == NULL ) return 0;

else return BTreeCount ( BT->leftChild ) + BTreeCount ( BT->rightChild ) + 1; }

4. 答：

参见算法设计中的BTreeDepth函数

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 {

if(T->data==x) { printf(\"%d\\n\找到了值为x的结点,求其深度 exit 1; } else { if(T->lchild) Get_Sub_Depth(T->lchild,x); if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 }

}//Get_Sub_Depth

int BTreeDepth(BTreeNode* BT) {//求子树深度的递归算法 if(BT==NULL) return 0; else { int dep1=BTreeDepth(BT->left); int dep2=BTreeDepth(BT->right); if(dep1>dep2) return dep1+1; else return dep2+1; } }

5. 答：

void Count(BTreeNode* BT,int& C1,int& C2) //分别统计出二叉树中所有结点数和叶子结点数 {

if(BT!=NULL){

C1++;//统计所有结点

if(BT->left==NULL&&BT->right==NULL)

C2++; //统计叶子结点数 Count(BT->left,C1,C2); Count(BT->right,C1,C2); }

}

6. 答：

首先，由于是完全二叉树，不必担心中途会出现孩子为null的情况。 其次分析：结点i的左孩子为2i，右孩子为2i+1;直接打印即可。

Printf(“Left_child=”, %d, v[2*i].data; “Right_child=”, %d, v[2*i+1].data;);

但其双亲是i/2，需先判断i为奇数还是偶数。若i为奇数，则应当先i-- ，然后再除以2。 If(i/2!=0)i--;

Printf(“Parents=”, %d, v[i/2].data;); 程序代码：

void Request(int a[],int n,int i)

//从数组A中打印出编号为i的结点的双亲和孩子 {

if(i>n){

cerr<<\"编号为\"<cout<<\"current element:\"<int j=i/2; //下标为j的结点是下标为i结点的双亲 if(j>0)

cout<<\"parent:\"<cout<<\"树根结点没有双亲结点!\"<cout<<\"left child:\"<else if(2*i==n){

cout<<\"left child:\"<cout<<\"no children!\"<7. 答：

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;

bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) {

if (bt!=0 && flag==0)

if (bt->data==x) { flag=1; return;}

else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } }

void parent(bitree *bt,char x) {

int i;

preorder(bt,x);

for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\"not found x\\n\");

else if (i<=r) printf(\"%c\}

8. 答：

typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) {

bitree *p;

if(bt==0) return;

swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; }

9. 答：

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) {

if (bt1==0 && bt2==0) return(1);

else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0); else

return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); }

10. 答：

void InorderN(BTreeNode*BT)

//对二叉树进行中序遍历的非递归算法 {

BTreeNode* s[10];//定义用于存储结点指针的栈 int top=-1;定义栈顶指针并赋初值使s栈为空

BTreeNode* p=BT;//定义指针p并使树根指针为它的初值 while(top!=-1||p!=NULL)

{//当栈非空或p指针非空时执行循环

while(p!=NULL){

top++;

s[top]=p; p=p->left; }

if(top!=-1){

p=s[top]; top--;

cout<data<<''; p=p->right; } } }