pascal数据结构之非线性结构.doc

第一节 树的概念教学课件下载一、树的定义 树是一种常见的非线性的数据结构。 树的定义：树是n(n0)个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根； 除根外，其余的每个结点都有且仅有一个前驱； 除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后驱（儿子结点）；二、结点的分类 在树中，一个结点包含一个元素以及所有指向其子树的分支。 结点一般分成三类: 根结点：没有前驱的结点。在树中有且仅有一个根结点。如上图（b）中的r； 分支结点：除根结点外，有后驱的结点称为分支结点。如上图（b）中的a，b，c，x，t，d，i。分支结点亦是其子树的根； 叶结点：没有后驱的结点称为树叶。如上图（b）中的w，h，e，f，s，m，o，n，j，u为叶结点。由树的定义可知，树叶本身也是其父结点的子树。 根结点到每一个分支结点或叶结点的路径是唯一的。例如上图（b）中，从根r到结点i的唯一路径为rcti。三、有关度的定义 结点的度：一个结点的子树数目称为该结点的度。在上图（b）中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。 树的度：所有结点中最大的度称为该树的度。图（b）中的树的度为3。四、树的深度（高度） 树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。 图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图（b）中树的深度为5。五、森林 所谓森林，是指若干棵互不相交的树的集合。 如图（b）去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合Ta，Tb，Tc就为森林，这三棵子树的具体形态如图（c）。六、有序树和无序树 按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。第二节 树的表示方法和存储结构一、树的表示方法 树的表示方法一般有两种： 自然界的树形表示法：用结点和边表示树，例如下图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。 括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如 下图(b)可写成如下形式 （r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）二、树的存储结构 树的存储结构一般有两种1.静态的记录数组 所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标。Const n=树的度； max=结点数的上限；Type node=record data：； 数据域s ch：array1n of integer；指向各儿子的下标 end； treetype=array1.maxof node；Var tree：treetype；该图用静态数组方法保存如右表下标数据域treei.data儿子的下标序列treei.ch1r2342a5603b7004c89105w0006x111207f0008s0009t1314010u00011d150012e00013i16171814j00015h00016m00017o00018n000 2.动态的多重链表 由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下：Const n=树的度；Type treetype=node； node=record data：datatype；数据域 next：array1n of treetype；指向各儿子的指针域 end；Var root：treetype；上图用多重链表表示如下：第三节 二叉树的概念一、二叉树的递归定义和基本形态 1.二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后继，且其子树有左右之分（次序不能任意颠倒）。 2.二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件： 有一个特定的结点称为根； 余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树； 由上述定义可以看出，二叉树和树是两个不同的概念: 树的每一个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2； 树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后继为左儿子，右后继为右儿子。 3.二叉树的五种基本形态二、二叉树的两个特殊形态 1.满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如下图(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。 2.完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）三、二叉树的三个主要性质 性质1：在二叉树的第i（1）层上，最多有2i-1个结点。 性质2：在深度为k(k1)的二叉树中最多有2k-1个结点。 性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。四、普通有序树转换成二叉树普通树为有序树T，将其转化成二叉树T的规则如下： T中的结点与T中的结点一一对应，即T中每个结点的序号 和值在T中保持不变； T中某结点v的第一个儿子结点为v1，则在T中v1为对应结点v的左儿子结点； T中结点v的儿子序列，在T中被依次链接成一条开始于v1的右链； 由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。五、森林转换成二叉树 如果m棵互不相交的普遍有序树组成了森林F=T1，Tm。我们可以按下述规则将森林F转换成一棵二叉树b=R，LB，RB： 若F为空（m=0），则b为空树； 若F非空（m0），则b的根R即为森林中第一棵树的根R(T1)；b的左子树LB是从T1的根结点的子树森林F1=T11，T12，T1k转换而成的二叉树；其右子树RB是从森林F2=T2，T3，Tm转换成的二叉树。第四节 二叉树的遍历一、树的存储结构1.顺序存储结构 将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括 一个数据域（data）； 三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。 满二叉树和完全二叉树一般采用顺序存储结构。Const m=树中结点数上限；Type node=record结点类型 data：；数据值 prt，lch，rch：0m； 父结点、左儿子、右儿子编号 end； treetype=array1m of node；二叉树的顺序表类型Var Tree：treetype；二叉树 2.链式存储结构 对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域： 值域： data 左指针域：lch 右指针域：rch 这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点Type bitrpetr=node；结点指针类型 node=record结点类型 data：；值域 lch，rch：bitreptr；左指针域和右指针域 end；Var bt：bitreptr；头指针二、二叉树的遍历 1.二叉树遍历的定义 按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。 2.二叉树遍历的顺序 如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。以下遍历以该树为例三、前序遍历 规则如下： 若二叉树为空，则退出。否则 访问处理根结点； 前序遍历左子树； 前序遍历右子树； 如上图的前序遍历结果为a b d e h i c f g顺序结构:Procedue preorder(i:integer);begin if i0 then begin 访问处理treei.data; preorder(treei.lch);递归遍历左子树 preorder(treei.rch);递归遍历右子树 end;end;链式结构:Procedue preorder(bt:bitreptr);begin if btnil then begin 访问处理bt.data; preorder(bt.lch);递归遍历左子树 preorder(bt.rch);递归遍历右子树 end; end;四、中序遍历 规则如下： 若二叉树为空，则退出；否则 中序遍历左子树； 访问处理根结点； 中序遍历右子树； 如上图的中序遍历结果为d b h e i a f c g顺序结构:Procedue inorder(i:integer);begin if i0 then begin inorder(treei.lch);递归遍历左子树 访问处理treei.data; inorder(treei.rch);递归遍历右子树 end;end;链式结构:Procedue inorder(bt:bitreptr);begin if btnil then begin inorder(bt.lch);递归遍历左子树 访问处理bt.data; inorder(bt.rch);递归遍历右子树 end; end;五、后序遍历 规则如下： 若二叉树为空，则退出；否则 后序遍历左子树； 后序遍历右子树； 访问处理根结点； 如上图的后序遍历结果为d h i e b f g c a顺序结构:Procedue postorder(i:integer);beginif i0 then begin postorder(treei.lch);递归遍历左子树 postorder(treei.rch);递归遍历右子树 访问处理treei.data; end;end;链式结构:Procedue postorder(bt:bitreptr);begin if btnil then begin postorder(bt.lch);递归遍历左子树 postorder(bt.rch);递归遍历右子树 访问处理bt.data; end; end;第五节 普通树的遍历一、先根次序遍历树 规则：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。上图先根遍历次序为r a w x d h e b f c s t i m o n j u当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。二、后根次序遍历树 规则：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。 上图后根遍历次序为w h d e x a f b s m o n i j t u c r 当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。三、森林的遍历 1.先根遍历森林 若森林非空，则可按下述规则遍历之 访问森林中第一棵树的根结点； 先根遍历第一棵树中根结点的子树森林； 先根遍历其余树构成的森林； 若对下图的森林进行先根遍历，则得到森林的先根序列为A B D C E F G H J I。森林的先根遍历即为其对应的二叉树的前序遍历。 2.后根遍历森林 若森林非空，则可按下述规则遍历之 后根遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 后根遍历其余树构成的森林； 若对上图(a)中的森林进行先根遍历，则得到森林的后根序列为B C D A F E H J I G 。森林的后根遍历即为其对应的二叉树的中序遍历。例如，对上图(c)中的二叉树进行中序遍历，亦可得出对应森林（上图(a)的后根遍历序列。第六节 根据两种遍历顺序确定树结构一、由两种顺序确定树结构 遍历二叉树有三种规则： 前序遍历：根左子树右子树； 中序遍历：左子树根右子树； 后序遍历：左子树右子树根； 由于前序遍历的第一个字符和后序遍历的最后一个字符为根，中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构，因此二叉树的形态可以由其中序与后序或者前序与中序唯一确定。但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点，因此这两个遍历顺序可对应多种二叉树的形态。二、由中序遍历与后序遍历确定前序遍历 由二叉树的遍历规则可以看出，后序遍历的最后一个字 符为根，中序遍历中位于该字符左侧的子串为左子树中序遍历的结果；中序遍历中位于该字符右侧的子串为右子树中序遍历的结果。 设 中序遍历s1=s1sksn 后序遍历s2=s1sn 显然，后序遍历中的sn为二叉树的根。按照前序遍历的规则输出sn。在中序遍历中与sn相同的字符为sk。若k1，说明左子树存在，位于sk左侧的子串s1sk-1为左子树中序遍历的结果，后序遍历中的前缀s1sk-1为左子树后序遍历的结果；若k1若左子树存在，则递归遍历左子树 then solve1(copy(s1，1，k-1)，copy(s2，1，k-1)； if k1若左子树存在，则递归遍历左子树 then solve2(copy(s1，1，k-1)，copy(s2，2，k-1)； if klength(s1) 若右子树存在，则递归遍历右子树 then solve2(copy(s1，k+1，length(s1)-k)，copy(s2，k+1，length(s2)-k)； end； write(s1k)；或者输出子树根s21end;第七节 二叉排序树一、概念 所谓二叉排序树是指具有下列性质的非空二叉树 若根结点的左子树不空，则左子树的所有结点值均小于根结点值； 若根结点的右子树不空，则右子树的所有结点值均不小于根结点值； 根结的左右树也分别为二叉排序树； 显然，对二叉排序树进行中序遍历，可得出结点值递增的排序序列。假设待排序的数存在数组a中procedure createtree;begin fillchar(b，sizeof(b)，0); b1.data:=a1; 二叉排序树初始化 for i:=2 to n do begin bi .data:=ai; p:=1; while true do begin if aibpdata 若aibpdata，顺左指针方向寻找顶点i的插入位置 then if bpl0 then p:=bpl else begin bpl:=i;break;end else 若aibpdata 时顺右指针方向寻找顶点i的插入位置 if bpr0 then p:=bpr else begin bpr:=i; break; end; end;while end;forend;createtree第八节 最优二叉树(哈夫曼树)一、概念在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使（Wk第k个叶结点的权值；Pk第k个叶结点的带权路径长度）达到最小。二、最优二叉树的构造方法假定给出n个结点ki(i=1n)，其权值分别为Wi(i=1n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下： 首先，将给定的n个结点构成n棵二叉树的集合F=T1，T2，Tn。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步 在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和； 在F中删除这两棵二叉树，同时将新得到的二叉树加入F 重复、，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。三、最优二叉树的数据类型定义 在最优二叉树中非叶结点的度均为2，为满二叉树，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。 Const n=叶结点数的上限； m=2*n-1；最优二叉树的结点数 Type node=record结点类型 data：；权值 prt，lch，rch,lth：0m；父指针、左、右指针和路径长度 end； wtype=array1n of ；n个叶结点权值的类型 treetype=array1m of node；最优二叉树的数组类型 Var tree：treetype； 其中tree 1n为叶结点，tree n+12n-1为中间结点，根为tree 2n-1四、构造最优二叉树的算法procedure hufm(w：wtype；var tree：treetype；var bt：integer)； function min (h：integer)：integer；在前h个结点中选择父指针为0且权值最小的结点min begin ml:=； for p:=1 to h do if (treepprt=0)and(m1treepdata) then begin i:=p；m1:=treepdata； end； min:=i； end；min begin fillchar (tree，sizeof(tree)，0)；构造初始集合F for i:=1 to n do read(treeiData)； for k:=n+1 to m do 构造最优二叉树 begin 计算k为根的左儿子和右儿子 i:=min(k-1)