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

1内部资料2011年3月计算机等级考试二级公共基础知识培训讲义理工大楼9152二级Access考试介绍一、考试方式1．笔试：90分钟，满分100分，其中含公共基础知识部分30分2．上机操作：90分钟，满分100分二、笔试题型及分值（根据考试大纲及往年试题)1．选择题70分（每小题2分，共35题）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排序技术61.6树与二叉树1.6.1树的基本概念树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。71.6.2二叉树及其基本性质二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。8二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；9满二叉树满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。101112完全二叉树完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。13满二叉树与完全二叉树（5）具有n个结点的完全二叉树的深度为[log2n]+1；（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：①若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)；②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。141.6.3二叉树的存储结构在计算机中，二叉树存储结构采用链式存储结构。对于满二叉树与完全二叉树可以按层序进行顺序存储。151.6.4二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。161.前序遍历（DLR）前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。即：若二叉树为空则结束返回，否则：（1）访问根结点（2）前序遍历左子树（3）前序遍历右子树注意的是：遍历左右子树时仍然采用前序遍历方法。例：如图二叉树，则前序遍历结果是：ABDECF172.中序遍历（LDR）中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：若二叉树为空则结束返回，否则：（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树。注意的是：遍历左右子树时仍然采用中序遍历方法。例：如图二叉树，则中序遍历结果是：DBEAFC183.后序遍历（LRD）后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。即：若二叉树为空则结束返回，否则：（1）后序遍历左子树，（2）后序遍历右子树（3）最后访问根结点。注意的是：遍历左右子树时仍然采用后序遍历方法。例：如图二叉树，19例:ABDECFGDBEAFGCDEBGFCA前序遍历：中序遍历：后序遍历：20历年考题【2005年4月填空第1题】（1）某二叉树中度为2的结点有18个，则该二叉树中有______个叶子结点。【2005年4月填空第4题】（4）一棵二叉树第六层（根结点为第一层）的结点数最多为______个。【2007年4月选择第7题】（7）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为A）n+1B）n-1C）2nD）n/221历年考题【2007年4月填空第1题】（1）在深度为7的满二叉树中，度为2的结点个数为。【2007年9月选择第8题】（8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为A)219B)221C)229D)231【2008年4月填空第2题】（2）深度为5的满二叉树有个叶子结点。22【2006年4月选择第6题】（6）对下列二叉树进行后序遍历的结果为A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCA23【2007年4月选择第6题】（6）对下列二叉树进行前序遍历的结果为A）DYBEAFCZXB）YDEBFZXCAC）ABDYECFXZD）ABCDEFXYZ24【2007年9月填空第4题】（4）对下列二叉树进行中序遍历的结果为【4】。252008.9(1)对下列二叉树进行中序遍历的结果是【1】。26P39练习题填空第2小题设一棵完全二叉树共有700个结点，则在该二叉树中有个叶子结点。27二叉树的遍历模拟题已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。A)cedbaB)acbedC)decabD)deabc