数据结构课后习题及解析第六章

第六章习题第六章习题 1 试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态 2 对题 1 所得各种形态的二叉树 分别写出前序 中序和后序遍历的序列 3 已知一棵度为 k 的树中有 n1个度为 1 的结点 n2个度为 2 的结点 nk个度为 k 的结点 则该树中有多少个叶子结点并证明之 4 假设一棵二叉树的先序序列为 EBADCFHGIKJ 中序序列为 ABCDEFGHIJK 请画出该二叉树 5 已知二叉树有 50 个叶子结点 则该二叉树的总结点数至少应有多少个 6 给出满足下列条件的所有二叉树 前序和后序相同 中序和后序相同 前序和后序相同 7 n 个结点的 K 叉树 若用具有 k 个 child 域的等长链结点存储树的一个结点 则空的 Child 域有多少个 8 画出与下列已知序列对应的树 树的先根次序访问序列为 GFKDAIEBCHJ 树的后根次序访问序列为 DIAEKFCJHBG 9 假设用于通讯的电文仅由 8 个字母组成 字母在电文中出现的频率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 请为这 8 个字母设计哈夫曼编码 10 已知二叉树采用二叉链表存放 要求返回二叉树 T 的后序序列中的第一个结点指针 是否可不 用递归且不用栈来完成 请简述原因 11 画出和下列树对应的二叉树 12 已知二叉树按照二叉链表方式存储 编写算法 计算二叉树中叶子结点的数目 13 编写递归算法 对于二叉树中每一个元素值为 x 的结点 删去以它为根的子树 并释放相应 的空间 14 分别写函数完成 在先序线索二叉树 T 中 查找给定结点 p 在先序序列中的后继 在后序 线索二叉树 T 中 查找给定结点 p 在后序序列中的前驱 15 分别写出算法 实现在中序线索二叉树中查找给定结点 p 在中序序列中的前驱与后继 16 编写算法 对一棵以孩子 兄弟链表表示的树统计其叶子的个数 17 对以孩子 兄弟链表表示的树编写计算树的深度的算法 18 已知二叉树按照二叉链表方式存储 利用栈的基本操作写出后序遍历非递归的算法 19 设二叉树按二叉链表存放 写算法判别一棵二叉树是否是一棵正则二叉树 正则二叉树是指 在二叉树中不存在子树个数为 1 的结点 20 计算二叉树最大宽度的算法 二叉树的最大宽度是指 二叉树所有层中结点个数的最大值 21 已知二叉树按照二叉链表方式存储 利用栈的基本操作写出先序遍历非递归形式的算法 22 证明 给定一棵二叉树的前序序列与中序序列 可唯一确定这棵二叉树 给定一棵二叉树的后序序列与中序序列 可唯一确定这棵二叉树 23 二叉树按照二叉链表方式存储 编写算法 计算二叉树中叶子结点的数目 24 二叉树按照二叉链表方式存储 编写算法 将二叉树左右子树进行交换 实习题实习题 1 问题描述 建立一棵用二叉链表方式存储的二叉树 并对其进行遍历 先序 中序和后序 打印输出遍历结果 基本要求 从键盘接受输入先序序列 以二叉链表作为存储结构 建立二叉树 以先序来建立 并对其进行遍历 先序 中序 后序 然后将遍历结果打印输出 要求采用递归和非递归两种 方法实现 测试数据 ABC DE G F 其中 表示空格字符 输出结果为 先序 ABCDEGF 中序 CBEGDFA 后序 CGBFDBA 2 已知二叉树按照二叉链表方式存储 编写算法 要求实现二叉树的竖向显示 竖向显示就是 二叉树的按层显示 3 如题 1 要求建立好二叉树 按凹入表形式打印二叉树结构 如下图所示 2 按凹入表形式打印树形结构 如下图所示 第六章答案 6 1 分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态 解答 具有 3 个结点的树 具有 3 个结点的二叉树 6 3 已知一棵度为 k 的树中有 n1个度为 1 的结点 n2个度为 2 的结点 nk个度为 k 的结 点 则该树中有多少个叶子结点 解答 设树中结点总数为 n 则 n n0 n1 nk 树中分支数目为 B 则 B n1 2n2 3n3 knk 因为除根结点外 每个结点均对应一个进入它的分支 所以有 n B 1 即 n0 n1 nk n1 2n2 3n3 knk 1 由上式可得叶子结点数为 n0 n2 2n3 k 1 nk 1 6 5 已知二叉树有 50 个叶子结点 则该二叉树的总结点数至少应有多少个 解答 n0表示叶子结点数 n2表示度为 2 的结点数 则 n0 n2 1 所以 n2 n0 1 49 当二叉树中没有度为 1 的结点时 总结点数 n n0 n2 99 6 6 试分别找出满足以下条件的所有二叉树 1 前序序列与中序序列相同 2 中序序列与后序序列相同 3 前序序列与后序序列相同 解答 1 前序与中序相同 空树或缺左子树的单支树 2 中序与后序相同 空树或缺右子树的单支树 3 前序与后序相同 空树或只有根结点的二叉树 6 9 假设通讯的电文仅由 8 个字母组成 字母在电文中出现的频率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 请为这 8 个字母设计哈夫曼编码 解答 构造哈夫曼树如下 哈夫曼编码为 I1 11111 I5 1100 I2 11110 I6 10 I3 1110 I7 01 I4 1101 I8 00 6 11 画出如下图所示树对应的二叉树 解答 6 15 分别写出算法 实现在中序线索二叉树 T 中查找给定结点 p 在中序序列中的前驱与后继 在先序线索二叉树 T 中 查找给定结点 p 在先序序列中的后继 在后序线索二叉树 T 中 查找 给定结点 p 在后序序列中的前驱 1 找结点的中序前驱结点 BiTNode InPre BiTNode p 在中序线索二叉树中查找 p 的中序前驱结点 并用 pre 指针返回结果 if p Ltag 1 pre p LChild 直接利用线索 else 在 p 的左子树中查找 最右下端 结点 for q p LChild q Rtag 0 q q RChild pre q return pre 2 找结点的中序后继结点 BiTNode InSucc BiTNode p 在中序线索二叉树中查找 p 的中序后继结点 并用 succ 指针返回结果 if p Rtag 1 succ p RChild 直接利用线索 else 在 p 的右子树中查找 最左下端 结点 for q p RChild q Ltag 0 q q LChild succ q return succ 3 找结点的先序后继结点 BiTNode PreSucc BiTNode p 在先序线索二叉树中查找 p 的先序后继结点 并用 succ 指针返回结果 if p Ltag 0 succ p LChild else succ p RChild return succ 4 找结点的后序前驱结点 BiTNode SuccPre BiTNode p 在后序线索二叉树中查找 p 的后序前驱结点 并用 pre 指针返回结果 if p Ltag 1 pre p LChild else pre p RChild return pre 6 21 已知二叉树按照二叉链表方式存储 利用栈的基本操作写出先序遍历非递归形式的算法 解答 Void PreOrder BiTree root 先序遍历二叉树的非递归算法 InitStack p root while p NULL IsEmpty S if p NULL Visit p data push p p Lchild else Pop p p RChild 6 24 已知二叉树按照二叉链表方式存储 编写算法 将二叉树左右子树进行交换 解答 算法 一 Void exchange BiTree root p root if p LChild NULL p RChild NULL temp p LChild p LChild p RChild p RChild temp exchange p LChild exchange p RChild 算法 二 Void exchange BiTree root p root if p LChild NULL p RChild NULL exchange p LChild exchange p RChild temp p LChild p LChild p RChild p RChild temp 第六章 习题解析 1 试分别画出具有 试分别画出具有 3 个结点的树和个结点的树和 3 个结点的二叉树的所有不同形态 个结点的二叉树的所有不同形态 2 对题 对题 1 所得各种形态的二叉树 分别写出前序 中序和后序遍历的所得各种形态的二叉树 分别写出前序 中序和后序遍历的 序列 序列 3 已知一棵度为 已知一棵度为 k 的树中有的树中有 n1个度为个度为 1 的结点 的结点 n2个度为个度为 2 的结点 的结点 nk个度为个度为 k 的结点 则该树中有多少个叶子结点 的结点 则该树中有多少个叶子结点 提示提示 参考 参考 P 116 性质性质 3 n n0 n1 nk B n1 2n2 3n3 knk n B 1 n0 n1 nk n1 2n2 3n3 knk 1 n0 n2 2n3 k 1 nk 1 4 假设一棵二叉树的先序序列为假设一棵二叉树的先序序列为 EBADCFHGIKJ 中序序列为 中序序列为 ABCDEFGHIJK 请画出该二叉树 请画出该二叉树 提示提示 参考 参考 P 148 6 已知二叉树有已知二叉树有 50 个叶子结点 则该二叉树的总结点数至少应有多个叶子结点 则该二叉树的总结点数至少应有多 少个 少个 提示提示 方法方法 1 1 一个叶子结点 总结点数一个叶子结点 总结点数至多至多有多少个 有多少个 结论 结论 可压缩可压缩一度一度结点 结点 2 满二叉树或完全二叉树具有最少的 满二叉树或完全二叉树具有最少的一度一度结点结点 3 可能的最大满二叉树是几层 有多少叶结点 如何增补 可能的最大满二叉树是几层 有多少叶结点 如何增补 25 50data x FreeTree bt bt NULL else DelTree bt x void DelTree BiTree bt DataType x if bt if bt LChild bt LChild NULL if bt RChild bt RChild NULL DelTree bt LChild x DelTree bt RChild x 方法方法 2 1 先序查找 先序查找 2 直接查看 直接查看当前根当前根结点 结点 3 用 用指针参数指针参数 方法方法 3 1 先序查找 先序查找 2 直接查看 直接查看当前根当前根结点结点 3 通过 通过函数函数值 返回值 返回删除后结果删除后结果 参示例程序 参示例程序 14 分别写函数完成 在先序线索二叉树 分别写函数完成 在先序线索二叉树 T 中 查找给定结点中 查找给定结点 p 在先序在先序 序列中的后继 在后序线索二叉树序列中的后继 在后序线索二叉树 T 中 查找给定结点中 查找给定结点 p 在后序序列中在后序序列中 的前驱 的前驱 提示提示 1 先查看线索 无线索时用下面规律 先查看线索 无线索时用下面规律 2 结点 结点 p 在先序序列中的后继为其左子或右子 在先序序列中的后继为其左子或右子 3 结点 结点 p 在后序序列中的前驱也是其左子或右子 在后序序列中的前驱也是其左子或右子 15 分别写出算法 实现在中序线索二叉树中查找给定结点 分别写出算法 实现在中序线索二叉树中查找给定结点 p 在中序序在中序序 列中的前驱与后继 列中的前驱与后继 参例题 参例题 16 编写算法 对一棵以孩子 编写算法 对一棵以孩子 兄弟链表表示的树统计其叶子的个数 兄弟链表表示的树统计其叶子的个数 提示提示 1 可将 可将孩子孩子 兄弟链表兄弟链表划分为划分为根根 首子树首子树 兄弟树兄弟树 递归处理 递归处理 2 可利用 可利用返回值返回值 或 或全局变量全局变量 17 对以孩子 对以孩子 兄弟链表表示的树编写计算树的深度的算法 兄弟链表表示的树编写计算树的深度的算法 18 已知二叉树按照二叉链表方式存储 利用栈的基本操作写出后序遍 已知二叉树按照二叉链表方式存储 利用栈的基本操作写出后序遍 历非递归的算法 历非递归的算法 参课本 参课本 19 设二叉树按二叉链表存放 写算法判别一棵二叉树是否是一棵正则 设二叉树按二叉链表存放 写算法判别一棵二叉树是否是一棵正则 二叉树 正则二叉树是指 在二叉树中不存在子树个数为二叉树 正则二叉树是指 在二叉树中不存在子树个数为 1 的结点 的结点 提示提示 可利用任何递归 非递归遍历算法 可利用任何递归 非递归遍历算法 20 计算二叉树最大宽度的算法 二叉树的最大宽度是指 二叉树所有 计算二叉树最大宽度的算法 二叉树的最大宽度是指 二叉树所有 层中结点个数的最大值 层中结点个数的最大值 21 已知二叉树按照二叉链表方式存储 利用栈的基本操作写出先序遍 已知二叉树按照二叉链表方式存储 利用栈的基本操作写出先序遍 历非递归形式的算法 历非递归形式的算法 22 证明 给定一棵二叉树的前序序列与中序序列 可唯一确定这棵二证明 给定一棵二叉树的前序序列与中序序列 可唯一确定这棵二 叉树 叉树 给定一棵二叉树的后序序列与中序序列 可唯一确定这棵二叉树 给定一棵二叉树的后序序列与中序序列 可唯一确定这棵二叉树 23 二叉树按照二叉链表方式存储 编写算法将二叉树左右子树进行交二叉树按照二叉链表方式存储 编写算法将二叉树左右子树进行交 换 换 实习题实习题 1 问题描述问题描述 建立一棵用二叉链表方式存储的二叉树 并对其进行遍建立一棵用二叉链表方式存储的二叉树 并对其进行遍 历 先序 中序和后序