NOIP初赛复习03.ppt

《NOIP初赛复习03.ppt》由会员分享，可在线阅读，更多相关《NOIP初赛复习03.ppt（116页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、目录 栈及其应用栈及其应用 队列及其应用队列及其应用 树及其应用树及其应用一、栈 栈（stack）：一种特殊的线性表，限定只能在表尾进行插入、 删除操作的线性表。 特点：后进先出LIFO(Last In First Out)栈顶栈顶(top)(top)：允许插入和删除数据元素的一端：允许插入和删除数据元素的一端。 栈底栈底(bottom)(bottom)：固定的一端。：固定的一端。空栈：不含任何元素。空栈：不含任何元素。进栈进栈( (压栈压栈push)push)：插入元素。：插入元素。出栈出栈( (退栈退栈pop)pop)：删除元素。：删除元素。1.栈的概念栈底栈底栈顶栈顶进栈进栈出栈出栈系统

2、栈在调用过程或函数之前，系统需完成三件事：将所有的实在参数、返回地址等信息传递给被调用过程保存；为被调用过程的局部变量分配存储区；将控制转移到被调过程的入口。从被调用过程返回调用过程之前，系统也应完成三件工作：保存被调过程的计算结果；释放被调过程的数据区；依照被调过程保存的返回地址将控制转移到调用过程。当有多个过程构成嵌套调用时，按照“后调用先返回”的原则用一组连续的存储单元依此存放自栈底到栈顶的用一组连续的存储单元依此存放自栈底到栈顶的数据元素，同时设立指针数据元素，同时设立指针toptop（称为栈顶指针）以（称为栈顶指针）以指示栈顶元素的当前位置。指示栈顶元素的当前位置。 2.栈的顺序存储

3、1. .设栈设栈S S的初始状态为空，现有序列的初始状态为空，现有序列1,2,3,4,51,2,3,4,5，对该序，对该序列在栈列在栈S S上依次进行如下操作（从序列中的上依次进行如下操作（从序列中的1 1开始）：开始）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是：栈的元素序列是：3,42. 2.若进栈的序列是若进栈的序列是1 1、2 2、3 3、4 4、5 5，问能否得，问能否得到出栈序列到出栈序列4 4、3 3、5 5、1 1、2 2 ？123出栈的元素出栈的元素334 445出栈的元素出栈的元素1234 44335 55此时

4、能出栈此时能出栈的只能是的只能是2 2不能不能小练习小练习3如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c（如右图所示），另有元素d已经出栈，则可能的入栈顺序是（ ）。（noip2012提高组）Aa, b, c, d Bb, a, c, d Ca, c, b, d Dd, a, b, c小练习4在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。A系统分配的栈空间溢出 B系统分配的堆空间溢出 C系统分配的队列空间溢出 D系统分配的链表空间溢出5. 元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可

5、能是( )。A. R1 B. R2 C.R4 D.R53.栈的基本操作CONST MAXCAPACITY = 100; 栈的最大容量栈的最大容量 BOTTOM = 0; 栈底标志栈底标志 TYPE ElemType = integer; 栈内元素数据类型栈内元素数据类型 Stack = array 1.MAXCAPACITY of ElemType; 用数组表示的栈用数组表示的栈VAR s : Stack; 定义定义s为栈为栈 top : integer; 栈顶标志栈顶标志 v, n : integer;3.栈的基本操作FUNCTION StackEmpty(s : Stack; top :

6、integer) : boolean; 判断是否栈空判断是否栈空 begin StackEmpty := (top = BOTTOM);end; StackEmpty FUNCTION StackFull(s : Stack; top : integer) : boolean; 判断是否栈满判断是否栈满 begin StackFull := (top = MAXCAPACITY);end; StackFullPROCEDURE Push(var s : Stack; var top : integer; data : ElemType); 进栈进栈 begin if StackFull(s,

7、top) then writeln(overflow) else begin inc(top); stop := data; end; ifend; Push进栈出栈操作之后，原栈顶元素依然存在，出栈操作之后，原栈顶元素依然存在，只是栈顶指针下移，不再指向它。只是栈顶指针下移，不再指向它。PROCEDURE Pop(var s : Stack; var top : integer) ; 出栈出栈 begin if StackEmpty(s, top) then writeln(underflow) else dec(top);end; Pop出栈FUNCTION GetTop(s : Stac

8、k; top : integer) : ElemType; 获取栈顶元素的值获取栈顶元素的值 begin if StackEmpty(s, top) then writeln(underflow) else GetTop := stop;end; GetTop这个算法中栈顶指针保持不变这个算法中栈顶指针保持不变, ,注意与注意与pop(s)pop(s)的区别的区别 。获取栈顶元素4.栈的应用举例题目：输入一个正整数题目：输入一个正整数n，试分离并输出其，试分离并输出其各位数字。例如，输入各位数字。例如，输入n=1234，则输出，则输出1，2，3，4。（保证。（保证n不超出不超出longint的

