第六章习题解答

第六章习题解答第六章习题解答 1 P38 6 5 已知一棵度为已知一棵度为m的树中有的树中有n1个度为个度为1的结点 的结点 n2个度为个度为2的结点 的结点 nm个度为个度为m的结的结 点 问该树中有多少片叶子 点 问该树中有多少片叶子 解 设树的总结点个数为解 设树的总结点个数为 n 叶子结点的个数为叶子结点的个数为 n0 则则 n n0 n1 n2 nm 1 又因为树的总分支数为又因为树的总分支数为 n 1 且且 n 1 n1 n2 2 n3 3 nm m 2 1 2 得得 1 n0 n2 2 n3 m 1 nm 即 即 n0 1 n2 2n3 m 1 nm 1 i 1 ni 2 P43 6 44 编写递归算法 求二叉树中以元素值为编写递归算法 求二叉树中以元素值为x的结点为根的子树的深度 的结点为根的子树的深度 二叉树的二叉链表存储结构定义如下 二叉树的二叉链表存储结构定义如下 typedef struct Bitnode int data struct Bitnode lchild rchild Bitnode Bitree int Get Sub Depth Bitree T int x 求二叉树中以值为求二叉树中以值为 x 的结点为根的子树深度的结点为根的子树深度 若树中有值为若树中有值为 x 的结点 则输出深度 函数返的结点 则输出深度 函数返 回值回值 1 否则 函数返回值 否则 函数返回值 0 if T if T data x printf d n Get Depth T 找到了值为找到了值为 x 的结点的结点 求其深度求其深度 return 1 else Get Sub Depth T lchild x Get Sub Depth T rchild x 在左右子树中继续寻找在左右子树中继续寻找 else return 0 int Get Depth Bitree T 求子树深度的递归算法求子树深度的递归算法 if T return 0 else i 1 m m Get Depth T lchild n Get Depth T rchild return m n m n 1 3 试采用顺序存储方法和二叉链表的链式存储方法分别试采用顺序存储方法和二叉链表的链式存储方法分别画画出下图所示的二叉树的存储结构 出下图所示的二叉树的存储结构 4 4 分别写出 分别写出 3 3 题中二叉树的前序 中序和后序序题中二叉树的前序 中序和后序序 列 列 前序序列 前序序列 ABDEGCFH 中序序列 中序序列 DBGEACHF 后序序列 后序序列 DGEBHFCA 5 5 已知一棵树二叉树的后序遍历和中序遍历的序列分别为 已知一棵树二叉树的后序遍历和中序遍历的序列分别为 A C D B G I H F E 和和 A B C D E F G H I 请画出该二叉树 并写出它的先序遍历的序列 请画出该二叉树 并写出它的先序遍历的序列 G E B D H F C A T B G C A C G H E FD 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B C D E F G H E B F D H I C G A 先序序列为 先序序列为 EBADCFHGI 6 6 已知一棵树二叉树的先序遍历和中序遍历的序列分别为 已知一棵树二叉树的先序遍历和中序遍历的序列分别为 A B D G H C E F I 和和 G D H B A E C I F 请画出此二叉树 并写出它的后序遍的序列 请画出此二叉树 并写出它的后序遍的序列 后序序列 GHDBEIFCA 7 写出在前序线索二叉树中查找给定结点写出在前序线索二叉树中查找给定结点 p 的前序序列中的后继的算法 的前序序列中的后继的算法 解 设二叉线索链存储类型定义如下 解 设二叉线索链存储类型定义如下 typedef enum pointertag 0 1 typedef struct bithrnode Telemtype data struct bithrnode lchild rchild pointertag ltag rtag bithrnode bithrtree 分析算法思想 分析算法思想 若若 p 的左子树为非空 则的左子树为非空 则 p lchild 为为 p 的前序后继 否则的前序后继 否则 p rchild 为为 p 的前序后继 的前序后继 算法如下 算法如下 bithrtree preordernext bithrtree p if p ltag 0 return p lchild else return p rchild 8 8 写出在后序线索二叉树中查找给定结点 写出在后序线索二叉树中查找给定结点 p 的后序序列中的前趋的算法 的后序序列中的前趋的算法 解 分析算法思想 解 分析算法思想 若若 p 的右子树为非空 则的右子树为非空 则 p rchild 为为 p 的后序序列中的前趋 否则的后序序列中的前趋 否则 p lchild 为为 p 的后序序列中的前趋 的后序序列中的前趋 bithrtree posorderpre bithrtree p if p rtag 0 p 的右子树非空的右子树非空 return p rchild else return p lchild 9 写出在中序线索二叉树中查找给定结点写出在中序线索二叉树中查找给定结点 p 的中序序列中的前趋的算法 的中序序列中的前趋的算法 解 分析算法思想 解 分析算法思想 1 若 若 p 的左子树为空 则的左子树为空 则 p lchild 为左线索 直接指向为左线索 直接指向 p 的中序序列中的中序序列中 的前趋 的前趋 A B I C G DFE H 2 若 若 p 的左子树非空 则的左子树非空 则 p 的中序序列中的前趋必是其左子树中最后遍历到的结点 也就是的中序序列中的前趋必是其左子树中最后遍历到的结点 也就是 p 的左子树中最右下的结点 的左子树中最右下的结点 算法如下 算法如下 bithrtree inorderpre bithrtree p if p ltag 1 p 的左子树为空的左子树为空 return p lchild else p 的左子树非空的左子树非空 for q p lchild q rtag 0 q q rchild 查找查找 p 的左子树的最右下结点的左子树的最右下结点 return q 10 将如下图的森林转换为二叉树将如下图的森林转换为二叉树 11 写出写出 1010 题中森林的先序和中序遍历序列题中森林的先序和中序遍历序列 先序序列 先序序列 ABCDEFGHIJKLNM 后序序列 后序序列 BCEDAHIJGFNLMK 12 假设用于通讯的电文仅由假设用于