《清华大学严蔚敏版数据结构考研要点(精华版).docx》由会员分享，可在线阅读，更多相关《清华大学严蔚敏版数据结构考研要点(精华版).docx（21页珍藏版）》请在三一办公上搜索。
1、1、数据(Data)：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataEIement)：是数据的根本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由假设十个数据项(DataItem)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C=7V；B：C,.。数据结构(DataStrUCtUre)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元
2、素之间的逻辑结构有四种根本类型，如图1-3所示。集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。线性结构：结构中的数据元素之间存在一对一的关系。树型结构：结构中的数据元素之间存在一对多的关系。图状结构或网状结构：结构中的数据元素之间存在多对多的关系。2、顺序结构：数据元素存放的地址是连续的：链式结构：数据元素存放的地址是否连续没有要求。数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。3、C语言中用带指针的结构体类型来描述typedefstr
3、uctLnodeEIemTypedata;/*数据域，保存结点的值*/structLnode*next;/*指针域*/LNode;/*结点的类型*/4、循环队列为空：front=rear。循环队列满：(rear+l)%MAX_QUEUE_SIZE=fronto5、性质1，在非空二叉树中，第i层上至多有21个结点(iMl)性质2：深度为k的二叉树至多有2匕1个结点(kl)o性质3:对任何一棵二叉树，假设其叶子结点数为11o,度为2的结点数为n2,那么n0=112+lo一棵深度为k且有2k-l个结点的二叉树称为满二叉树(FUllBinaryTree)0完全二叉树的特点：假设完全二叉树的深度为k,那
4、么所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为/,那么其左子树的最大层次为/或/+Io性质4：n个结点的完全二叉树深度为：IJogznWlo性质5：假设对一棵有n个结点的完全二叉树(深度为g2n+l)的结点按层(从第1层到第UogznjU层)序自左至右进行编号,那么对于编号为i(IWiWn)的结点：假设i=l:那么结点i是二叉树的根，无双亲结点；否那么，假设il,那么其双亲结点编号是Li启。如果2in:那么结点i为叶子结点，无左孩子；否那么，其左孩子结点编号是2i。如果2i+ln:那么结点i无右孩子；否那么，其右孩子结点编号是2i+l.6、线索二叉树：设一棵二
5、叉树有n个结点，那么有n-1条边(指针连线)，而n个结点共有2n个指针域(LChild和RChiId),显然有n+1个空闲指针域未用，那么可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。7、HUffman树：具有n个叶子结点(每个结点的权值为Wi)的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为HUffman树(或称最优树)。8、完全无向图：对于无向图，假设图中顶点数为n,用e表示边的数目，那么e0,n(n-l)2。具有n(n-l)2条边的无向图称为完全无向图。完全有向图：对于有向图，假设图中顶点数为n,用e表示弧的数目，那么ew0,n(n-l)。
6、具有n(n-l)条边的有向图称为完全有向图。生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的nl条边，称为图的生成树关于无向图的生成树的几个结论：1)一棵有n个顶点的生成树有且仅有nl条边；2)如果一个图有n个顶点和小于n-1条边，那么是非连通图：3)如果多于nl条边，那么一定有环：4)有n-1条边的图不一定是生成树。9、最小生成树(MinimUmSPanningTree)：带权连通图中代价最小的生成树称为最小生成树。最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信
7、线路的费用。n个城市之间最多可以建n(n-l)2条线路，如何选择其中的n-1条，使总的建造费用最低？10、工程完成最短时间：从起点到终点的最长路径长度(路径上各活动持续时间之和)。长度最长的路径称为关键路径，关键路径上的活动称为关键活动。关键活动是影响整个工程的关键。5MB7.2甭Rlr6施及工舞桂中住11、查找方法比拟顺序查找折半查找分块查找12、在随机情况下，二叉排序树ASL最大最小两者之间表结构有序表、无序表有序表分块有序表的平均查找长度ASL和蜘(n)(树存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表的深度)是等数量级的。二叉排序树(BinarySOrtTree或Bina
8、rySearChTree)的定义为：二叉排序树或者是空树，或者是满足以下性质的二叉树。(1)：假设左子树不为空，那么左子树上所有结点的值(关键字)都小于根结点的值；(2)：假设右子树不为空，那么右子树上所有结点的值(关键字)都大于根结点的值；(3)：左、右子树都分别是二叉排序树。结论：假设按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。13、平衡二叉树或者是空树，或者是满足以下性质的二叉树。：左子树和右子树深度之差的绝对值不大于1;：左子树和右子树也都是平衡二叉树。平衡因子(BalanCeFaCtor)：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。平衡二叉排序树上
9、进行查找的平均查找长度和m2n是一个数量级的，平均时间复杂度为0(2n)四种平衡化旋转，其正确性容易由遍历所得中序序列不变来证明。并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以a为根结点的平衡二叉排序树的深度相同。所以，在平衡二叉排序树上因插入结点而失衡，仅需对失衡子树做平衡化旋转处理。14、一棵m阶B一树，或者是空树，或者是满足以下性质的m叉树：根结点或者是叶子，或者至少有两棵子树，至多有m棵子树；除根结点外，所有非终端结点至少有lml棵子树，至多有m棵子树；所有叶子结点都在树的同一层上；(4)每个结点应包含如下信息：(n,Ao，Ki,Ai，
10、K2，A?,，KA)其中Ki(lin)是关键字，且KiK+(lin-l);Ai(i=O,1,.,n)为指向孩子结点的指针,且Ajr所指向的子树中所有结点的关键字都小于Ki,Ai所指向的子树中所有结点的关键字都大于Ki;n是结点中关键字的个数，且Lm2,lnm-l,n+1为子树的棵数。根据m阶B_树的定义,第一层上至少有1个结点,第二层上至少有2个结点;除根结点外,所有非终端结点至少有m/2旗子树，,第h层上至少有Tm/ZF个结点。在这些结点中,根结点至少包含1个关键字,其它结点至少包含m/2k个关键字,&s=m2l那么总的关键字数目n满足,f(7耍，、J22”因此有：hl+s(n+l)Z)=l
11、+m21(n+l)Z)即在含有n个关键字的B举上进行查找时,从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+m(n+l)启)o15、m阶B树。它与B_树的主要不同是叶子结点中存储记录。在树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字，用来界定某一关键字的记录所在的子树。一棵)阶夕树与m阶B一树的主要差异是：(1)假设一个结点有n棵子树，那么必含有n个关键字；所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接；所有的非叶子结点可以看成是索引的局部，结点中只含有其子树的根结点中的最大(或最小)关键字。
12、16、哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数是一种映象,是从关键字空间到存储地址空间的一种映象。可写成:addr(ai)=H(ki),其中i是表中一个元素，addr(ai)是ai的地址，K是ai的关键字。哈希表:应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。哈希查找(又叫散列查找)：利用哈希函数进行查找的过程叫哈希查找。例1.设散列表长为7,记录关键字组为：15,14,28,26,56,23,散列函数:H(key)=keyMOD7,冲突处理采用线性探测法。解:H(15)=15MOD7=1H(14)=14M
13、OD7=0H(28)=28MOD7=0冲突H1(28)=l又冲突Hz(28)=2H(26)=26MOD7=5H(56)=56MOD7=0冲突H1(56)=l又冲突H2(56)=2又冲突H3(56)=3H(23)=23MOD7=2冲突H1(23)=3又冲突H3(23)=4次中均入的记录败各种散列函数所构造的散列表的ASl如下:“M土”J17、排序的稳定性假设记录序列中有两个或两个以上关键字相等的记录：Ki=Kj(ij,i,j=l,2,.n),且在排序前Ri先于Rj(ij),排序后的记录序列仍然是Ri先于Rj,称排序方法是稳定的，否那么是不稳定的。排序的分类待排序的记录数量不同，排序过程中涉及的存
14、储器的不同，有不同的排序分类。待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序；待排序的记录数太多：所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。18、插入排序采用的是以“玩桥牌者的方法为根底的。即在考察记录Ri之前，设以前的所有记录Ri,R2Rii已排好序，然后将Ri插入到已排好序的诸记录的适当位置。最根本的插入排序是直接插入排序(StraightInsertionSort)o(1)最好情况,假设待排序记录按关键字从小到大排列(正用,算法中的内循环无须执行,那么一趟排序时:关键字比拟次数1次，记录移动次数2次(2)最坏情
15、况:假设待排序记录按关键字从大到小排列(逆用,那么一趟排序时:算法中的内循环体执行a关键字比拟次数i次,记录移动次数i+T.一般地,认为待排序的记录可能出现的各种排列的概率相同,那么取以上两种情况的平均值,作为排序的关键字比拟次数和记录移动次数,约为标4那么复杂度为。(四。算法实现voidstraightJnsert_sort(Sqlist*L)intij;for(i=2;ilength;i+)L-RO=L-Rijj=i-l;*设置哨兵*/while(LT(L-R0.key,L-Rj.key)L-Ri+l=L-Rj;H*查找插入位置*/1.-RU+1=L-RO;/*插入到相应位置*/)=步*菽
16、入排序当将待排序的记录RUl插入到已排好序的记录子表RlTill中时,由于RLR2,Rc已排好序,那么查找插入位置可以用“折半查找，实现,那么直接插入排序就变成为折半插入排序。从时间上比拟,折半插入排序仅仅减少了关键字的比拟次数,却没有减少记录的移动次数,故时间复杂度仍然为。排序例如：设有一组关键字30,13,70,85,39,42,6,20,采用折半插入排序方法排序的过程1=工30)37085394NG20i=N工3,703942GNOi=7NoI=20339f427020Iiuli三li=820cf13T3?394270SS)20Iowmi4N708SNolowI11miB三I=8NO53
17、NO30394N70ION匕斤十用;八月RYjJ才呈算法实现voidBinaryJnsert_sort(Sqlist*L)inti,j,low,high,mid;for(i=2;ilength;i+)L-RO=L-Ri;*设置哨兵*/Iow=I;high=i-l;while(lowRO.key,L-Rmid.key)high=mid-l;elselow=mid+l;)*查找插入位置*/for(j=i-l;j=hgh+l;j-)1.-Rj+l=L-Rj;1.-Rh!gh+l=L-RO;*插入到相应位置*/=2路插入排序排序例如：设有初始关键字集合49,38,65,13,97,27,76,采用2-
18、路插入排序的过程first图10-32-路插入排序过程例：设有关键字集合49,38,65,97,76,13,27,49,采用表插入排序的过程=希尔排序(ShellSort,又称缩小增量法)是一种分组插入排序方法。排序例如设有10个待排序的记录，关健字分别为9,13,8,2,5,玛7,1,15,11,增量序列是5,3,1,希尔排序的过程：算法实现先给出一趟希尔排序的算法，类似直接插入排序。voidshell-pass(Sqlist*L,intd)/*对顺序表L进行一趟希尔排序，增量为d*/ntj,k；for(j=d+l;jlength;j+)L-R0=L-RU;/*设置监视哨兵*/k=j-d;w
19、hile(k088LT(L-R0.keL-Rk.key)L-Rk+d=L-Rk;k=k-d;1.-Rk+j=L-RO;)voidshelI-sort(Sqlist*L,intdk,intt)/*按增量序列dkO.t-l,对顺序表L进行希尔排序*/intm;for(m=0;m=t;m+)ShILPaSs(L,dkm);)=冒泡排序排序例如：设有9个待排序的记录，关键字分别为23,38,22,45,里,67,31,15,41,冒泡排序的过程：voidBubble-Sort(Sqlist*L)intj,k,flag;for(j=0;jlength;j+)*共有n-1趟排序*/flag=TRUE;fo
20、r(k=l;klength-j;k+)*一趟排序*/if(LT(L-Rk+l.keL-Rk.key)Hag=FALSE;L-R0=L-Rk;1.-Rk=L-Rk+l;1.-Rk+l=L-RO;)if(flag=TRUE)break;)算法分析：时间复杂度：最好情况(正序)：比拟次数：nl；移动次数：0；1-.1BBl比岐次敬.2=2年七N力次数.n-13RO=L-Ri;*R0作为临时单元和哨兵*/dowhile(LQ(L-R0.key,L-Rj.key)&(ji)j-；if(j0L-Ri=L-Rj;i+;while(LQ(L-Ri.key,L-RO.key)&(ji)i+;if(ji)L-Rj
21、=L-Ri;H)while(i!=j);*i=j时退出扫描*/1.-Ri=L-RO;return(i);)递归算法voidquick-Sort(Sqlist*L,intlow,inthigh)intk;if(lowhigh)k=quick_one_pass(Ulow,high);quick_Sort(L,low,k-l);quick-Sort(Lzk+l,high);*序列分为两局部后分别对每个子序列排序*/)非递归算法#defineMAX_STACK100voidquick-Sort(Sqlist*L,intlow,inthigh)intk,stackMAX_S7ACK,top=0;dowh
22、ile(lowigh)k=quick_one_pass(LJow,high);stack+top=high;stack+top=k+l;*第二个子序列的上,下界分别入栈*/high=k-l;)if(top!=0)low=stacktop-;high=stacktop-;while(topl=0&lowhigh);)简单项选择择排序(SimPIeSeIeCtionSort,又称为直接选择排序)排序例如例：设有关键字序列为：7,4,-2,19,13,6,直接选择排序的过程算法实现voidsimple_selection_sort(Sqlist*L)intm,n,k;for(m=l;mlength;
23、m+)k=m;for(n=m+l;nlength;n+)if(L(L-Rn.key,L-Rk.key)k=n;if (k!=m)/*记录交换*/L-RO=L-Rm;L-Rm=L-Rk;1.-Rk=L-RO;)算法分析整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为nl越；内循环控制每一趟的排序。. (n-i aIP0次数1进行第i趟排序时，关键字的比拟次数为n-i,那么：二时间复杂度是：T(n)=O(n2)空间复杂度是，S(n)=O(l)从排序的稳定性来看，直接选择排序是不稳定的。堆的定义是n个元素的序列H=k,k2,.kn),满足：堆的性质堆是一棵采用顺序存储结构的完全二
24、叉树,k是根结点;堆的根结点是关键字序列中的最小(或最为值,分别称为小(或为根堆;从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的;堆中的任一子树也是堆。利用堆顶记录的关键字值最小(或最大)的性质,从当前待排序的记录中依次选取关键字最小(或最大)的记录,就可以实现对数据记录的排序,这种排序方法称为堆排序。堆排序思想对一组待排序的记录，按堆的定义建立堆；将堆顶记录和最后一个记录交换位置，那么前n-1个记录是无序的，而最后一个记录是有序的；堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交
25、换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区；重复上述步骤，直到全部记录排好序为止。结论：排序过程中，假设采用小根堆，排序后得到的是非递减序列；假设采用大根堆，排序后得到的是非递增序列。堆排序算法实现堆的根结点是关键字最小的记录，输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的左、右子树都是堆，那么进行一次筛选就可以成为堆。voidHeap-Sort(Sqlist*H)intj;for(j=H-length2;j0;j-)Heap-adjust(Hzj,H-length);*初始建堆*/for(j=H-length2;j=l;j-)H-RO=H-R1;H-R1=H-R
26、O；H-Rj=H-RO;/*堆顶与最后一个交换*/Heap-adjust(H,lzj-l);)堆排序的比拟次数的数量级为：T(n)=0(n2n);而附加空间就是交换时所用的临时空间，故空间复杂度为：S(n)=O(l)=归并(Merging)：是指将两个或两个以上的有序序列合并成一个有序序列。假设采用线性表(无论是那种存储结构)易于实现，其时间复杂度为0(m+n)。归并排序的算法开始归并时,每个记录是长度为1的有序子序列,对这些有序子序列逐趟归并,每一趟归并后有序子序列的长度均扩大一倍;当有序子序列的长度与整个记录序列长度相等时,整个记录序列就成为有序序列。算法是:voidMerge_sort(
27、Sqlist*L,RecTypeDR)intd=l;while(dlength)Merge-pass(L-R,DR,d,L-length);Merge-pass(DR,L-R,2*d,L-length);d=4*d;具有n个待排序记录的归并次数是晚2。,而一趟归并的时间复杂度为08),那么整个归并排序的时间复杂度无论是最好还是最坏情况均为OS蜘2坨。在排序过程中,使用了辅助向量DR,大小与待排序记录空间相同,那么空间复杂度为08)。归并排序是稳定的。=各种内部排序的比拟：各种内部排序按所采用的根本思想(策略)可分为，插入排序、交换排序、选择排序、归并排序和基数排序，它们的根本策略分别是：1插入
28、排序：依次将无序序列中的一个记录，按关键字值的大小插入到已排好序一个子序列的适当位置，直到所有的记录都插入为止。具体的方法有：直接插入、表插入、2.路插入和SheIl排序。2交换排序：对于待排序记录序列中的记录，两两比拟记录的关键字，并对反序的两个记录进行交换，直到整个序列中没有反序的记录偶对为止。具体的方法有：冒泡排序、快速排序。3选择排序：不断地从待排序的记录序列中选取关键字最小的记录，放在已排好序的序列的最后，直到所有记录都被选取为止。具体的方法有：简单项选择择排序、堆排序。4归并排序：利用“归并”技术不断地对待排序记录序列中的有序子序列进行合并，直到合并为一个有序序列为止。5基数排序：
29、按待排序记录的关键字的组成成分(“位”)从低到高(或从高到低)进行。每次是按记录关键字某一“位的值将所有记录分配到相应的桶中，再按桶的编号依次将记录进行收集，最后得到一个有序序列。各种内部排序方法的性能比拟如下表。文件的根本概念数据项(Item或field)：数据文件中最小的根本单位，反映实体某一方面的特征一属性的数据表示。记录(ReCOrd)：一个实体的所有数据项的集合。用来标识一个记录的数据项集合(一个或多个)称为关键字项(Key),关键字项的值称为关键字；能唯一标识一个记录的关键字称为主关键字(PrimaryKey),其它的关键字称为次关键字(SeCondaryKey)。利用外存对数据文
30、件进行排序称为外部排序。算法局部:素数的判断算法。Voidprime(intn)*n是一个正整数*/inti=2;while(n%i)!=0&i*1.0sqrt(n)Printf(&d是一个素数n”,n);elsePrintf(&d不是一个素数n,n);)冒泡排序法。Voidbubble_sort(intaintn)change=false;for(i=n-l;Change=TURE;il&change;-i)for(j=0;jaU+l)ajaj+l;Change=TURE;-最好情况：。次最坏情况：l+2+3+n-l=n(n-l)2-平均时间复杂度为：0(n2)算法说明，算法中Pa，Pb分别
31、是待考察的两个链表的当前结点,PC是合并过程中合并的链表的最后一个结点。1.Node*Merge_LinkList(LNode*La,LNode*Lb)/*合并以LaJb为头结点的两个有序单链表*/LNode*Lc,*pa,*pb,*pc,*ptr;1.c=La;pc=La;pa=La-next;pb=Lb-next;while(pa!=NULL&pb=NLL)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;/*将Pa所指的结点合并，Pa指向下一个结点*/if(pa-datapb-data)pc-next=pb;pc=pb;pb=pb-net;/*将Pa所
32、指的结点合并，Pa指向下一个结点*/if(pa-data=pb-data)pc-next=pa;pc=pa;pa=pa-next;ptr=pb;pb=pb-next;free(ptr);/*将Pa所指的结点合并，Pb所指结点删除*/if(pa!=NULL)pc-next=pa;elsepc-next=pb;/*将剩余的结点链上*/free(Lb);return(Lc);采用静态顺序栈方式实现voidconversion(intn,intd)/*将十进制整数N转换为d(2或8)进制数*/SqStackS;intk,*e;S=lnit-Stack();while(n0)k=n%d;push(S,k
33、);n=nd;/*求出所有的余数，进栈*/while(S.top!=0)/*栈不空时出栈，输出*/Pop(S,e);Printf(%ld,*e);2求转置矩阵的算法如下：voidTransMatri(TMatria,TMatrixb)intp,q,col;b.rn=a;b=a.rn;b.tn=a.tn;*置三元组表b.data的行、列数和非O元素个数*/if(b.tn=O)printf(wTheMatrixA=0nw);elseq=o；for(col=l;col=a;col+)*每循环一次找到转置后的一个三元组*/for(p=0;pdata);/*访问根结点*/PreorderTraverse
34、(T-Lchild);PreorderTraverse(T-Rchild);)非递归算法设T是指向二叉树根结点的指针变量,非递归算法是:假设二叉树为空,那么返回;否那么,令p=T;(1)访问P所指向的结点;(2)q=p-Rchild,假设q不为空,那么q进栈;(3)p=p-Lchild,假设P不为空,转(1),否那么转(4卜退栈到P，转(1),直到栈空为止。算法实现：#defineMAX_NODE50voidPreorderTraverse(BTNode*T)BTNode*StackMAX_NODE,*p=L*q;inttop=0;if(T=NULL)Printf(BinaryTreeisEm
35、pty!nw);elsedovisit(p-data);q=p-Rchild;if(q!=NULL)stack+top=q;p=p-Lchild;if(p=NULL)p=stacktop;top-;while(p!=NULL);)=中序遍历的递归算法voidInorderTraverselBTNode*T)if(TI=NULL)lnorderTraverse(T-Lchild);visit(T-data);/*访问根结点*/lnorderTraverse(T-Rchild);)非递归算法设T是指向二叉树根结点的指针变量,非递归算法是:假设二叉树为空,那么返回;否那么,令P=T假设P不为空,P进
36、栈,p=p-Lchildf(2)否那么(即P为空),退栈到p,访问P所指向的结点;(3)p=p-Rchild,转(1)；直到栈空为止。算法实现：#defineMAX_NODE50voidInorderTraversefBTNode*T)BTNode*StackMAX_NODE,*p=T;inttop=0,bool=l;if(T=NULL)Printf(BinaryTreeisEmpty!nw);elsedowhile(p!=NULL)stack+top=p;p=p-Lchild;if(top=0)bool=0;elsep=stacktop;top-;visit(p-data);p=p-Rchi
37、ld;while(bool!=0);)=g：递归算法voidPostorderTraverse(BTNode*T)if(TI=NULL)PostorderTraverse(T-Lchild);PostorderTraverse(T-Rchild);visit(T-data);*访问根结点*/)非递归算法在后序遍历中,根结点是最后被访问的。因此,在遍历过程中,当搜索指针指向某一根结点时,不能立即访问,而要先遍历其左子树,此时根结点进栈。当其左子树遍历完后再搜索到该根结点时,还是不能访问,还得遍历其右子树。所以,此根结点还需再次进栈,当其右子树遍历完后再退栈到到该根结点时,才能被访问。因此,设立一
38、个状态标志变量tagt0；结点暂不能访问1;结点可以被访问其次,设两个堆栈s】、S2,51保存结点,Sz保存结点的状态标志变量tag。Sl和Sz共用一个栈顶指针。设T是指向根结点的指针变量,非递归算法是:假设二叉树为空,那么返回;否那么,令p=T;(1)第一次经过根结点P，不访问2P进栈5T,tag赋值。,进栈S2,p=p-Lchild。(2)假设P不为空,转(1),否那么,取状态标志值tagi(3)假设tag=(h对栈51,不访问,不出栈;修改S2栈顶元素值(tag赋值1),取SI栈顶元素的右子树,SPp=Sltop-Rchild,相1)；假设tag=l*Sl退栈,访问该结点;直到栈空为止。
39、算法实现:#defineMAX_NODE50voidPostorderTraverselBTNode*T)BTNode*SiMAX_NODE,*p=T;intS2MAX_N0DE,top=。，bool=l;if(T=NULL)Printf(BinaryTreeisEmpty!nw);elsedowhile(p!=NULL)Sl+top=p;S2top=0;p=p-Lchild;)if(top=0)bool=0;elseif(S2top=O)p=Stop-Rchild;S2t0p=l;elsep=Stop;top-;visit(p-data);p=NULL;*使循环继续进行而不至于死循环*/while(bool!=0);)=