9、范围）的范围）输入一个正整数输入一个正整数n n，试分离并输出其各位数字，试分离并输出其各位数字 PROGRAM Separate(INPUT, OUTPUT);VAR v, n :longint;BEGIN MAIN writeln(Input n:); readln(n); while n 0 do begin v := n mod 10; 分离出分离出n n的个位数字的个位数字 write(v:2); n := n div 10; 去除去除n n的个位数字的个位数字 end; whileEND.下列程序对吗？利用栈解决分离数字问题利用栈解决分离数字问题BEGIN MAIN top :=

10、0; 栈顶初始化栈顶初始化 readln(n); while n 0 do 分离数字并将其入栈分离数字并将其入栈 begin v := n mod 10; 分离出分离出n n的个位数字的个位数字 Push(s, top, v); 个位数字入栈个位数字入栈 n := n div 10; 去除去除n n的个位数字的个位数字 end; while while not StackEmpty(s, top) do 输出数字并出栈输出数字并出栈 begin write(GetTop(s, top) : 2); Pop(s, top); end; whileEND.小练习地面上有标号为A、B、C的3根细柱,

11、 在A柱上放有10个直径相同中间有孔的圆盘, 从上到下次依次编号为1, 2, 3, ，将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么, 在C柱上, 从下到上的盘子的编号为（ ）。 A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 E. 2 1 4 3 7 5 二、队列u 队列也是一种队列也是一种受限的线性表受限的线性表。它的所有。它的所有插入都在队列的一端进行，所有删除都插入都在队列的一端进行，所有删除都在另一端进行。在另一端进行

12、。u 特点：先进先出特点：先进先出(FIFO(FIFO，First First In First Out)In First Out)u 例例1 1：到医院看病，首先需要到挂号处挂：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。号，然后，按号码顺序救诊。u 例例2 2：乘坐公共汽车，应该在车站排队，：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。车来后，按顺序上车。1.队列的概念 允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。 队列的插入和删除我们称为入队和出队，新元素入队就成为新的队尾元素，删除元素后，其后继元素成为新的队首元素。 出队出队进队进队 A

13、1 A2 A3 A4AN-1 ANF（队头）（队头）R（队尾）（队尾）const maxn=xxxx; /队列的最大长度var q:array1.maxn of qtype; /队列 front,rear:1.maxn; /队首指针和队尾指针2.队列的基本操作1）队列的初始化或置空将队首指针和队尾指针皆置为0。 procedure init； front:=0; rear:=0 end；f r 0 1 2 3 2）入队add(x)，也称进队 首先判断队列q是否已满，若未满，则后移队尾指针，并在队列的尾端插入元素x。 procedure add(x:qtype)； begin if rear=m

