数据结构（本）课程辅导与练习-第6章 第6章树和二叉树 树是一种重要的非线性结构，从逻辑角度看，其数据元素之间体现的是一对多的非线性 关系，一切具有层次关系的问题都可以用树来描述。 一、相关术语 树、二叉树、树根、子树、有序树、无序数、森林、终端结点（叶子）、非终端结点、 结点的度、结点的层次、树的深度、满二叉树、完全二叉树、理想二叉树、孩子、双亲、左 孩子、右孩子、先序遍历、中序遍历、后序遍历、层次遍历、哈夫曼树、最优二叉树、路径、 路径长度、权、带权路径长度、哈夫曼编码。 二、树的概念 树的定义 树的递归定义： 树(Tree)是n(n≥O)个结点的有限集T,T为空时称为空树，否则它满足如下两 个条件： (1)有且仅有一个特定的称为根(Root)的结点： (2)其余的结点可分为m(m≥0)个互不相交的子集T,T2,·,T,其中每个子集本身又是一 棵树，并称其为根的子树(Subree)。 注意： 树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又 可由若干棵更小的子树构成。 三、二叉树的定义 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的 形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简 单，因此二叉树显得特别重要。 (1)二叉树与无序树不同 二叉树中，每个结点最多只能有两棵子树，并且有左右之分。 二叉树并非是树的特殊情形，它们是两种不同的数据结构。 (2)二叉树与度数为2的有序树不同 在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩 子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 四、二叉树的存储结构 (一)顺序存储结构 该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。 结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。 1.完全二叉树结点编号 (1)编号办法
1 数据结构(本)课程辅导与练习-第 6 章 第 6 章 树和二叉树 树是一种重要的非线性结构，从逻辑角度看，其数据元素之间体现的是一对多的非线性 关系，一切具有层次关系的问题都可以用树来描述。 一、相关术语 树、二叉树、树根、子树、有序树、无序数、森林、终端结点（叶子）、非终端结点、 结点的度、结点的层次、树的深度、满二叉树、完全二叉树、理想二叉树、孩子、双亲、左 孩子、右孩子、先序遍历、中序遍历、后序遍历、层次遍历、哈夫曼树、最优二叉树、路径、 路径长度、权、带权路径长度、哈夫曼编码。 二、树的概念 树的定义 树的递归定义： 树(Tree)是 n(n≥0)个结点的有限集 T，T 为空时称为空树，否则它满足如下两 个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为 m(m≥0)个互不相交的子集 Tl，T2，…，Tm，其中每个子集本身又是一 棵树，并称其为根的子树(Subree)。 注意： 树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又 可由若干棵更小的子树构成。 三、二叉树的定义 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的 形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简 单，因此二叉树显得特别重要。 （1）二叉树与无序树不同 二叉树中，每个结点最多只能有两棵子树，并且有左右之分。 二叉树并非是树的特殊情形，它们是两种不同的数据结构。 （2）二叉树与度数为 2 的有序树不同 在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩 子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 四、二叉树的存储结构 （一）顺序存储结构 该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。 结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。 1．完全二叉树结点编号 （1） 编号办法
在一棵个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给 所有结点编号，能得到一个反映整个二叉树结构的线性序列。 【例】如下图所示。 2 C 5 6 D F G 8 10 12 13 14 15 ( M 16 Q 结点编号的完全二叉树 (2)编号特点 完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上 一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。 假设编号为i的结点是k:(1≤i≤n),则有： ①若i)1,则k:的双亲编号为[i/2]:若i=1,则K:是根结点，无双亲。 ②若2i≤n,则K:的左孩子的编号是2i:否则，K无左孩子，即K:必定是叶子。因此 完全二叉树中编号i>[n/2]的结点必定是叶结点。 ③若2i+1≤n,则K:的右孩子的编号是2i+1;否则，K:无右孩子。 ④若i为奇数且不为1，则K:的左兄弟的编号是i-1:否则，K:无左兄弟。 ⑤若i为偶数且小于n,则K:的右兄弟的编号是i+1:否则，K无右兄弟。 2.完全二叉树的顺序存储 将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[0.,n]中。 其中： bt[1.n]用来存储结点 bt[o]不用或用来存储结点数目。 【例】下表是上图的完全二叉树的顺序存储结构，bt[0]为结点数目，b[7]的双亲、左右 孩子分别是bt[3]、bt[14]和bt[15]。 下标01234567891011121314151617 bt 17AB C D E F G H I J K LM N O P Q 3.一般二叉树的顺序存储 (1)具体方法 ①将一般二叉树添上一些"虚结点”，成为”完全二叉树” ②为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给 结点编号 ③将结点按编号存入向量对应分量，其中“虚结点”用”∮“表示 2
2 在一棵 n 个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给 所有结点编号，能得到一个反映整个二叉树结构的线性序列。 【例】如下图所示。 （2） 编号特点 完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上 一层结点个数的 2 倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。 假设编号为 i 的结点是 ki(1≤i≤n)，则有： ①若 i>1，则 ki 的双亲编号为[i/2]；若 i=1，则 Ki 是根结点，无双亲。 ②若 2i≤n，则 Ki 的左孩子的编号是 2i；否则，Ki 无左孩子，即 Ki 必定是叶子。因此 完全二叉树中编号 i>[n/2]的结点必定是叶结点。 ③若 2i+1≤n，则 Ki 的右孩子的编号是 2i+1；否则，Ki 无右孩子。 ④若 i 为奇数且不为 1，则 Ki 的左兄弟的编号是 i-1；否则，Ki 无左兄弟。 ⑤若 i 为偶数且小于 n，则 Ki 的右兄弟的编号是 i+1；否则，Ki 无右兄弟。 2．完全二叉树的顺序存储 将完全二叉树中所有结点按编号顺序依次存储在一个向量 bt[0..n]中。 其中： bt[1．．n]用来存储结点 bt[0]不用或用来存储结点数目。 【例】下表是上图的完全二叉树的顺序存储结构，bt[0]为结点数目，b[7]的双亲、左右 孩子分别是 bt[3]、bt[l4]和 bt[15]。 3．一般二叉树的顺序存储 （1） 具体方法 ① 将一般二叉树添上一些 "虚结点"，成为"完全二叉树" ② 为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给 结点编号 ③ 将结点按编号存入向量对应分量，其中"虚结点"用"∮"表示
A 【例】上图中单支树的顺序存储结构如下图 下标 0123456 7 bt AφBΦΦ中C 3 (2)优点和缺点 ①对完全二叉树而言，顺序存储结构既简单又节省存储空间。 ②一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。 【例】最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存 储空间。 ③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。 4.二叉树的顺序存储结构类型定义 【参见教材】 (二)链式存储结构 1.结点的结构 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储 结点本身的数据外，还应设置两个指针域lchild和rchild,分别指向该结点的左孩子和右 孩子。结点的结构为： lchild data rchild 2.结点的类型说明 typedef char DataType:/*用户可根据具体应用定义DataType的实际类型*/ typedef struct node DataType data: Struct node*lchild,rchild;/*左右孩子指针*/ }BinTNode::/*结点类型*/ typedef BinTNode *BinTree;/BinTree为指向BinTNode类型结点的指针类型*/ 3.二叉链表（二叉树的常用链式存储结构) 在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点（即根结 点)的BinTree型头指针（即根指针）root,就构成了二叉树的链式存储结构，并将其称为二 又链表
3 【例】上图中单支树的顺序存储结构如下图 （2） 优点和缺点 ① 对完全二叉树而言，顺序存储结构既简单又节省存储空间。 ② 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。 【例】最坏的情况下，一个深度为 k 且只有 k 个结点的右单支树需要 2k-1 个结点的存 储空间。 ③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。 4．二叉树的顺序存储结构类型定义 【参见教材】 （二）链式存储结构 1．结点的结构 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储 结点本身的数据外，还应设置两个指针域 lchild 和 rchild，分别指向该结点的左孩子和右 孩子。结点的结构为： 2．结点的类型说明 typedef char DataType； /*用户可根据具体应用定义 DataType 的实际类型*/ typedef struct node{ DataType data； Struct node *lchild，*rchild； /*左右孩子指针*/ }BinTNode； /*结点类型*/ typedef BinTNode *BinTree；/*BinTree 为指向 BinTNode 类型结点的指针类型*/ 3．二叉链表（二叉树的常用链式存储结构） 在一棵二叉树中，所有类型为 BinTNode 的结点，再加上一个指向开始结点(即根结 点)的 BinTree 型头指针(即根指针)root，就构成了二叉树的链式存储结构，并将其称为二 叉链表
(示例参见教材) 注意： ①一个二叉链表由根指针root惟一确定。若二叉树为空，则root=NULL:若结点的某 个孩子不存在，则相应的指针为空。 ②具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点 的左、右孩子，其余的n+1个指针域为空。 4.带双亲指针的二叉链表 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指 针parent,形成一个带双亲指针的二叉链表。 注意： 二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。 五、二叉树的遍历 D (一)中序序列 中序遍历二叉树时，对结点的访问次序为中序序列 【例】中序遍历上图所示的二叉树时，得到的中序序列为： DBAE C F (二)先序序列 先序遍历二叉树时，对结点的访问次序为先序序列 【例】先序遍历上图所示的二叉树时，得到的先序序列为： A BDC E F (三)后序序列 后序遍历二叉树时，对结点的访问次序为后序序列 【例】后序遍历上图所示的二叉树时，得到的后序序列为： DBE F CA 注意： (1)在搜索路线中，若访问结点均是第一次经过结点时进行的，则是先序遍历：若访 问结点均是在第二次（或第三次）经过结点时进行的，则是中序遍历（或后序遍历）。只要将搜 索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的先 序序列、中序序列和后序序列
4 （示例参见教材） 注意： ① 一个二叉链表由根指针 root 惟一确定。若二叉树为空，则 root=NULL；若结点的某 个孩子不存在，则相应的指针为空。 ② 具有 n 个结点的二叉链表中，共有 2n 个指针域。其中只有 n-1 个用来指示结点 的左、右孩子，其余的 n+1 个指针域为空。 4．带双亲指针的二叉链表 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指 针 parent，形成一个带双亲指针的二叉链表。 注意： 二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。 五、二叉树的遍历 （一） 中序序列 中序遍历二叉树时，对结点的访问次序为中序序列 【例】中序遍历上图所示的二叉树时，得到的中序序列为： D B A E C F （二） 先序序列 先序遍历二叉树时，对结点的访问次序为先序序列 【例】先序遍历上图所示的二叉树时，得到的先序序列为： A B D C E F （三） 后序序列 后序遍历二叉树时，对结点的访问次序为后序序列 【例】后序遍历上图所示的二叉树时，得到的后序序列为： D B E F C A 注意： （1） 在搜索路线中，若访问结点均是第一次经过结点时进行的，则是先序遍历；若访 问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜 索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的先 序序列、中序序列和后序序列。 A C E F D B
(2)上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点 都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋（即双亲）结点和后继 (即孩子)结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序 名称。 六、哈夫曼树 用哈夫曼算法构造哈夫曼树的要注意以下问题。 ①初始森林中的棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子 ②n个叶子的哈夫曼树要经过n-1次合并，产生-1个新结点。最终求得的哈夫曼 树中共有2n-1个结点。 ③哈夫曼树是严格的二叉树，没有度数为1的分支结点。 下面对教材中的哈夫曼编码加以补充，以帮助同学们理解。 （一)编码方案 1.编码和解码 数据压缩过程称为编码。即将文件中的每个字符均转换为一个惟一的二进制位串。 数据解压过程称为解码。即将二进制位串转换为对应的字符。 2.等长编码方案和变长编码方案 给定的字符集C,可能存在多种编码方案。 (1)等长编码方案 等长编码方案将给定字符集C中每个字符的码长定为[1gC门，|C表示字符集的大 小。 【例】设待压缩的数据文件共有100000个字符，这些字符均取自字符集C={a,b,c, d,e,f},等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为 300000位。 (2)变长编码方案 变长编码方案将频度高的字符编码设置短，将频度低的字符编码设置较长。 【例】设待压缩的数据文件共有100000个字符，这些字符均取自字符集C={a,b,c, d,e,f},其中每个字符在文件中出现的次数（简称频度）见表。 字符编码问题 字 符 a b e f 频 度 ( 单 位 千 次) 45 13 12 16 9 5 定 长 编 码 000 001 010 011 100 101 变 长 编 码 0 101 100 111 1101 1100 根据计算公式： (45*1+13*3+12*3+16*3+9*4+584)*1000=224000
5 （2） 上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点 都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继 (即孩子)结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序 名称。 六、哈夫曼树 用哈夫曼算法构造哈夫曼树的要注意以下问题。 ① 初始森林中的 n 棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子 ② n 个叶子的哈夫曼树要经过 n-1 次合并，产生 n-1 个新结点。最终求得的哈夫曼 树中共有 2n-1 个结点。 ③ 哈夫曼树是严格的二叉树，没有度数为 1 的分支结点。 下面对教材中的哈夫曼编码加以补充，以帮助同学们理解。 （一）编码方案 1.编码和解码 数据压缩过程称为编码。即将文件中的每个字符均转换为一个惟一的二进制位串。 数据解压过程称为解码。即将二进制位串转换为对应的字符。 2．等长编码方案和变长编码方案 给定的字符集 C，可能存在多种编码方案。 （1） 等长编码方案 等长编码方案将给定字符集 C 中每个字符的码长定为[lg|C|]，|C|表示字符集的大 小。 【例】设待压缩的数据文件共有 100000 个字符，这些字符均取自字符集 C={a，b，c， d，e，f}，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为 300000 位。 （2）变长编码方案 变长编码方案将频度高的字符编码设置短，将频度低的字符编码设置较长。 【例】设待压缩的数据文件共有 100000 个字符，这些字符均取自字符集 C={a，b，c， d，e，f}，其中每个字符在文件中出现的次数(简称频度)见表。 字符编码问题 ----------------------------------------------------------------- 字 符 a b c d e f 频度（单位：千 次） 45 13 12 16 9 5 定长编 码 000 001 010 011 100 101 变长编 码 0 101 100 111 1101 1100 ----------------------------------------------------------------- 根据计算公式： (45*1+13*3+12*3+16*3+9*4+584)*1000=224000
整个文件被编码为224000位，比定长编码方式节约了约25%的存储空间。 注意： 变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他 字符的编码开始部分（称为前缀）相同。 【例】设E、T、W分别编码为00、01、0001，则解码时无法确定信息串0001是ET还 是W。 3 前 缀 码 方 案 对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀， 这种编码称为前缀（编）码。 注意： 等长编码是前缀码 4.最优前缀码 平均码长或文件总长最小的前缀编码称为最优的前缀码。最优的前缀码对文件的压缩 效果亦最佳。 2 平均码长=∑： l 其中： p:为第i个字符得概率， 1:为码长 【例】若将表6.5所示的文件作为统计的样本，则a至f六个字符的概率分别为0.45， 0.13,0.12,0.16,0.09,0.05,对变长编码求得的平均码长为2.24，优于定长编码（平均 码长为3)。 (二)根据哈夫曼树构造哈夫曼编码 利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码 正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20%至 90%,其压缩效率取决于被压缩文件的特征。 1.具体做法 (1)用字符c:作为叶子，p:或f:做为叶子c:的权，构造一棵哈夫曼树，并将树中左分 支和右分支分别标记为0和1： (2)将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即 为最优前缀码（也称哈夫曼编码）。 2.哈夫曼编码为最优前缀码 由哈夫曼树求得编码为最优前缀码的原因： ①每个叶子字符c:的码长恰为从根到该叶子的路径长度1：，平均码长（或文件总长）又 是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树，因此编码的平均码长（或 文件总长)亦最小。 ②树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编 码的前缀。即上述编码是二进制的前缀码。 3,求哈夫曼编码的算法 (1)思想方法 给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子 6
6 整个文件被编码为 224000 位，比定长编码方式节约了约 25％的存储空间。 注意： 变长编码可能使解码产生二义性。产生该问题的原因是某些字符的编码可能与其他 字符的编码开始部分(称为前缀)相同。 【例】设 E、T、W 分别编码为 00、01、0001，则解码时无法确定信息串 0001 是 ET 还 是 W。 3 ． 前 缀 码 方 案 对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀， 这种编码称为前缀(编)码。 注意： 等长编码是前缀码 4．最优前缀码 平均码长或文件总长最小的前缀编码称为最优的前缀码。最优的前缀码对文件的压缩 效果亦最佳。 其中： pi 为第 i 个字符得概率， li 为码长 【例】若将表 6.5 所示的文件作为统计的样本，则 a 至 f 六个字符的概率分别为 0.45， 0.13，0.12，0.16，0.09，0.05，对变长编码求得的平均码长为 2.24，优于定长编码(平均 码长为 3)。 （二）根据哈夫曼树构造哈夫曼编码 利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码 正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉 20％至 90％，其压缩效率取决于被压缩文件的特征。 1.具体做法 （1）用字符 ci 作为叶子，pi 或 fi 做为叶子 ci 的权，构造一棵哈夫曼树，并将树中左分 支和右分支分别标记为 0 和 1； （2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即 为最优前缀码（也称哈夫曼编码）。 2．哈夫曼编码为最优前缀码 由哈夫曼树求得编码为最优前缀码的原因： ① 每个叶子字符 ci 的码长恰为从根到该叶子的路径长度 li，平均码长(或文件总长)又 是二叉树的带权路径长度 WPL。而哈夫曼树是 WPL 最小的二叉树，因此编码的平均码长(或 文件总长)亦最小。 ② 树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编 码的前缀。即上述编码是二进制的前缀码。 3． 求哈夫曼编码的算法 （1）思想方法 给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子
T[i](0≤i≤n-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支 则生成代码1。 注意： ①由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时 向量中，并设一个指针start指示编码在该向量中的起始位置(start初始时指示向量的结 束位置)。 ②当某字符编码完成时，从临时向量的start处将编码复制到该字符相应的位串bits 中即可。 ③因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符'\0'，bits 的大小应为n+1。 (2)字符集编码的存储结构及其算法描述 typedef struct char ch:/*存储字符*/ char bits[n+1]:/*存放编码位串*/ }CodeNode: typedef CodeNode HuffmanCode[n]; void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H) {/*根据哈夫曼树T求哈夫曼编码表*/ int c,p,i; /C和p分别指示T中孩子和双亲的位置*/ char cd[n+1]: /*临时存放编码*/ int start; /*指示编码在cd中的起始位置*/ cd[n]='\0': /*编码结束符*/ for(i=0,in,i+){/*依次求叶子T[i]的编码*/ H[i].ch=getchar():/*读入叶子T[i]对应的字符*/ start=n: /*编码起始位置的初值*/ c=i: /*从叶子T[门开始上溯*/ while(p=T[c].parent).>=O){/*直至上溯到T[c]是树根为止 /*若T[c]是T[p]的左孩子，则生成代码O:否则生成 代码1 cd[--start]=(T[p).1child==C)?'0':'1';* c=p; /*继续上溯*/ } strcpy([i].bits,&cd[start]);/*复制编码位串*/ }/*endfor*/ }/*CharSetHuffmanEncoding*/ 七、练习题 单项选择题 1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为 ()。 A.15 B.16 C.17 D.47 2.在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法()。 A.正确 B.不正确 >
7 T[i](0≤i≤n-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码 0，走右分支 则生成代码 1。 注意： ① 由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时 向量中，并设一个指针 start 指示编码在该向量中的起始位置（start 初始时指示向量的结 束位置）。 ② 当某字符编码完成时，从临时向量的 start 处将编码复制到该字符相应的位串 bits 中即可。 ③ 因为字符集大小为 n，故变长编码的长度不会超过 n，加上一个结束符'\0'，bits 的大小应为 n+1。 （2）字符集编码的存储结构及其算法描述 typedef struct { char ch； /*存储字符*/ char bits[n+1]； /*存放编码位串*/ }CodeNode； typedef CodeNode HuffmanCode[n]； void CharSetHuffmanEncoding(HuffmanTree T，HuffmanCode H) {/*根据哈夫曼树 T 求哈夫曼编码表 H*/ int c，p，i; /*c 和 p 分别指示 T 中孩子和双亲的位置*/ char cd[n+1]； /*临时存放编码*/ int start； /*指示编码在 cd 中的起始位置*/ cd[n]='\0'； /*编码结束符*/ for(i=0，i=0){/*直至上溯到 T[c]是树根为止 /*若 T[c]是 T[p]的左孩子，则生成代码 0；否则生成 代码 1 cd[--start]=(T[p).1child==C)?'0'：'1'；*/ c=p； /*继续上溯*/ } strcpy(H[i].bits，&cd[start])； /*复制编码位串*/ }/*endfor*/ }/*CharSetHuffmanEncoding*/ 七、练习题 单项选择题 1.假定一棵二叉树中，双分支结点数为 15，单分支结点数为 30，则叶子结点数为 （ ）。 A．15 B．16 C．17 D．47 2．在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法（ ）。 A．正确 B．不正确
C.无法判断 D.以上均不对 3.二叉树第k层上最多有()个结点。 A.2k B.2- C.2-1 D.2k 4.二叉树的深度为k,则二叉树最多有()个结点。 A.2k B.2k-1 C.2* D.2-1 5.设某一二叉树先序遍历为abdec,中序遍历为dbeac,.则该二叉树后序遍历的顺序是 ( )。 A.abdec B.debac C.debca D.abedc 6.设某一二叉树中序遍历为badce,后序遍历为bdeca,则该二叉树先序遍历的顺序是 ()。 A.adbec B.decab C.debac D.abcde 7.树最适合于用来表示()。 A.线性结构的数据 B.顺序结构的数据 C.元素之间无前驱和后继关系的数据 D.元素之间有包含和层次关系的数据 8.一棵非空的二叉树，先序遍历与后续遍历正好相反，则该二叉树满足()。 A.无左孩子 B.无右孩子 C.只有一个叶子结点 D.任意二叉树 9.设a,b为一棵二叉树的两个结点，在后续遍历中，a在b前的条件是()。 A.a在b上方 B.a在b下方 C.a在b左方 D.a在b右方 10.权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是()。 A.18 B.28 C.19 D.29 11.将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行 编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为()。 A.33 B.34 C.35 D.36 12.如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则 该树称为()。 A.哈夫曼树 B.平衡二叉树 C.二叉树 D.完全二叉树
8 C．无法判断 D．以上均不对 3．二叉树第 k 层上最多有（ ）个结点。 A．2k B．2 k-1 C．2 k -1 D．2k-1 4．二叉树的深度为 k,则二叉树最多有（ ）个结点。 A．2k B．2k-1 C．2 k-1 D．2 k -1 5. 设某一二叉树先序遍历为 abdec，中序遍历为 dbeac，则该二叉树后序遍历的顺序是 （ ）。 A．abdec B．debac C．debca D．abedc 6．设某一二叉树中序遍历为 badce，后序遍历为 bdeca，则该二叉树先序遍历的顺序是 （ ）。 A．adbec B．decab C．debac D．abcde 7．树最适合于用来表示（ ）。 A．线性结构的数据 B．顺序结构的数据 C．元素之间无前驱和后继关系的数据 D．元素之间有包含和层次关系的数据 8．一棵非空的二叉树，先序遍历与后续遍历正好相反，则该二叉树满足（ ）。 A．无左孩子 B．无右孩子 C．只有一个叶子结点 D．任意二叉树 9．设 a,b 为一棵二叉树的两个结点，在后续遍历中，a 在 b 前的条件是（ ）。 A．a 在 b 上方 B．a 在 b 下方 C．a 在 b 左方 D．a 在 b 右方 10．权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（ ）。 A．18 B．28 C．19 D．29 11．将含有 150 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行 编号，根结点的编号为 1，则编号为 69 的结点的双亲结点的编号为（ ）。 A．33 B．34 C．35 D．36 12．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则 该树称为（ ）。 A．哈夫曼树 B．平衡二叉树 C．二叉树 D．完全二叉树
13.下列有关二叉树的说法正确的是()。 A.二叉树中度为0的结点的个数等于度为2的结点的个数加1 B.二叉树中结点个数必大于0 C.完全二叉树中，任何一个结点的度，或者为0或者为2 D.二叉树的度是2 14.二叉树是非线性数据结构，所以()。 A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 15.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 练习题答案 单项选择题 1.B2.A3.B4.D5.C6.D7.D8.C9.C10.D 11.B12.A13.A14.C15.A
9 13．下列有关二叉树的说法正确的是（ ）。 A．二叉树中度为 0 的结点的个数等于度为 2 的结点的个数加 1 B．二叉树中结点个数必大于 0 C．完全二叉树中，任何一个结点的度，或者为 0 或者为 2 D．二叉树的度是 2 14．二叉树是非线性数据结构，所以（ ）。 A．它不能用顺序存储结构存储 B．它不能用链式存储结构存储 C．顺序存储结构和链式存储结构都能存储 D．顺序存储结构和链式存储结构都不能使用 15．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对 练习题答案 单项选择题 1．B 2．A 3．B 4．D 5．C 6．D 7．D 8．C 9．C 10．D 11．B 12．A 13．A 14．C 15．A