2011年3月二级公共基础知识讲义(1.6树与二叉树).ppt

1,内部资料,2011年3月计算机等级考试 二级公共基础知识培训讲义 理工大楼915,2,二级Access考试介绍,一、考试方式 1笔试：90 分钟，满分100 分，其中含公共基础知识部分30分 2上机操作：90 分钟，满分100 分 二、笔试题型及分值（根据考试大纲及往年试题) 1选择题70 分（每小题2分，共3 5题） 2填空题30 分（每空2 分，共15题） 三、上机操作 1基本操作（30 分） 2简单应用（40 分） 3综合应用（30 分）,3,我们的目标,通过二级考试,4,基础知识部分：30分,设有10道选择题和5道填空题,5,第一章 数据结构与算法,1.1 算法 1.2 数据结构的基本概念 1.3 线性表及其顺序存储结构 1.4 栈和队列 1.5 线性链表 1.6 树与二叉树 1.7 查找技术 1.8 排序技术,6,1.6 树与二叉树,1.6.1 树的基本概念 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。,7,1.6.2 二叉树及其基本性质,二叉树的特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,8,二叉树的基本性质：,（1）在二叉树的第k层上，最多有2k-1(k1)个结点； （2）深度为m的二叉树最多有2m-1个结点； （3）度为0的结点（即叶子结点）总是比度为2的结点多一个； （4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分；,9,满二叉树,满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。,10,11,12,完全二叉树,完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。,13,满二叉树与完全二叉树,（5）具有n个结点的完全二叉树的深度为log2n+1； （6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，.n给结点进行编号（k=1,2.n），有以下结论： 若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)； 若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）； 若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。,14,1.6.3 二叉树的存储结构,在计算机中，二叉树存储结构采用链式存储结构。,对于满二叉树与完全二叉树可以按层序进行顺序存储。,15,1.6.4 二叉树的遍历,二叉树的遍历是指不重复地访问二叉树中的所有结点。 二叉树的遍历： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树； （2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树； （3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。,16,1. 前序遍历（DLR）,前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）访问根结点 （2）前序遍历左子树 （3）前序遍历右子树 注意的是：遍历左右子树时仍然采用前序遍历方法。 例：如图二叉树， 则前序遍历结果是：A B D E C F,17,2. 中序遍历（LDR）,中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即： 若二叉树为空则结束返回，否则： （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树。 注意的是：遍历左右子树时仍然采用中序遍历方法。 例：如图二叉树， 则中序遍历结果是：D B E A F C,18,3. 后序遍历（LRD）,后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。即： 若二叉树为空则结束返回，否则： （1）后序遍历左子树， （2）后序遍历右子树 （3）最后访问根结点。 注意的是：遍历左右子树时仍然采用后序遍历方法。 例：如图二叉树，,19,例:,A B D E C F G,D B E A F G C,D E B G F C A,前序遍历：,中序遍历：,后序遍历：,20,历年考题,【2005年4月填空第1题】（1）某二叉树中度为2的结点有18个，则该二叉树中有_个叶子结点。 【2005年4月填空第4题】（4）一棵二叉树第六层（根结点为第一层）的结点数最多为_个。 【2007年4月选择第7题】（7）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为 A）n+1 B）n-1 C）2n D）n/2,21,历年考题,【2007年4月填空第1题】（1）在深度为7的满二叉树中，度为2的结点个数为 。 【2007年9月选择第8题】（8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 A)219 B)221 C)229 D)231 【2008年4月填空第2题】（2）深度为5的满二叉树有 个叶子结点。,22,【2006年4月选择第6题】,（6）对下列二叉树 进行后序遍历的结果为 A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA,23,【2007年4月选择第6题】,（6）对下列二叉树 进行前序遍历的结果为 A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ,24,【2007年9月填空第4题】,（4）对下列二叉树进行中序遍历的结果为 【4】 。,25,2008.9,(1)对下列二叉树进行中序遍历的结果是 【1】 。,26,P39 练习