14、axn /队满 then writeln (queue full!); halt end else begin rear:=rear+1； /后移队尾指针 qrear:=x； end； end； Xrf3）出队del 首先判断队列q是否已空，若未空，则后移队首指针，并取出队列q的队首元素。 function del； begin if front=rear /队空 then writeln (queue empty!) ; halt end else begin front:=front+1; /后移队首指针 del:=qfront； /取出队首元素 end; end； B C Dfr小练习1

15、. 已知队列(13，2，11，34，41，77，5，7，18， 26，15)，第一个进入队列的元素是13，则第五个出队列的元素是（ ）。A） 5 B） 41 C） 77 D） 13 E） 18 小练习2. 设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ ）。 A）2 B）3 C）4 D）53.队列的溢出与假溢出3.队列的假溢出 由于队列只能在一端插入，在另一端删除，因此随着入队及出队运算的不断进行，就会出现一种有

16、别于栈的情形：队列在数组中不断地向队尾方向移动，而在队首的前面产生一片不能利用的空闲存储区，最后会导致当尾指针指向数组最后一个位置（即r=max）而不能再加入元素时，存储空间的前部却有一片存储区无端浪费，这种现象称为“假溢出”。01234567a5a6a7a8frontrear克服假溢出的两种方法 一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的。 另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到max地址后，下一个地址就“翻转”为。在结构上采用这种技巧来存储的队列称为循环队列。4.循环队列若队列若队列Q Q为空，则返回值为空，则返回值truetrue，否则返

17、回，否则返回值值falsefalse。 function qempty(Q:equeue):Boolean;function qempty(Q:equeue):Boolean;beginbeginqempty:=(front=rear)qempty:=(front=rear)end;end;4.循环队列，判断队空若队列满，则返回值若队列满，则返回值truetrue，否则返回值，否则返回值falsefalse。为了区分队列空和队列满，改用。为了区分队列空和队列满，改用“队尾指针追上队首指针队尾指针追上队首指针” ” 这一特征作这一特征作为队列满标志。为队列满标志。 function qfull(

18、Q:equeue):Boolean;function qfull(Q:equeue):Boolean;beginbeginqfull:=(rear+1) mod maxn=front);qfull:=(rear+1) mod maxn=front);end;end;4.循环队列，判断队满若队列若队列Q Q不满时，把元素不满时，把元素X X插入到队列插入到队列Q Q的队尾，否则返回信息的队尾，否则返回信息“Overflow”Overflow”procedure add(var Q:equeue;X:elemtype);procedure add(var Q:equeue;X:elemtype);

19、beginbegin if qfull(Q) then writeln(Overflow) if qfull(Q) then writeln(Overflow) else begin else begin rear:= rear:=( (rear+1rear+1) ) mod maxn; mod maxn; Q rear:=X; Q rear:=X; end endend;end;4.循环队列，元素进队假设在周末舞会上，男士们和女士们进入假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定男

20、队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对舞曲。现要求写一个程序，模拟上述舞伴配对问题。问题。输入：第一行两队的人数输入：第一行两队的人数 第二行舞曲的数目第二行舞曲的数目5.队列的应用举例设计两个队列分别存放男士和女士。每对跳舞设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。的人一旦跳完后就回到队尾等待下次被选。如如m=3 n=2 k=6m=3 n=2 k=6A1 2

21、3 1 2 31 2 1 2 1 2BF1R1F2R2const max=10000;var a,b:array1.max of integer; m,n,k1,k,i,f1,r1,f2,r2:integer;begin readln(m，n);for i:=1 to m do ai:=i; for i:=1 to n do bi:=i;readln(k); k1:=1; f1:=1;r1:=m;f2:=1;r2:=n;repeat writeln(af1:3, ,bf1:3); r1:=r1+1;ar1:=af1; f1:=f1+1 ; r2:=r2+1;br2:=bf2; f2:=f2+1

