数据结构习题课4ppt课件.ppt

数据结构习题第4章 吉林大学计算机科学与技术学院谷方明 1 第4章作业 4 2 4 3 4 5 4 6 4 7 4 8 4 10 4 12 4 13 2 作业4 2 题目描述由三个结点A B和C可以构成多少棵不同的树 可以构成多少棵不同的二叉树 3 树有2种形态 6 3 9种二叉树有5种形态 6 5 30种 4 作业4 3 判断以下命题是否为真 若真 请证明之 否则 举出反例 一棵二叉树形的所有的叶结点 在先根次序 中根次序和后根次序下的排列都按相同的相对位置出现 5 先根 ABCEIFJDGHKL中根 EICFJBGDKHLA后根 IEJFCGKLHDBA 6 数学归纳法 令n等于二叉树的高度 n 0时命题成立假设n k时命题成立 往证n k 1时命题也成立 当n k 1时 对任意两个叶结点l1 l2 有三种情况l1 l2都在根的左子树中 l1 l2都在根的右子树当中 l1 l2不在根的同一个子树当中 7 作业4 5 编写一算法 判别给定二叉树是否为完全二叉树 8 分析 完全二叉树的叶子结点只能在层数最大两层出现 并且连续出现在层次遍历二叉树时 增加一个标志B B 1表示所有已扫描过的结点均有左 右孩子 B 0 表示遇到无左或右孩子的结点 此后的所有结点均应为叶结点 层次遍历时 空指针可以入队 出队遇到第一个空指针时 此后队列里的都是空指针 对所有结点按完全二叉树编号 记录编号的最大值和结点数n 相等 则是完全二叉树 设有一个指针数组 下标代表编号 数组元素代表结点 出现空缺编号或编号大于n 则不是完全二叉树 建立编号函数 递归记录结点数和编号最大值 9 参考算法如下 为此 在层次遍历二叉树时 增加一个标志B B 1表示所有已扫描过的结点均有左 右孩子 B 0 表示遇到无左或右孩子的结点 此后的所有结点均应为叶结点 时间复杂性为T n 2n或O n 10 boolcompletetree BintreeNode t BoolB 1 QueueQ if t NULL Q Insert t while Q QueueEmpty 11 while Q QueueEmpty 处理剩余叶节点 p Q Delete if p left NULL p right NULL returnfalse returntrue 12 4 6 编写算法求任意二叉树中一条最长的路径 并输出此路径上各结点的值 13 分析 教材中 树上的路径定义 若树T中存在结点序列Vm Vm 1 Vm k 1 k T的最大层数 Vi 1是Vi的子结点 相当于求根结点开始的最长路径 可以根据左右子树的高度确定下一步的结点 14 参考答案 intheight BinTreeNode t if t NULL return 1 return1 max height t left height t right voidpath BinTreeNode t while t coutdataleft height t right t t left elset t right 15 时间复杂度为O n2 或O n h 原因在于高度的重复计算 在每个结点中引入高度域 可以将时间复杂度为降为O n 树上的路径也有另一种理解 即图论的理解 这时 最长路不一定是从根结点出发的 需要先确定路径最长的结点 然后按前面的方法处理 也可以按第五章的方法处理 16 TreeNode lstp NULL intmaxl 1 voidLongest TreeNode t if t NULL returnNULL if height t left height t right 2 maxl maxl height t left height t right 2 maxl lstp t Longest t left Longest t right 17 其它方法 课后提示 非递归后根遍历 当i 2是 判断是否为叶子节点 若是就与当前记录的最长路径比较 大于就更新最大路径值及最大路径 回溯法 引入一个数组记录路径上的结点 递归出口是叶子结点 非叶子结点继续尝试和修改 18 4 7 编写算法判断两棵二叉树T和T 是否相似 两棵二叉树相似是指它们具有相同结构 19 参考答案 算法Like t1 t2 判断两棵二叉树是否相似 t1 t2表示两棵树的根节点 若相似 返回值为true 否则为false L1 递归出口 IFt1 NULLANDt2 NULLTHENRETURNtrue IFt1 NULLORt2 NULLTHENRETURNfalse L2 递归调用 RETURNLike left t1 left t2 ANDLike right t1 right t2 时间复杂度为O n1 n2 20 4 8 对于下图所示的树 a 对其进行先根和后根遍历 b 给出其在自然对应下的二叉树 21 参考答案 a 对其进行先根和后根遍历 先根遍历 ABEKGJFCGDHI后根遍历 KGJEFBGCHIDA b 给出其在自然对应下的二叉树 22 作业4 10 对以左儿子 右兄弟链接表示的树 编写计算树的深度的算法 23 分析 解题思路1 对树做层次遍历 每遍历一层树的深度 1 关键 将队列中的结点结构变为 结点 该结点的层数i 24 算法Depth t d 解题思路1 对树做层次遍历 每遍历一层树的深度 1 D1 判断t是否为NULL IFt NULLTHEN d 1 RETURN D2 创建辅助队列 根结点入队 CREATE Q Q t 0 D3 利用队列Q遍历第d层结点 WHILENOT IsEmpty Q DO p d Q WHILEp NULLDO IFFirstChild p NULLTHENQ FirstChild p d 1 p NextBrother p 25 分析 解题思路2 树的深度dept t max t的各子树的深度 1 26 算法Depth t d 解题思路2 树的深度dept t max t的各子树的深度 1D1 递归出口 IFt NULLTHEN d 1 RETURN IF GFC t NULL THEN d 0 RETURN D2 递归调用 p GFC t Max 1 Max存储各子树的最大深度WHILE p NULL Depth p dp IF dp Max THENMax dp p GNB p d Max 1 RETURN 27 分析 解题思路3 基于对应的二叉树直接求树的深度 dept t max 左子树的深度 1 右子树的深度 28 算法Depth t d 解题思路3 基于对应的二叉树直接求树的深度D1 递归出口 IFt NULLTHEN d 1 RETURN D2 递归调用 Depth GFC t d1 Depth GNB t d2 d Max d1 1 d2 29 作业4 12 题目描述构造权值为 5 13 21 7 18 30 41 的哈夫曼树 30 首先 在森林中取权值最小的两个根结点s和n 合成一棵二叉树 新生成的结点T1 作为这两个结点的父结点 T1的权值是两个子结点的权值之和 对新的森林重复上一步操作 直至森林中只有唯一的根结点时 终止操作 31 5 13 21 7 18 30 41 25 80 55 135 12 39 5 7 13 30 18 21 41 32 4 13 编写算法计算二叉树中边的个数 33 分析 边数 结点数 1 各种遍历计算结点数直接计算边数 时间复杂度都是O n 34 算法E t n 计算二叉树t的边数 结果放在n中 L1 递归出口 n 0 IFt NULLTHENRETURN L2 递归调用 IF left t NULL THEN E left t n1 n n 1