数据结构章节练习题及答案5

1、第5章树和二叉树.请简述树、二叉树、满二叉树和完全二叉树的结构特性。树：只有最顶层的结点没有前驱,其余结点都有且只有一个前驱; 一个结点可以没有后继，也可以有一个或多个后继。二叉树：一种特殊形态的树，每个结点至多有两个后继。满二叉树：一种特殊形态的二叉树，除了最后一层的结点为叶子 结点外其它结点都有左、右两棵子树的二叉树。完全二叉树：一种特殊形态的二叉树，其结点与相同深度的满二 叉树中的结点编号完全一致，即对于深度为k的完全二叉树，其前 k-i层与深度为k的满二叉树的前k-i层完全一样，只是在第k层上 有可能缺少右边假设干个结点。.请解释结点的度、树的度、结点的层、树的深度、分支、路 径、路径

2、长度、树的路径长度、叶子结点、分支结点、内部结点、孩 子、双亲、兄弟、堂兄弟、祖先、子孙、有序树、无序树和森林等基 本术语的含义。结点的度和树的度：一个结点的后继的数目称为该结点的度，树 中各结点度的最大值称为树的度。结点的层和树的深度：树的根结点所在的层为第1层，其余结点 的层等于其前驱结点的层加1,树中各结点的层的最大值称为树的深 度。分支、路径、路径长度和树的路径长度：从一个结点到其后继结 点之间的连线称为一个分支，从一个结点X到另一个结点Y所经历的所有分支构成结点X到结点Y的路径，一条路径上的分支数目称 为路径长度，从树的根结点到其他各个结点的路径长度之和称为树的 路径长度。叶子结点、

3、分支结点和内部结点：树中度为0的结点称为叶子结 点（或终端结点），度不为0的结点称为分支结点（或非终端结点）， 除根结点以外的分支结点也称为内部结点。孩子和双亲：在树中，一个结点的后继结点称为该结点的孩子， 相应地，一个结点的前驱结点称为该结点的双亲，即一个结点是其孩 子结点的双亲、其双亲结点的孩子。兄弟和堂兄弟：同一双亲的孩子结点之间互称为兄弟，不同双亲 但在同一层的结点之间互称为堂兄弟。祖先和子孙：从树的根结点到某一个结点X的路径上经历的所 有结点（包括根结点但不包括结点X）称为结点X的祖先，以某一 结点X为根的子树上的所有非根结点（即除结点X外）称为结点X 的子孙。有序树和无序树：对于树

4、中的任一结点，如果其各棵子树的相对 次序被用来表示数据之间的关系，即交换子树位置会改变树所表示的 内容，那么称该树为有序树；否那么称为无序树。森林：m （m0）棵互不相交的树的集合就构成了森林。.请简述二叉树的五条基本性质。性质1：在二叉树的第i层上至多有2M个结点（i之1）。性质2：深度为k的二叉树至多有2k-l个结点。性质3：在二叉树中，假设度为0的结点（即叶子结点）数为no, 度为2的结点数为ii2,那么n0=n2+lo性质4：具有n个结点的完全二叉树其深度为Uog2n+1 （其中 I_log2n表示不大于log2n的最大整数）。性质5：采用顺序编号的完全二叉树具有如下性质：假设一个分支

5、 结点的编号为i,那么其左子树的根结点（即左孩子结点）编号为2*i, 右子树的根结点（即右孩子结点）编号为2*i+l；反之，假设一个非根 结点的编号为i,那么其双亲结点的编号为Li/2（其中Li/2j表示不大于 i/2的最大整数）。.请简述二叉树的常用操作及各操作的含义。创立一棵空二叉树：创立一棵没有任何结点的二叉树。在顺序表 示中，根据树的深度为结点分配内存；在二叉链表表示中，将指向根 结点的指针赋值为NULLo删除一棵二叉树：将二叉树各结点所占据的内存释放。清空二叉树：将二叉树的所有结点删除，使之成为一棵空二叉树。以指定元素值创立根结点：创立根结点，并以指定值作为根结点 的元素值。将一个结

6、点作为指定结点的左孩子插入：根据指定元素值生成一 个新结点，并将其作为指定结点的左孩子。将一个结点作为指定结点的右孩子插入：根据指定元素值生成一 个新结点，并将其作为指定结点的右孩子。先序遍历二叉树：也称为先根遍历，其访问方式递归定义如下： 对于一棵二叉树，先访问其根结点，再访问根结点的左、右子树；对 于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结 点，再访问根结点的左、右子树。中序遍历二叉树：也称为中根遍历，其访问方式递归定义如下： 对于一棵二叉树，先访问根结点左子树，再访问根结点，最后访问右 子树；对于左、右子树中的结点仍然是按照中序遍历方式访问。后序遍历二叉树：也称为后根遍

7、历，其访问方式递归定义如下： 对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问 根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。逐层遍历二叉树：从第1层开始依次对每层中的结点按照从左至 右的顺序进行访问。获取指定结点的双亲结点：根据指定结点获取其双亲结点。在顺 序表示中，可以直接根据指定结点的位置计算双亲结点的位置；在二 叉链表表示中，那么需要从根结点开始遍历二叉树直至找到指定结点的 双亲结点。删除以指定结点为根的子树：将以指定结点为根结点的子树上的 所有结点（包括指定结点）删除。按关键字查找结点：按照某种规那么（先序、中序、后序或逐层） 依次访问二叉树中的每一结点，直至

