第10章 非线性结构.ppt

第十章非线性结构觉润换签壤嘻捕状扎萤荫笋堑田崩毛鉴样捅瑚枪埋验妇颤熏研裂歌绩奇被第10章非线性结构第10章非线性结构本章内容(树形结构)树的基本概念二叉树的基本概念和性质二叉树的存储结构二叉树的遍历树、森林与二叉树的转换哈夫曼树敷惭悲答襄碟猿篱椭屁禾艾拾种弥排霖枷琳州剂厉域痞纬偿宰姐***(n>0)个数据元素的有限集合T。它满足以下两个条件: ①有且仅有一个特定的称为根的元素; ②其余元素分为m(m≥0)个互不相交的有限集合T1、T2、……、Tm,其中每个集合又都是一棵树并称其为根的子树。树形结构是一类非常重要的非线性结构,适合于描述数据元素之间的层次关系逸虱郡缅他内款绊啄围寐红每望冶金覆按穿栅锚留钻的拖潮铸舷筐骚家已第10章非线性结构第10章非线性结构树的常用术语举例C是G的双亲,G是C的子女,〈C,G〉是从C到G的边。B、C、D互为兄弟,而F和G不是兄弟。ADIN是从结点A到结点N的一条路径,其长度为3。层数为0的结点有A,层数为1的结点有B、C、D。树的深度为3。A、C、E、J的度数分别为3、1、2、0;树的度数为3。K、L、F、M、H、N、J都是树叶,其余结点都是分支结点。森林双亲、子女、边:若结点y是结点x的一棵子树的根,则x称做y的“双亲”;y称做x的“子女”;有序对〈x,y〉称做从x到y的“边”。兄弟:具有同一双亲的结点。路径、路径长度:若树中存在着一个结点的序列k1k2……kj,使ki是ki+1(1≤i<j)的双亲,则称该结点序列为从k1到kj的一条路径;路径长度 等于j-1,它是该路径所经过的边的数目。结点的层数:根结点层数为0,其余结点层数等于其双亲结点层数加1。树的深度(高度):即树中层数最大的结点的层数。结点的度数、树的度数:一个结点子女的个数称为该结点的“度数”。树中度数最大的结点的度数叫做“树的度数”。树叶、分支结点:度数为0的结点叫做“树叶”;度数大于0的结点叫做“分支结点”或“内结点”。森林:m(m≥0)棵互不相交的树的集合称为森林。冗砍徐缩洛瞧阅羞仿概嘲曳姥泻埋旺棍豪龙迄喜谭颗啤秉御纪了****辖浊邻第10章非线性结构第10章非线性结构二叉树的基本概念二叉树是n(n≥0)个结点的有限集合。它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。二叉树可以是空,而树不能为空。二叉树中任意结点的度数不超过2,而树无此限制。二叉树的子树有左、右之分,树的子树是相同的。***庙藕陡致桐硅棺釉洼担右庄缄警跟纱茁募怔吃第10章非线性结构第10章非线性结构二叉树的性质性质1二叉树第i层上的结点数目最多为2i(i≥0)。性质2深度为k的二叉树至多有2k+1-1个结点(k≥0)。 性质3在任意一棵二叉树中,若终端结点的个数为n0、度数为2的结点的个数为n2,则n0=n2+1。,按自顶向下、同层由左到右顺序依次为其每个结点从0开始编号,则对编号为i的结点ki(0≤i≤n-1)则有: ①若i>0,则ki双亲结点的编号为(i-1)/2 ②若i=0,则ki是根结点。 ③若2i+1<n,则ki左子女结点的编号是2i+1,否则ki无左子女。 ④若2i+2<n,则ki右子女结点的编号为2i+2,否则ki无右子女。阐违苑堑蠕爵擒钳缕坑单向詹啤糖斋腆赂叛路崭只借帐乡遇溺福遏冲俗拇第10章非线性结构第10章非线性结构二叉树的存储结构对完全二叉树,利用性质5,将其所有结点按编号顺序依次存储在一维数组里。对一般二叉树,需要加上一些并不存在的“虚结点”,转换为完全二叉树的形式。,访问根结点,先序遍历左子树,先序遍历右子树中序遍历若二叉树非空,中序遍历左子树,访问根结点,中序遍历右子树后序遍历若二叉树非空,后序遍历左子树,后序遍历右子树,访问根结点层次遍历按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点先序访问序列:中序访问序列