22、; k1:=k1+1; until k1k end.现将上面的路线图，按记录结构存储如下现将上面的路线图，按记录结构存储如下 ： 例例2. 2. 写出下图从入口（写出下图从入口（1 1）到出口（）到出口（1717）的可行路）的可行路线图中，数字标号表示关卡：线图中，数字标号表示关卡：5.队列的应用举例(17)(16)(19)(18)(1)(17)(16)(19)(18)(1)开始开始 I：=1 ； WHILE NOI 17 DO I:=I+1 ; REPEAT WRITE(,NOI,); WRITE(); I:=PREI ; UNTIL I=0；请设计一种能从存储数据中求出从入口到请设计一种能

23、从存储数据中求出从入口到出口经过最少关卡路径的算法。出口经过最少关卡路径的算法。 栈、队列属于线性结构。在这种结构中，不管其存储方栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关线性关系系，即每一个数据元素通常只有一个前驱（除第一个元素外），即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。和一个后继（除最后一个元素外）。 但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数至少存在一个结点（数据元素）有多于一个前驱或

24、后继的数据结构称为非线性结构。据元素）有多于一个前驱或后继的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种： 树树 图图线性结构小结v0v3v1v6v2v4v5三、树 树的概念 树的表示方法和存储结构 二叉树的概念 二叉树的存储结构 二叉树的遍历 二叉树的应用堆排序 哈夫曼树及其应用1）树的定义）树的定义 树是一种常见的非线性的数据结构。树的递归定义如树是一种常见的非线性的数据结构。树的递归定义如下：下： 树是树是n(n0)个结点的有限集，这个集合满足以下条件：个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结有且仅有一个结点没有前驱（父亲结点），该

25、结点称为树的根；点称为树的根； 除根外，其余的每个结点都有且仅有一个前驱；除根外，其余的每个结点都有且仅有一个前驱； 除根外，每一个结点都通过唯一的路径连到根上除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；的后继（儿子结点）；由上述定义可知，树结构没有封闭的回路。由上述定义可知，树结构没有封闭的回路。 1.树的概念根结点：根结点：没有父亲的结点。没有父亲的结点。在树中有且仅有一个根结点。分

26、支结点：分支结点：除根结点外，有除根结点外，有孩子的结点称为分支结点孩子的结点称为分支结点。b，c，x，t，d，i。分支结点亦是分支结点亦是其子树的根；其子树的根；叶结点：叶结点：没有孩子的结点称没有孩子的结点称为树叶为树叶。w，h，e，f，s，m，o，n，j，u为叶结点。根结点到每一个分支结点或叶根结点到每一个分支结点或叶结点的路径是唯一的。结点的路径是唯一的。从根r到结点i的唯一路径为rcti。2）结点的分类 结点的度：结点的度：一个结点的子树数目称为该结点的度一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为所有