8、找到与关键字匹配的结点。判断二叉树是否为空：判断一棵二叉树是否为空二叉树。修改指定结点的元素值：将指定结点的元素值修改为指定值。计算二叉树的深度：按照某种规那么依次访问二叉树中的每一结点, 计算各结点所在层的最大值。计算二叉树的叶子结点数：按照某种规那么依次访问二叉树中的每 一结点，计算度为。的结点数。.请简述顺序表示的二叉树中各结点的编号规那么。顺序表示的二叉树中各结点的编号与相同深度的完全二叉树中对应结点的编号相同。.请简述二叉链表表示和三叉链表表示的二叉树中结点的结 构。在二叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点不包含指向其双亲结点的指针；在三叉链表表示中，双亲结点有指

9、向其孩子结点的指针，而孩子结点也包含指向其双亲结点的指针。7.请简述二叉树的U!种遍历方式及每一种遍历方式中结点的访问顺序。7.请简述二叉树的U!种遍历方式及每一种遍历方式中结点的访先序遍历二叉树：也称为先根遍历，其访问方式递归定义如下： 对于一棵二叉树，先访问其根结点，再访问根结点的左、右子树；对 于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结 点，再访问根结点的左、右子树。中序遍历二叉树：也称为中根遍历，其访问方式递归定义如下： 对于一棵二叉树，先访问根结点左子树，再访问根结点，最后访问右 子树；对于左、右子树中的结点仍然是按照中序遍历方式访问。后序遍历二叉树：也称为后根遍历

10、，其访问方式递归定义如下： 对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问 根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。逐层遍历二叉树：从第1层开始依次对每层中的结点按照从左至 右的顺序进行访问。.一棵二叉树的先序遍历结果为A、B、D、G、C、E、F、 H、I,中序遍历结果为D、G、B、A、Ev C、H、F、I,请给出该 二叉树的后序遍历结果。G、D、B、E、H、I、F、C、A.一棵二叉树的中序遍历结果为D、G、B、Av Ex Cv H、 Fv I,后序遍历结果为G、Dx B、Ev H、I、F、C、A,请给出该 二叉树的先序遍历结果。A、B、D、G、C、Ex F、H

11、、I.一棵二叉树的先序遍历结果为A、B、D、G、C、E、F、 H、I,后序遍历结果为G、D、B、E、H、I、F、C、A,请给出该 二叉树的中序遍历结果。D、G、B、A、E、C、H、F、I.请简述哈夫曼树的结构特性。哈夫曼树，又称最优二叉树，是指在由个叶子结点构成的一类 二叉树中具有最短带权路径长度的二叉树。.请简述结点的权、结点的带权路径长度、树的带权路径长度 等基本术语的含义。结点的权和结点的带权路径长度：在实际应用中，往往给树中的 结点赋予一个具有某种意义的实数，该实数就称为是结点的权。结点 的带权路径长度是指从树根到该结点的路径长度与结点的权的乘积。树的带权路径长度：是指树中所有叶子结点

12、的带权路径长度之 和，记为(其中，为叶子结点的数目，也为第，个叶 子结点的权，乙为根结点到第，个叶子结点的路径长度，可知卬心为 第，个叶子结点的带权路径长度)。.请简述哈夫曼树的构造方法。哈夫曼树的构造方法如下：(a)个权值为阴(，=1, 2,的结点，将每个结点作 为根结点生成棵只有根结点的二叉树形成森林代Ti,乃，,Tn o(b)从森林尸中选出根结点权值最小的两棵二叉树。和Tq,并 通过添加新的根结点将它们合并为一棵新二叉树，新二叉树中和 分别作为根结点的左子树和右子树，且根结点的权值等于。和Tq 两棵二叉树的根结点权值之和。以合并后生成的新二叉树替代森林F 中的原有二叉树。和Tqo重复该步

13、骤直至森林F中只存在一棵二叉 树。.请简述哈夫曼码的作用及其编码方法。哈夫曼编码是指将用其他编码法表示的字符序列转成用哈夫曼码表示以减少存储空间，其具体方法为：(a)以要编码的字符集C=a, C2,c“作为叶子结点、字符出现的频度或次数W=Wl, W2,皿作为结点的权，构造哈夫曼树。(b)规定哈夫曼树中，从根结点开始，双亲结点到左孩子结点 的分支标为0,双亲结点到右孩子结点的分支标为1。从根结点到某 一叶子结点经过的分支形成的编码即是该叶子结点所对应字符的哈 夫曼码。.请简述树的四种常用表示方式。双亲表示法：在孩子结点中设置一个指针域记录其双亲结点的存 储位置。孩子表示法：在双亲结点中设置指向孩子结点的指针域来表示一 棵树。孩子双亲表示法：综合了孩子表示法和双亲表示法的特点，既在 孩子结点中设置记录双亲结点位置的指针域，又在双亲结点中设置记 录孩子结点位置的指针域。孩子兄弟表示法：又称为二叉链表表示法，与二叉树的二叉链表 表示法存储结构完全相同，只是结点中指针域的含义有所不同(一个 指针域指向该结点的第一个孩子结点，另一个指针域指向该结点的下 一个兄弟结点)。.请简述森林转换为二叉树的具体步骤