资源描述
,完全二叉树的计算问题,31.,对一颗,699,个结点的完全二叉树，求它共有的非叶子结点数？,首先应该理解什么是“完全二叉树”,完全二叉树数学定义：设二叉树的高度为,h,，若：,除第,h,层外，其它各层的结点数都达到最大个数,第,h,层所有的节点都连续集中在最左边,同时成立，则称此这二叉树为,完全二叉树,完全二叉树的计算问题,完全二叉树数学定义：设二叉树的高度为,h,，若：,除第,h,层外，其它各层的结点数都达到最大个数,第,h,层所有的节点都连续集中在最左边,同时成立，则称此这二叉树为,完全二叉树,A,F,B,C,G,I,J,E,A,F,K,B,C,G,I,J,L,E,L,完全二叉树的计算问题,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=188,511,个,188,个,9,28=256,188/2=94,256-94=162,非叶子节点的个数,=699-188-162=349,由遍历逆推二叉树问题,32.,官方教材习题,已知一颗二叉树的前序遍历为,ABDEGCFH,，中序遍历为,DBGEACHF,，则该二叉树的后序遍历为（,）,根左右,ABDEGCFH,左根右,DBGEACHF,A,B,C,D,E,F,G,H,由遍历逆推二叉树问题,37.,设一颗二叉树的中序遍历结果为,DBEAFC,，前序遍历结果为,ABDECF,，则后序遍历结果为？,先前资料网上发布的答案有误，请以下图为准！,B,A,D,E,C,F,新颖题型,38.,二叉树的深度为,k,，且它没有度为,1,的结点，则此二叉树中所含结点数至多为,。,明显满二叉树符合题目要求，且满二叉树已经是一定深度树中最多结点的情况。所以填,2k-1,本题为官方教材附录“样卷”中的一题，难度很小。但是，“样卷”所给答案为,2*k-1,，与我们计算的答案有所出入。,但事实上，若将题目中“至多”两字改为“至少”，则答案就恰为,2*k-1,，并且题目将具有一定的难度。所以我怀疑，样卷本来要考查的就是“至少”，而“至多”系笔误。那么，你会计算“至少”么？,新颖题型,38.,二叉树的深度为,k,，且它没有度为,1,的结点，则此二叉树中所含结点数,至少,为,。,新颖题型,补充题,1,：中序遍历可以记录多项式的四则运算。下面的二叉树表达的多项式运算之后的结果是？,*,+,-,5,2,2,4,新颖题型,补充题,2,：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过,1,，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？,新颖题型,补充题,2,：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过,1,，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？,新颖题型,补充题,2,：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过,1,，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？,新颖题型,补充题,2,：若二叉树中每一个结点都左右两颗子树的深度绝对值之差不超过,1,，则称此二叉树为“平衡二叉树”，则下列选项中，是平衡二叉树的是？,
展开阅读全文