27、树叶的度为0 0。 树的度：树的度：所有结点中最大的度称为该树的度所有结点中最大的度称为该树的度( (宽度）宽度）。图中树的度为3。3）树的度树是分层次的。树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。 树中最大的层次称为树的深度，亦称高度树中最大的层次称为树的深度，亦称高度。图中树的深度为5。4）树的高度（深度）1 1）树的表示方法）树的表示方法 树的表示方法一般有两种： 自然界的树形表示法：自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般

28、用于分析问题。2.树的表示方法和存储结构 广义表方法：广义表方法： 先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式（r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）（表示结束）静态的记录数组。所有结点存储在一个数组中，数组元素为静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为记录类型，包括数据域和长度为n(n n(n 为树的度为树的度) )的数组，分别存的数组，分别存储该结点的每

29、一个儿子的下标储该结点的每一个儿子的下标Const Const n=n=树的度；树的度；max=max=结点数的上限；结点数的上限； Type Type node=record node=record 结点类型结点类型 data data：datatypedatatype； 数据域数据域 ch ch：array1n of integerarray1n of integer； 指向各儿子的下标指向各儿子的下标 end end；Treetype=array1.maxof nodeTreetype=array1.maxof node； Var treeVar tree：treetypetreetyp

30、e；2）树的存储结构例下图的树，其记录数组如下。由于未规定同层结点的次序，因此每个结例下图的树，其记录数组如下。由于未规定同层结点的次序，因此每个结点儿子的下标序列（点儿子的下标序列（Treei.chTreei.ch）任意。其中）任意。其中Treei.chj=0Treei.chj=0说明结点说明结点i i的第的第j j个儿子不存在。个儿子不存在。( (编号按层编号编号按层编号) ) 二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。1 1、二叉树的递归定义和基本形态、二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它

31、或者为空，或者满足二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：以下条件：有一个特定的结点称为根；有一个特定的结点称为根；余下的结点分为互不相交的子集余下的结点分为互不相交的子集L L和和R R，其中，其中L L是根的左子树；是根的左子树；R R是根的右子树；是根的右子树；L L和和R R又是二叉树；又是二叉树；？ 二叉树是不是树？二叉树二叉树是不是树？二叉树树？树？3.二叉树的概念由上述定义可以看出，二叉树和树是两个不同由上述定义可以看出，二叉树和树是两个不同的概念的概念树的每一个结点可以有任意多个，而二叉树树的每一个结点可以有任意多个，而二叉树中每个结点的后继不能超过中每个结

32、点的后继不能超过2 2；树的子树可以不分次序（除有序树外）；而树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。点的左后件为左儿子，右后件为右儿子。1）二叉树的基本形态前面引入的有关树的一些基本术语对二叉树仍然适用。下图列出二叉树的五种基本形态：满二叉树：满二叉树： 如果一棵深度为如果一棵深度为K K的二叉树，共有的二叉树，共有2 2K K-1-1个结点，个结点，即第即第I I层有层有2 2I-1I-1的结点的结点，称为满二叉树。(a)完全二叉树：完全二叉树：如果一棵二叉树最多只有最下面两层

33、结点度数如果一棵二叉树最多只有最下面两层结点度数可以小于可以小于2 2，并且最下面一层的结点都集中在该层最左边的若，并且最下面一层的结点都集中在该层最左边的若干位置上，干位置上，则称此二叉树为完全二叉树（例如下图(b)）2）二叉树的特殊形态性质性质1 1：在二叉树的第：在二叉树的第i i（11）层上，最多有）层上，最多有2 2i-1i-1个结点个结点证明证明 数学归纳法证明数学归纳法证明归纳基础归纳基础 i=1 i=1时，有时，有2 2i-1i-1=2=20 0=1,=1,因为第一层只有因为第一层只有一个根结点，所以命题成立。一个根结点，所以命题成立。归纳假设归纳假设 假设对于所有的假设对于所

34、有的j j（1=ji1=j2n2k-1k-1-1-1。但但n n又要满足又要满足 n=2 n=2k k-1-1所以所以2 2k-1k-1-1n=2-1n=2k k-1,-1,即即 2 2k-1k-1=n2=n2k k以以2 2为底取对数得到：为底取对数得到：k-1=log2nk,k-1=log2n=1，它的叶结点数目为：A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1 小练习 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（

35、 ）号位置。 A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2小练习二叉树的遍历是不重复地访问二叉树中的每一个结点。二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。点作其它的处理。 如果用如果用L L、D D、R R分别表示遍历左子树、访问根结点、分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合遍历右子树，限定先左后右的次序，三种组合 DLR DLR、LDRLDR、 LRD LRD这三种遍历规则分别称为这三种遍历规则分别称为先（前）序遍历、

36、中序遍历和后序遍历（以根为标准）先（前）序遍历、中序遍历和后序遍历（以根为标准）。5.二叉树的遍历为了方便叙述，我们以下图为例解释三种遍历规则，我们在写遍历子过程前先定义树结构如下：program bianli;type asdf=record name:char;结点名字 father:integer;父结点信息 left:integer;左孩子信息 right:integer;右孩子信息 end;var l,i,h,a:longint; s:string; t:array1.100 of asdf;5.二叉树的遍历若二叉树为空，则退出。否则 访问处理根结点； 前序遍历左子树； 前序遍历右子

37、树； a b d e h i c f g1）前（先）序遍历 procedure front(i:integer);begin if ti.name# then begin write(ti.name); if ti.left0 then front(ti.left); if ti.right0 then front(ti.right);end;end;2）中序遍历若二叉树为空，则退出；否则 中序遍历左子树； 访问处理根结点； 中序遍历右子树； d b h e i a f c g procedure mid(i:integer);begin if ti.name# then begin if t

38、i.left0 then mid(ti.left); write(ti.name); if ti.right0 then mid(ti.right); end;end;若二叉树为空，则退出；否则 后序遍历左子树； 后序遍历右子树； 访问处理根结点； d h i e b f g c a3）后序遍历 procedure back(i:integer);begin if ti.name# then begin if ti.left0 then back(ti.left); if ti.right0 then back(ti.right); write(ti.name); end;end;遍历二叉树（

39、如下图）有三种规则： 前序遍历：根左子树右子树； 中序遍历：左子树根右子树； 后序遍历：左子树右子树根；4)由遍历顺序确定二叉树的结构【例题】已知二叉树的前序遍历顺序为abcdefg，中序遍历顺序为cbdafeg，请确定后序遍历的顺序。后序遍历为cdbfgeacbdfega 右图是一棵二叉树，它的先序遍历是（ ）。AABDEFC BDBEFACCDFEBCA DABCDEF 一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ ）。 A0 B. 2 C. 4 D. 6小练习 表达式a*(b+c)-d的后缀表达式是： A) abcd*+- B

