习题课二叉树.pdf

数据结构与算法 二叉树部分习题讲解 齐荣嵘 qrr0831 edx二叉树（上） Problem1 一棵有510个结点的完全二叉树的高度为多少？（独根树高度为1） 答案答案: : 根据公式 log2510 + 1 可以计算出高度为9 Problem2 在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数 为m，则有n=_ 答案答案: : m+1 Problem3-1 下列关于二叉树性质的说法正确的有： 1. 非空满二叉树的结点个数一定为奇数个。 结点度为0或2的数目相差1 2. 当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。 倒数第二层的度都为0或者2 3. 一棵非空二叉树的为空的外部结点数目等于其结点数加1。 2*n0+n1=n0+n1+n2+1 4. 非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。 5. 完全二叉树最多只有最下面的一层结点度数可以小于2。 倒数第二层 6. 满二叉树的所有结点的度均为2。 可能为0 Problem3-2 下列关于二叉树遍历的说法正确的有： 1. 只有空二叉树和一个根结点的二叉树这两种二叉树的前序和中序遍历 的顺序恰好一样。 所有结点左子树为空的二叉树也满足要求 2. 所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。 3. 所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。 4. 只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历 的顺序恰好一样。 前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能 让两者一样。 5. 所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。 6. 存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。 只有一个根结点的二叉树满足要求。 Problem4-1 已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这 棵树的后序遍历。 答案：答案：DGEBFCA Problem4-2 已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这 棵树的前序遍历。 答案：答案：ABDEGCF Problem5 请写出这棵二叉树的前序、中序、后序遍历。 答案：答案： 前序：BEXLMKCPDHQA 中序：LXMECKPBQHDA 后序：LMXCPKEQHADB 由中根序列和后根序列重建二叉树 基本基本思想思想 采用递归的算法 1. 选定后根序列中最后一个节点，即为根节点，在中根序列中找到这一 节点。这一节点将中根序列分为左右两棵子树，并根据这两棵子树将 后根序列中的两棵子树分出。 2. 分别在左右两棵子树中重复上述算法 3. 最后，可得到重建的二叉树 由中根序列和后根序列重建二叉树 代码实现代码实现 实现堆结构 基本基本思想：思想： 初始化堆： 分配内存空间，初始化数组长度为0 堆中插入一个元素： 在数组末尾增加一个元素，数组长度加1 删除堆中的一个元素： 遍历数组找到最小值，将最小值之后的元素全部向前移动一位，数组 长度减1 文本二叉树 基本思想：基本思想： 每个节点用一个结构体存储 建立二叉树 将根节点压栈 依次读入每一行的节点，并建立与其父节点（栈顶寻找层次比其大1 的节点）的关系，然后将节点压栈 注意不要将“*”，即空节点压栈 注意存在左子节点，不存在右子节点的情况 前序、中序、后序遍历二叉树：递归实现 edx二叉树（下） Problem1-1 下列关于二叉搜索树的说法正确的有下列关于二叉搜索树的说法正确的有： 1.二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由 小到大的排列。 2.如果结点x的左子树有右子树，则存在某个结点的值介于结点x的值和x左儿子 的值之间，并且这个结点在x的左子树之中。 3.当根结点没有左儿子时，根结点一定是值最小的结点。 4.二叉搜索树一定是满二叉树。 一个结点存在值比它大的结点，但不存在比它小的，这时它可能就只有一 个儿子。 5.二叉搜索树一定是完全二叉树。 按照从小到大的顺序依次插入一些值（数量超过1个），就可以让二叉搜索 树变成一条链，这样显然不是完全二叉树。 6.从根结点一直沿右儿子向下找不一定能找到树中值最大的结点。 Problem1-2 如果按关键码值递增的顺序依次将n个关键码值插入到二叉搜索 树中，如果对这样的二叉搜索树进行检索时，每次检索的字符都 等概率的从这n个关键码值中选取，平均比较次数为多少？ 答案答案： +1 2 检索第i大的元素需要比较i次，依此可得 =1 = ( + 1) 2 = + 1 2 Problem2-1 从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转 平衡），逐个插入关键码18,73,10,5,68,99,27,41,51,32,25构造出 一棵二叉搜索树，对该二叉搜索树按照前序、后序遍历得到的序 列为 答案：答案： 前序：18 10 5 73 68 27 25 41 32 51 99 后序：5 10 25 32 51 41 27 68 99 73 18 Problem2-2 从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平 衡），逐个插入关键码构造出一棵二叉搜索树，以怎样的顺序插入 关键码集合14,32,47,6,9,12,78,63,29,81可以使得树的深度最小？如 果有多组满足要求的方案，请使得你的答案中先插入的元素尽可能 的小。 12 6 47 92978 14326381 答案答案： 通过 log210 =4可以得到树的最小层 数。因为需要保证先插入的元素尽可 能的小，所以可以使得右子树尽可能 的满。构造出后，可得前序遍历结果 为12 6 9 47 29 14 32 78 63 81 Problem3-1 下列关于堆的说法正确的有： 1.堆一定是完全二叉树。 2.最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。 堆中一个结点的左儿子和右儿子并没有严格的大小关系 3.使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。 筛选法建堆的时间复杂度为O(n)，而一个一个插入建堆时间复杂度为O(nlog n)。 其中，n为堆中元素个数。 4.堆一定是满二叉树。 有些堆的倒数第二层有部分结点只有一个儿子 5.最小堆中，最下面一层最靠右的结点一定是权值最大的结点。 6.堆是实现优先队列的惟一方法。 堆只是实现优先队列的一种方法。用普通的队列也可以实现优先队列，只是效率 比较低 Problem3-2 对于关键码序列38,64,52,15,73,40,48,55,26,12，用筛选法建最小 值堆，若一旦发现逆序对就进行交换，共需交换元素多少次？ 答案：答案： 筛选法建堆过程： 1.先将所有元素放到一维数组中 2. 从最后一个分支结点（在完全二叉树的倒数第二层，此时i = (n- 1)/2 ）开始，从右至左依次通过筛选法调整 3. 对一层调整完后，继续对上一层进行同样的调整工作，直到整个过 程到达树根时，整棵完全二叉树就成为一个堆 73和12进行交换，52和40进行交换，64和12进行交换，38和12进行交换， 38和15进行交换，38和26进行交换，一共6次。 Problem4 对于如下图所示的最大堆，删除掉最大 的元素后，堆的前序、后序遍历结果是 答案：答案： 删除最大元素：SiftDown 前序：59 43 24 12 23 37 28 5 57 48 3 后序：12 23 24 28 5 37 43 48 3 57 59 Problem5-1 下列关于Huffman树和Huffman编码的说法正确的有： 1. Huffman树一定是满二叉树。 在建立的过程中，每次都选取两棵子树进行合并，所以所有结点要么有两个儿子，要么 没有儿子。 2. Huffman编码是一种前缀编码。 3. 对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。 把某一个结点往左子树编码0，往右子树编码1反过来就可以得到另外一组编码方案 4. Huffman树一定是完全二叉树。 5. Huffman编码中所有编码都是等长的。Huffman树的叶结点并不一定在同一层 6. 使用频率越高的字母，Huffman编码越长。 Problem5-2 一组包含不同权的字母已经对应好Huffman编码，如果某一个字母对应 编码001，下面说法正确的有： 1.以001开头的编码不可能对应其他字母。 通过001在Huffman树中已经到达叶结点，往下不会再有其他字母。 2.以01开头和1开头的代码肯定对应某个字母。 不然的话，不需要用001编码这一字母，可以更短 3.建好的Huffman树至少包含4个叶结点。 至少包含对应于001、000、01和1的4个叶结点 4.编码0和00可能对应于其他字母。 任何一个字母的编码都不可能其它字母编码的前缀 5.以000开头的代码不可能对应任何字母。 肯定要对应字母，不然的话001对应的字母可以缩短编码到00 Problem5-3 下表展示了在一段文本中每个字母出现的次数。 对于这段文本使用Huffman编码相较使用等长编码 能够节约多少比特的空间？ 48 21 27 912 48 1215 答案答案： Huffman编码： 2*12+3*8+2*15+3*4+2*9=108比特 定长编码： 每个字母需要3位，3*(12+8+15+4+9)=144比特 所以总共节约36比特 Problem5-4 对于给定的一组权W=1,4,9,16,25,36,49,64,81,100，构造一棵具 有最小带权外部路径长度的三叉树，写出这棵树的带权外部路径 长度。 答案：答案：705 增加额外字符来补充，令额外字符 的权值比最小的权值更小，如0， 使得n = 1c(k-1)。 1*4+4*4+9*3+16*3+25*2+36*2 +49*2+64*2+81*2+100*1=705 Problem6 若此段代码的作用是用来进行前序、中序遍历，那么应该在几号 访问点进行访问？ 答案：答案： 前序：No.1 中序：No.2 HUFFMAN编码树 创建创建HUFFMANHUFFMAN树树 二叉搜索树 基本思想：基本思想： 1. 使用递归的思想，从根节 点向下插入 2. 如果比当前节点小，则在 左子树中递归插入;如果比 当前节点大，则在右子树 中插入 3. 直到子树为空，建立新节 点 表达式-表达式树-表达式求值 基本思想：基本思想： 1. 读入中缀表达式 2. 使用栈存储，将中缀表达式转换为逆波兰表达式 3. 利用逆波兰表达式，将表达式存储为二叉树结构 4. 递归计算每个节点的深度 5. 利用节点深度，将表达式树输出 6. 再次使用栈和逆波兰表达式，计算表达式的值 表达式-表达式树-表达式求值 表达式树输出部分代码表达式树输出部分代码 二叉树书面作业 Q1 证明：由二叉树的中序中序遍历序列和后序后序遍历序列可唯一地确定出该 二叉树。 证明如下证明如下：数学归纳法证明。 1. 当n=1时，只有一个根结点，由中序序列和后序序列可以确定 这棵二叉树。 2. 设当n=m-1时结论成立，现证明当n=m时结论成立。 Q1 设中序序列为S1,S2,Sm,后序序列是P1,P2,Pm。后序序列最后一个 元素Pm是根，则在中序序列中可找到与Pm相等的结点Si(1im)， S1,S2,Si-1是左子树的中序序列，而Si+1,Si+2,Sm是右子树的中序 序列。 a) 若i=1，则S1是根，二叉树的左子树为空，右子树的结点数是m-1 b) 若i=m，则Sm是根，二叉树的右子树为空，左子树的结点数是m-1 c) 若1i 1， 2S1, 1S2 Q3 一种表示二维数组的方法是 4 叉树表示法，其中一个结 点的 4 个儿子分别表示数组的 NE,SE,SW,NW。四个分块 如图所示。这种表示二维数组的 4 叉树称为金字塔。 a) 设计一个基于金字塔表示法的矩阵乘法算法 b) 对于给定的 2 2矩阵，设计一个用二叉树表示这 个矩阵的算法。并将这个算法推广到可表示任意 MN 矩阵的情形，算法效率如何？ Q3(a) a) 设计一个基于金字塔表示法的矩阵乘法算法 主要思想：主要思想：分治法分治法 M0.NW = M.NW*M2.NW + M1.NE*M2.SW M0.NE = M1.NW* M2.NE + M1.NE*M2.SE M0.SW = M1.SW*M2.NW + M1.SE*M2.SW M0.SE = M1.SW*M2.NE + M1.SE*M2.SE Q3(b) 算法思想算法思想 每个节点的子节点都对应与上一个节点一半大小的矩阵， 并且每次取行列中较大的一个进行分裂 复杂度分析复杂度分析 总层数决定分裂次数，m对应于log m 的分裂次数，n对应 于log n 的分裂次数，因此总次数为log m + log n； 转换算法中每个节点都会遍历到，且每个节点仅访问一次， 因此复杂度为2log m+log n，即O(mn)。 M*N M*(N/2)M*(N/2) (M/2)*(N/2) Q3(b) Q4 如何使用优先级队列的堆实现解决下列问题？如果输入的数据是有 序的，那么又该如何解决？ a) 构建 Huffman 码； b) 计算大型浮点数集合的和； c) 在存有 10 亿个数的文件中找出最大的 100 万个数； d) 将多个较小的有序文件归并为一个较大的有序文件。 考察对Huffman树和最小堆的掌握 Q4(a) 构建 Huffman 码 输入数据无序： 1. 每次从堆中取出权值最小的两个结点并从堆中删除这两个结点 2. 新添加一个结点作为这两个结点的父结点，新结点的权值定义为左儿子和 右儿子的权值之和，并将新结点加入堆中 时间复杂度为O(nlogn)。 输入数据有序： 1. 建立两个队列A，B，将所有结点按照权值从小到大的顺序放入队列A中， 并令队列B为空。 2. 每次比较队列A和B的队首结点的权值大小，设权值较小的结点为x，将x从 所在的队列中删除。再次比较队列A和B的队首结点的权值大小，设权值较 小的结点为y，将y从所在的队列中删除。新添加一个结点并将x,y分别作为 新结点的左儿子和右儿子，令新结点的权值为x和y的权值之和，并将新结 点插入队列B的末尾。 时间复杂度为O(n)。 Q4(b)计算大型浮点数集合的和 输入数据无序: 1. 将所有的数放入一个堆中，每次从堆中取出两个最小的数，并从堆中 删除这两个数，将两个数的和加入堆中。 2. 反复进行上述