资源描述
,*,树 结 构,树,二 叉 树,逻辑结构,逻辑结构,存储结构,存储结构,树的定义,基本术语,抽象数据类型,双亲表示法,孩子表示法,孩子兄弟表示法,二叉树的定义,特殊的二叉树,二叉树的性质,抽象数据类型,顺序存储结构,二叉链表,斜树,满二叉树,完全二叉树,三叉链表,线索链表,树的遍历,前序遍历,后序遍历,层序遍历,二叉树的遍历,前序遍历,中序遍历,后序遍历,层序遍历,遍历操作的实现,基于遍历的其他算法,相互转换,第,6,章 树和二叉树,1,习题,1.,填空题,树是,n,（,n0,）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成,m,（,m,0,）个（）的集合，每个集合都是根结点的子树。,【,解答,】,有且仅有一个，互不相交,树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。,【,解答,】,度，孩子，双亲,2,一棵二叉树的第,i,（,i1,）层最多有（）个结点；一棵有,n,（,n0,）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。,【,解答,】2(i-1),，,(n+1)/2,，,(n-1)/2,【,分析,】,设满二叉树中叶子结点的个数为,n0,，度为,2,的结点个数为,n2,，由于满二叉树中不存在度为,1,的结点，所以,n=n0+n2,；由二叉树的性质,n0=n2+1,，得,n0=(n+1)/2,，,n2=(n-1)/2,。,(4),深度为,k,的二叉树中，所含叶子的个数最多为（）,【,解答,】2(k-1),【,分析,】,在满二叉树中叶子结点的个数达到最多。,3,(5),具有,100,个结点的完全二叉树的叶子结点数为（）。,【,解答,】50,【,分析,】100,个结点的完全二叉树中最后一个结点的编号为,100,，其双亲即最后一个分支结点的编号为,50,，也就是说，从编号,51,开始均为叶子。,(6),已知一棵度为,3,的树有,2,个度为,1,的结点，,3,个度为,2,的结点，,4,个度为,3,的结点。则该树中有（）个叶子结点。,【,解答,】12,【,分析,】,根据二叉树性质,3,的证明过程，有,n0=n2+2n3+1,（,n0,、,n2,、,n3,分别为叶子结点、度为,2,的结点和度为,3,的结点的个数,),4,(7),某二叉树的前序遍历序列是,ABCDEFG,，中序遍历序列是,CBDAFGE,，则其后序遍历序列是（）。,【,解答,】CDBGFEA,【,分析,】,根据前序遍历序列和后序遍历序列将该二叉树构造出来。,二,.,选择题,如果结点,A,有,3,个兄弟，,B,是,A,的双亲，则结点,B,的度是（）。,A 1 B 2 C 3 D 4,【,解答,】D,5,设二叉树有,n,个结点，则其深度为（）。,A n-1 B n C +1 D,不能确定,【,解答,】D,(3),二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。,A,空或只有一个结点,B,高度等于其结点数,C,任一结点无左孩子,D,任一结点无右孩子,【,解答,】B,【,分析,】,此题注意是序列正好相反，则左斜树和右斜树均满足条件。,6,(4),任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。,A,肯定不发生改变,B,肯定发生改变,C,不能确定,D,有时发生变化,【,解答,】A,【,分析,】,三种遍历次序均是先左子树后右子树。,7,三,.,判断题,(1),在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。,【,解答,】,对。由前序遍历的操作定义可知。,(2),二叉树是度为,2,的树。,【,解答,】,错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为,1,。,8,1.,已知一棵度为,m,的树中有：,n1,个度为,1,的结点，,n2,个度为,2,的结点，,，,nm,个度为,m,的结点，问该树中共有多少个叶子结点？,(,写出解答过程,),四,.,简答题,9,2.,已知二叉树的中序和后序序列分别为,CBEDAFIGH,和,CEDBIFHGA,，试构造该二叉树,.(,写出构造过程,),10,3.,试找出分别满足下列条件的所有二叉树：前序序列和中序序列相同。,中序序列和后序序列相同。,前序序列和后序序列相同。,11,第二次上机作业（,2011.11.18,）,已知某字符串,S,中共有,n,种字符，各种字符分别出现,w1,次、,w2,次、,w3,次、,w4,次、,w5,次、,w6,次、,w7,次和,w8,次，利用赫夫曼树对该字符串用,0,，,1,进行前缀编码，写出算法并上机实现你的算法并进行测试。,要求：期末考之前提交源程序和上机报告。提交办法与第一次上机作业一样。,12,
展开阅读全文