全国计算机等级考试二级VisualBasic精讲.pptx

完全二叉树的计算问题31.对一颗699个结点的完全二叉树，求它共有的非叶子结点数？首先应该理解什么是“完全二叉树”完全二叉树数学定义：设二叉树的高度为h，若：i)除第 h 层外，其它各层的结点数都达到最大个数ii)第 h 层所有的节点都连续集中在最左边同时成立，则称此这二叉树为完全二叉树完全二叉树的计算问题完全二叉树数学定义：设二叉树的高度为h，若：i)除第 h 层外，其它各层的结点数都达到最大个数ii)第 h 层所有的节点都连续集中在最左边同时成立，则称此这二叉树为完全二叉树AFBCGIJEAFKBCGIJLEL完全二叉树的计算问题31.对一颗699个结点的完全二叉树，求它共有的非叶子结点数？解：首先计算此完全二叉树的层数。我们知道，9层的满二叉树一共有29-1=511个结点，而10层满二叉树一共有210-1=1023个结点。因为511 699 1023所以可以知道此完全二叉树一共有10层，且前9层成满结点状态。前9层共有的结点数=29-1=511个，所以第10层的结点数为699-511=148完全二叉树的计算问题31.对一颗699个结点的完全二叉树，求它共有的非叶子结点数？前9层共有的结点数=29-1=511个，所以第10层的结点数为699-511=188511个188个928=256188/2=94256-94=162非叶子节点的个数=699-188-162=349由遍历逆推二叉树问题32.官方教材习题已知一颗二叉树的前序遍历为ABDEGCFH，中序遍历为DBGEACHF，则该二叉树的后序遍历为（）根左右ABDEGCFH 左根右DBGEACHF A AB BC CD DE EF FG GH H由遍历逆推二叉树问题37.设一颗二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为？先前资料网上发布的答案有误，请以下图为准！B BA AD DE EC CF F新颖题型38.二叉树的深度为k，且它没有度为1的结点，则此二叉树中所含结点数至多为 。明显满二叉树符合题目要求，且满二叉树已经是一定深度树中最多结点的情况。所以填2k-1本题为官方教材附录“样卷”中的一题，难度很小。但是，“样卷”所给答案为2*k-1，与我们计算的答案有所出入。但事实上，若将题目中“至多”两字改为“至少”，则答案就恰为2*k-1，并且题目将具有一定的难度。所以我怀疑，样卷本来要考查的就是“至少”，而“至多”系笔误。那么，你会计算“至少”么？新颖题型38.二叉树的深度为k，且它没有度为1的结点，则此二叉树中所含结点数至少为 。新颖题型补充题1：中序遍历可以记录多项式的四则运算。下面的二叉树表达的多项式运算之后的结果是？*+-5 52 22 24 4新颖题型补充题2：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过1，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？新颖题型补充题2：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过1，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？新颖题型补充题2：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过1，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？新颖题型补充题2：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过1，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？