40、) abc+*d- C) abc*+d- D) -+*abcd 前缀表达式“+ 3 * 2 + 5 12 ” 的值是（ ）。A. 23 B. 25 C. 37 D. 65小练习-*dab+c 堆就是一个关键字序列堆就是一个关键字序列：并且这并且这n个关键字的序列个关键字的序列K1,K2.Kn要满足以下性质要满足以下性质(堆性质堆性质)，就是，就是: KiK2i且且KiK2i+1 或者或者 KiK2i且且KiK2i+1 (正堆正堆)(逆堆逆堆)12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 是正堆是正堆12, 36, 27, 65, 40, 14, 98,

41、81, 73, 55, 49 不是堆不是堆1 2 3 4 5 6 7 8 9 10 116. 二叉树的应用堆排序o 当把这个序列存入一个向量并把它看作是一棵完全二当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时，堆就是这样一棵二叉树：叉树的存储结构时，堆就是这样一棵二叉树：任一非任一非叶结点的关键字均不小于叶结点的关键字均不小于( (或不大于或不大于) )其左右孩子结点其左右孩子结点的关键字。的关键字。1236276549817355403498是堆是堆14不不6. 二叉树的应用堆排序1 2 3 4 5 6 7 89470174642550513堆堆最大值6. 二叉树的应用堆排序

42、897624331510112536497856a) 堆顶元素取最大值堆顶元素取最大值大根堆大根堆b) 堆顶元素取最小值堆顶元素取最小值小根堆小根堆6. 二叉树的应用堆排序 因为堆顶是最大的数，所以当把一个关键字序列排成一个大根堆时，就很容易地找到最大的数，它就在序列的第一个位置上 然后把这个最大的数与最后一个记录交换，这时，最后一个记录就是关键字最大的记录了。 对于剩下的关键字序列，我们仍然把它排成一个大根堆，然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换。这时，在整个序列后面就有了两个有序的关键字(从小到大)。 重复这样的过程，就可以把有序区不断扩大直到全部关键字都进入有序

43、区。直到排序完成。947017464255 0513初始堆初始堆427017469455 0513135517469442 05701) 堆排序的基本思想 无序序列无序序列r1：n构成的完全二叉树。构成的完全二叉树。 从它最后一个非叶子结点（第从它最后一个非叶子结点（第n/2个元素）开始直个元素）开始直到根结点为止，逐步进行到根结点为止，逐步进行调整调整即可将此完全二叉树即可将此完全二叉树构成堆。构成堆。 调整：调整：与其左右子树根结点值比较，取其中大的进与其左右子树根结点值比较，取其中大的进行交换。行交换。2) 堆的构造堆的构造例堆的构造例465513427094 051746 55 13

