期末复习-树、图、查找、排序.ppt

《期末复习-树、图、查找、排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、期末复习树、图、查找、排序Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.树:是n(n≥0)个结点的有限集合。如果该集合为空，称为空树。在任意一棵非空树中:ABCDEFKLGHIJM树的定义有且仅有一个特定的称为根结点(root)的结点;2)其他结点可分为若干个互不相交的子集,而且每一个子集本身又是一棵树,称为根的子树。递归定义Evaluationonly.CreatedwithAspose.Slidesfor.

2、NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支结点分支的个数,即子树的数目如：A的度-3；B的度-2；K的度-0；树中所有结点的度的最大值如：树的度为3；度为零的结点，也称终端结点如例：K，L，F，G，M，I，J为终端结点度大于零的结点如例：A,B,C,D,E基本术语612345Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copy

3、right2004-2011AsposePtyLtd.森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMFEvaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)Eva

4、luationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.7.2二叉树Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.二叉树或为空树；或是由一个根结点加上两棵分别称为左和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF特点：1）每个结点最多只有两棵子树；2

5、）两颗子树有左右之分，顺序不能换。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.特殊的二叉树：满二叉树满二叉树：指的是

6、深度为k且含有2k-1个结点的二叉树。1234567891011121314151234567深度为3，节点数=23-1=7深度为4，节点数=24-1=15特点：1）每一层上的结点数都是最大结点数；2）叶子结点都在最后一层。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。12345612345612345特点：1）除了最下一层外其余各层都是满的

7、；2）最下一层的结点都集中在该层的左侧。12345678910特殊的二叉树：完全二叉树Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.性质1：满二叉树的第i层上有2i-1个结点(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1时，只有一个根结点，2i-1=20=1；假设第j层有2j-1结点，命题成立;第j层的每个结点都有2个结点，则第(j+1)层上的结点数=2*2j-1=2j=2(j+1)-1。二叉树的性

8、质1234