44、42 94 05 17 707017594421355461 2 3 4 5 6 7 81 2 3 4 5 6 7 8465513704294 0517465513427094 05177017594421355461 2 3 4 5 6 7 8对调对调4217594701355461 2 3 4 5 6 7 8对调对调131346 55 13 42 94 05 17 70堆的构造例堆的构造例465517704294 05134213594701755461 2 3 4 5 6 7 8对调5555对调469417704255 05134213555701794461 2 3 4 5 6 7 8

45、对调4646对调46 55 13 42 94 05 17 70堆的构造例堆的构造例944617704255 05134213555701746941 2 3 4 5 6 7 8对调4646对调947017464255 05134213555461770941 2 3 4 5 6 7 8成堆成堆!46 55 13 42 94 05 17 70堆的构造例堆的构造例465513427094 0517初始无序结点,从42开始调整465513704294 0517将以13为根的子树调整成堆465517704294 0513将以55为根的子树调整成堆46 55 13 42 94 05 17 70堆的构造例

46、堆的构造例469417704255 0513将以46为根的子树调整成堆947017464255 0513成堆堆的构造例堆的构造例 由给定的无序序列构造堆由给定的无序序列构造堆 将堆顶元素与堆中最后一个元素交换将堆顶元素与堆中最后一个元素交换 将最后一个元素从堆中删除将最后一个元素从堆中删除 将余下的元素构成完全二叉树重新调整成堆将余下的元素构成完全二叉树重新调整成堆 反复进行，直到堆空反复进行，直到堆空3) 堆排序的过程堆排序过程示例堆排序过程示例947017464255 0513初始堆初始堆427017469455 0513705517469442 051394与与42交换交换前前7个元素个

47、元素重新建堆重新建堆941355546177042135517469442 0570554617139442 0570054617139442 557070与与13交换交换前前6个元素个元素重新建堆重新建堆55与与05交换交换947054246175513947055421317465堆排序过程示例堆排序过程示例464217139405 5570054217139446 5570421317059446 5570前前5个元素个元素重新建堆重新建堆46与与05交换交换947055461317425前前4个元素个元素重新建堆重新建堆堆排序过程示例堆排序过程示例051317429446 557017

48、1305429446 5570051317429446 557042与与05交换交换947055464217135前前3个元素个元素重新建堆重新建堆17与与05交换交换947055464217135堆排序过程示例堆排序过程示例130517429446 5570051317429446 5570前前2个元素个元素重新建堆重新建堆13与与05交换交换947055464217135堆排序结果堆排序结果堆排序过程示例堆排序过程示例941355546177042947054246175513947055421317465947055461317425947055464217135947055464217

49、135947055464217135第一趟结果第一趟结果:第二趟结果第二趟结果:第三趟结果第三趟结果:第四趟结果第四趟结果:第五趟结果第五趟结果:第六趟结果第六趟结果:第七趟结果第七趟结果:堆排序过程堆排序过程7.哈夫曼树及其应用D E FG HB CA 在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。 在路径上的分支数目被称为路径长度。 带权的路径长度最小的二叉树称为哈夫曼二叉树或最优二叉树。nkkklwWPL11)相关概念 假设有6个权值分别为3，6，9，10，7，11，以这6个权值作为叶子结点的权值可以构造出下面三棵二叉树。 3 6 7 910 112)权值、树形与带

50、权路径长度31110976(b)11103679(c) 这三棵二叉树的带权路径长度分别为： WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117 WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177 WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158（1）将给定的n个权值w1,w2,.,wn作为n个根结点的权值构造一个具有n棵二叉树的森林T1,T2,.,Tn，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值