数据结构重要算法

版权：wuliming_sc修改：Air_sky说明：本资料是Air_sky修改wuliming_sc整理的数据结构材料.仅供各位考研师弟师妹们方便之用，如有什么疑议，请通知Air_sky(iceman0481)本人即删除！1、栈的基本操作：编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。void reverse( Stack *s ) Stack s1, s2; ElemType x; InitStack( s1 ); InitStack( s1 ); /将s栈中的内容转移到s1栈中 while( StackEmpty( s ) != 0 ) Pop( s, x );Push( s1, x ); /将s1栈中的内容转移到s2栈中 while( StackEmpty( s1 ) != 0 ) Pop( s1, x );Push( s2, x ); /将s2栈中的内容转移到s栈中 while( StackEmpty( s2 ) != 0 ) Pop( s2, x );Push( s, x ); 解题思路：假定栈采用顺序结构。利用两个临时的栈s1，s2。先将s栈中的内容转移到s1栈中；再将s1栈中内容转移到s2栈中；最后将s2栈中的内容转移到s栈中，这样s栈中的内容就被逆转了。2、利用两个栈s1、s2模拟一个队列是，如何用栈的运算来实现该队列的运算： EnQueue：插入一个元素； DeQueue：删除一个元素； QueueEmpty：判断队列为空；解题思路：由于栈的特点是先进后出，为了模拟先进先出的队列，必须有两个栈，一个栈s1用于插入元素，另一个栈s2用于删除元素，每次删除元素时应将前一个栈的所有元素出栈并压栈到第二个栈中，这样才能达到模拟队列的效果。int EnQueue( Stack *s1, Stack *s2, ElemType x ) if( s1-top = MaxSize ) /队列上溢 return -1; else Push( s1, x ); return 0; int DeQueue( Stack *s1, Stack *s2, ElemType *x ) ElemType y; while( StackEmpty(s1) != 0 ) /将s1的所有元素退栈进入s2中 Pop( s1, y ); Push( s2, y ); Pop( s2, x ); /将s2的栈顶元素退栈并赋给x while( StackEmpty(s2) != 0 ) /将s2余下的元素退栈后进入s1中 Pop( s2, y ); Push( s1, y ); 3、共享存储空间的栈：有两个栈s1和s2共享存储空间c1m，其中的一个栈s1的栈底设在c1处，另一个栈s2的栈底设在cm处。分别编写s1和s2的进栈push(i, x)、退栈pop(i)和设置栈空setnull(i)的函数，其中i=1、2，分别表示对栈1或者栈2进行设置（注意：仅当整个空间c1m占满时才产生溢出）。top1 = 1;top2 = m;.int push( ElemType x, int i )/上溢出 if( top1 = top2 - 1 ) return -1;/对第一个栈进行进栈操作else if( i = 1 ) top1+;ctop1 = x;/对第二个栈进行进栈操作else top2-;ctop2 = x;return 0;int pop( ElemType *x, int i )/对第一个栈进行出栈操作 if( i = 1 ) if( top1 = 0 )/栈1下溢出 return -1;else x = ctop1;top1-;/对第二个栈进行出栈操作else if( top2 = m + 1 )/栈2下溢出 return -1;else x = ctop2;top2+;return 0;void setnull( int i ) if( i = 1 ) top1 = 1;else top2 = m + 1;补充说明：top1是s1的栈指针；top2是s2的栈指针，当top2top11时出现上溢出，当top10时出现下溢出，当top2m1时出现下溢出。4、假设一个算数表达式中包含圆括号、方括号、花括号三种类型的括号。编写一个判别表达式中括号是否正确配对的函数correct（exp, tag）；其中exp为字符串类型的变量，表示被判别的表达式，tag为布尔型变量。解题思路：利用一个栈进行判断，将(、进栈，当遇到)、或时，检查当前栈顶元素是否是对应的（、，若是则退栈，否则表示不配对。当整个算数表达式检查完毕时栈为空，表示括号正确配对，否则不配对。5、编写一个算法，利用队列和栈的基本运算将指定队列中的内容进行逆转。解题思路：假设是否循环顺序队列。建立一个临时的栈，将指定队列中的所有元素出队列到临时的栈中，然后再将栈中的所有元素出栈并入队列，这样队列中的内容就发生了逆转6、编写一个算法，利用队列的基本运算返回指定队列中的最后一个元素。解题思路：假设是循环顺序队列，没有取对尾元素的基本运算。建立一个临时的队列tmpqu，将指定队列qu中的所有元素出队并入队到tmpqu对中，这样qu为空，再将队列tmpqu中的所有元素出队并入队到qu中，这是最后入队的一个元素即为所求。7、编写一个算法，利用栈的基本运算返回指定栈中栈底元素。解题思路：假定栈采用顺序结构。先退栈s中的所有元素，利用一个临时的栈存放从s栈中退出来的元素，最后的一个元素即为所要返回的元素。然后将临时栈中的元素逐一出栈，压栈到s中，恢复到s栈中原来的顺序。 串、稀疏矩阵、广义表串的常考知识点：利用串的几个基本操作解决其它的问题：串的基本操作有：求串的长度、串的赋值、串的连接、求指定位置的子串、返回子串在主串中的起始位置、判断串是否等价、串的比较串的模式匹配：很少考察该问题，最多考察一下求nextjhe nextvalj的值模式匹配待参照教材进一步总结稀疏矩阵常考知识点：对称矩阵的压缩存储；上三角、下三角矩阵的压缩存储；对角矩阵；多维数组；以上主要考察下标的变换关系。广义表常考知识点：广义表的定义；广义表的取头取尾；广义表的做图（头尾表示法、孩子兄弟表示法）。字符串的模式匹配算法古典的模式匹配算法：int Index( S, T, pos )i = pos;j = 1;while( i = length( S ) & j length( T ) ) return i length( T );else return 0;补充说明：该算法用计数指针i和j指示主串S和模式串T中当前正在比较的字符位置，算法的时间复杂度是O(n*m)，其主串的指针i存在回溯。但是在一般的情况下，其实际的执行时间近似于O(n+m)，所以至今仍被采用。补充说明：该算法用计数指针i和j指示主串S和模式串T中当前正在比较的字符位置，算法的时间复杂度是O(n*m)，其主串的指针i存在回溯。但是在一般的情况下，其实际的执行时间近似于O(n+m)，所以至今仍被采用。模式匹配的一种改进算法：KMP算法KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程中出现字符比较不相等时，不需要回溯i指针，而是利用已经得到得“部分匹配”的结果将模式向右“滑动”尽可能远得一段距离后，继续进行比较。假设主串为S1S2S3Sn，模式串为P1P2P3Pn。当主串中的第i个字符与模式串中的j个字符不相等时，主串中的第i个字符（i指针不回溯）应该和模式串中的那个字符再比较？假设此时应与模式串的第K（K K满足下列关系式： P1P2P3Pk1S i-k+1S i-k+2Si-k+3Si-1 （1）而已经得到的“部分匹配”的结果是（匹配的模式串中从后向前取k1个字符）： Pj-k+1Pj-k+2Pj-k+3Pj1S i-k+1S i-k+2Si-k+3Si-1 （2）从而个得到下列等式： P1P2P3Pk1Pj-k+1Pj-k+2Pj-k+3Pj1 （3） 反之，若模式串中存在满足（3）的两个子串，则在匹配过程中，当主串的第i个字符与模式串的第j个字符比较不等时，仅需将模式串向右滑动至模式串中第k个字符和主串中第i个字符对齐，此时，模式中头K1个字符的子串P1P2P3Pk1必定与主串中第i个字符之前的长度为K1的子串S i-k+1S i-k+2Si-k+3Si-1相等，由此，匹配仅需从模式中第k个字符与主串的第i个字符开始继续往下比较。若令nextj = k，则nextj表明当模式中第j个字符与主串中相应字符比较失配时，在模式中需要重新和主串中该字符进行比较的字符的位置。由此引入模式串的next函数的定义： 0 当j = 1时nextj Max k | 1 K j 且P1P2Pk1Pj-k+1Pj-k+2Pj1 当此集合不为空时 1 其他情况时KMP算法如下所示：int Index_KMP( SString S, SString T, int pos )i = pos;j = 1;While( i = length( S ) & j length( T ) ) return i length( T );else return 0;说明：在匹配的过程中产生失配时，指针i不变，指针j退回到nextj所示的位置上重新进行比较，并且当指针j退至零时，指针i和j需同时增加1。即若主串的第i个字符和模式串的第1个字符不等，应从主串的第i1个字符起重新进行匹配。KMP算法中next以及nextval函数值的求解void GetNext( SString t, int next )/*求模式t的next值并存入next数组中*/ int i = 1, j = 0;next1 = 0;while( i length(t) ) if( j = 0 | ti = tj ) i+; j+;nexti = j; else j = nextj;void GetNextval( SString t, int nextval )/*求模式t的nextval值并存入nextval数组中*/ int i = 1, j = 0;nextval1 = 0;while( i length(t) ) if( j = 0 | ti = tj ) i+; j+;if(ti = tj ) nextvali = nextvalj;else nextvali = j; else j = nextvalj;举例说明怎样求得nextj和nextvalj的值求模式串abcaabbcabcaabdab的next数组和nextval数组的值：- j . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17- . a b c a a b b c a b c a a b d a b nextj . 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2nextvalj . 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1-下面用比较直观的方法求得nextj和nextvalj的值：nextj的求法：用公式表示即为： 0 当j = 1时nextj Max k | 1 K j 且P1P2Pk1Pj-k+1Pj-k+2Pj1 当此集合不为空时 1 其他情况时用平实的话表述，就是说第一个字符的nextj为0，第二个字符的nextj为1。剩下字符的nextj按下面的规则确定：取从开始到j前面一个字符为止的子串，然后从这个子串的开始和末尾查找两个完全相同的子串，这两个子串应满足以下条件：前面的子串必须从P1开始、后面的子串必须以Pj1结尾，找到的两个子串必须是能找到的最长的相等的子串。然后以找到的子串的长度值加上1，即为其nextj的值（如果从0开始编号，则不加1）。以j 15的字符为例说明：在从1到14的这一个子串中，从头到尾所能找到的最长的匹配的子串是abcaab,所以next15 =7;同时在这14个字符中再也找不到比abcaab更长的相等的子串了。nextvalj的求法(依据个人理解)得出nextvalj的值要以nextj为基础。nextvalj是在nextj的基础上推出来的。以j12的字符为例说明： next12=4,而s12和s4字符相同，这是next4=1,而s1和s12字符也相同，再往前则不能递推了。所以nextval12就取next1的值0。以j=14的字符为例说明： next14=6,s14和s6相同；这时next6=2,而s2和s14也相同；next2=1,但s1和s14不同，所以nextval14取最后一个其字符和它相同的s2的next值1。字符串的一些比较典型的算法：1、ss1s2s3s4sn是一个长度为n的字符串，存放在一个数组当中，编程序将s改造之后输出：将s的偶数下标的字符按原来的相对顺序放在s的后半部分；将s的奇数下标的字符按原来相对顺序的逆序放在s的前半部分。例如，字符串sABCDEFGHIJKL经改造后为ACEGIKLJHFDB。解题思路：这一类的改造数组中元素排列的题目，往往需要用到栈或者队列来解决。本题思路如下：自首到尾扫描数组，对偶数号字符，将它们逐个入栈保存；对奇数号字符，直接前移到指定的位置，最后将栈中的字符逐个置入指定位置。2、采用顺序结构存储串，编写一个函数求串s中出现的第一个最长重复子串的下标和长度。解题思路：先给最长重复子串的下标index和长度length均赋值为0。设s a1a2a3a4an，扫描串s，对于当前字符ai，判定其后是否有相同的字符，若有记为aj，再判定ai+1是否等于aj+1，ai+2是否等于aj+2，如此找到一个不同的字符为止，即找到了一个重复出现的子串，把其下标index1和长度length1，将length1与length比较，保留较长的子串；再从aj+length1之后找重复子串。然后对ai+1之后的字符重复上述过程 最后得到的index和length即纪录了最长重复子串的下标和长度。LCB1103、采用顺序结构存储串，编写一个函数，求串s和串t的一个最长公共子串。解题思路：该题的原理同上题，只不过上题是扫描一个字符串，这里改为扫描两个字符串。LCB111 4、采用顺序结构存储串，编写一个实现串通配符匹配的函数pattern_index()，其中的通配符只有？，它可以和任一字符匹配成功，例如，pattern_index( “?re”, ”there are” )返回的结果是2（掌握这种对通配符的处理方法）。int pattern_index( substr, str ) int i, j, k; for( i = 0; i substr.length )return i; return -1;二叉树的存储结构顺序存储所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。下图给出了一完全二叉树的顺序存储示意。A BEDFGHIJ对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如下图给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费。 (a) 一棵完全二叉树 A B C D E F G H I J数组下标 0 1 2 3 4 5 6 7 8 9 完全二叉树的顺序存储示意图 AACBCBEDDEGFFG (b) 一棵二叉树 (c) 改造后的完全二叉树 A B C D E F G (d) 改造后完全二叉树顺序存储状态 一般二叉树及其顺序存储示意图链式存储所谓二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式：（1）二叉链表存储链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为： lchild data rchild其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号或NULL表示）。下图所示为一棵二叉树的二叉链表示（二叉链表也可以带头结点的方式存放，如b所示）。头指针bt 头结点指针btAACBCBFEDFEDGG (a) 带头指针的二叉链表 (b) 带头结点的二叉链表 （2）三叉链表存储每个结点由四个域组成，具体结构为： lchild data rchild parent其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。下图为一棵二叉树的三叉链表示。ACBFEDG 二叉树的三叉链表表示示意图尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。在后面所涉及到的二叉树的链式存储结构不加特别说明的都是指二叉链表结构。在二叉树的链式存储结构中，不带双亲指针的节点类型可定义如下：struct BTreeNodeElemType data;struct BTreeNode *lchild; struct BTreeNode *rchild;BiTree;带双亲指针的节点类型可定义如下：struct PBTreeNodeElemType data;struct PBTreeNode *lchild; struct PBTreeNode *rchild;struct PBTreeNode *parent;PBiTree;二叉树转换成树和森林树和森林都可以转换为二叉树，二者不同的是树转换成的二叉树，其根结点无右分支，而森林转换后的二叉树，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右分支，将一棵二叉树还原为树或森林的具体方法如下：（1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子都与该结点的双亲结点用线连起来；（2）删去原二叉树中所有的双亲结点与右孩子结点的连线；（3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。下图给出了一棵二叉树还原为森林的过程示意：CAAABBEEBECCFGGFGFDHHDHDIII(a) 一棵二叉树 (b) 加连线 (c) 去掉与右孩子的连线GEAIHDBCF (d) 还原后的树二叉树的三种递归遍历先序遍历：按照先访问根结点，再访问左子树，最后访问右子树的次序访问二叉树中所有结点，且每个结点仅访问一次。其递归算法如下：void PreOrder( BiTree *p ) if( p != NULL ) printf( %d , p-data ); /访问根结点PreOrder( p-lchild ); /访问左子树PreOrder( p-rchild ); /访问右子树中序遍历：按照先访问左子树，再访问根结点，最后访问右子树的次序访问二叉树中所有结点，且每个结点仅访问一次。其递归算法如下：void InOrder( BiTree *p ) if( p != NULL )InOrder( p-lchild ); /访问左子树printf( %d , p-data ); /访问根结点InOrder( p-rchild ); /访问右子树后序遍历：按照先访问左子树，再访问右子树，最后访问根结点的次序访问二叉树中所有结点，且每个结点仅访问一次。其递归算法如下：void PostOrder( BiTree *p ) if( p != NULL )PostOrder( p-lchild ); /访问左子树PostOrder( p-rchild ); /访问右子树printf( %d , p-data ); /访问根结点树的存储结构树有多种存储方法，这里仅讨论最常用的孩子兄弟表示法。即以二叉树链表作为树的存储结构。链表中结点的两个指针域分别指向该结点的第一个孩子结点和下一个兄弟结点。下图左边的树采用孩子兄弟表示法表示成右边的形式：BAEDCIHFGABCDEFGIH二叉树的4种非递归遍历算法二叉树的层次遍历算法所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后队头取出一个元素，每取一个元素，执行下面两个操作：（1） 访问该元素所指结点；（2） 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组QueueMaxSize用以实现队列，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。void LevelOrder( BiTree *bt )int MaxSize = 100;BiTree *QueueMaxSize,*p;/定义队列的头指针和尾指针int front = 0, rear = 0;if( bt = NULL ) return;Queuerear+ = bt; /当队列非空时执行循环while( front != rear ) p = Queuefront+; /访问队列的首节点的数据域 Visite(p-data); /若节点存在左孩子，则左孩子节点指针进入队列 if( p-left != NULL ) Queuerear+ = p-left;/若节点存在右孩子，则右孩子节点指针进入队列 if( p-right != NULL ) Queuerear+ = p-right;层次遍历二叉树时，统计二叉树的每一层的信息（比如说统计每一层的结点中大于50的有多少个，或者统计每一层的结点的和是多少，或者统计每一层有多少个元素等等）int LevelOrder( BiTree *bt ) BiTree *queue100, *p; int front = rear = 0;int level = count = 1; /level表示当前的层数；count表示当前层元素的个数 if( bt = NULL ) return -1; queuerear+ = bt;while( front != rear ) int temp = 0;/暂时保存当前层结点的个数 for( int i = 1; i lchild != NULL ) temp+;queuerear+ = p-lchild; if( p-rchild != NULL ) temp+;queuerear+ = p-rchild;count = temp;level+;二叉树先序（中序）遍历的非递归算法如图所示的二叉树，对其进行先序、中序和后序遍历都是从根结点A开始的，且在遍历过程中经过结点的路线是一样的，只是访问的时机不同而已。图中所示的从根结点左外侧开始，由根结点右外侧结束的曲线，为遍历二叉树的路线。沿着该路线按标记的结点读得的序列为先序序列，按*标记读得的序列为中序序列，按标记读得的序列为后序序列。然而，这一路线正是从根结点开始沿左子树深入下去，当深入到最左端，无法再深入下去时，则返回，再逐一进入刚才深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。A*CB*DFE*G*在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。其过程如下：在沿左子树深入时，深入一个结点入栈一个结点，若为先序遍历，则在入栈之前访问之；当沿左分支深入不下去时，则返回，即从堆栈中弹出前面压入的结点，若为中序遍历，则此时访问该结点，然后从该结点的右子树继续深入；若为后序遍历，则将此结点再次入栈，然后从该结点的右子树继续深入，与前面类同，仍为深入一个结点入栈一个结点，深入不下去再返回，直到第二次从栈里弹出该结点，才访问之(中序遍历的非递归算法只需将visite(p-date)移到p=Stacktop-和p=p-right之间即可)。PreOrder( BiTree *bt ) /先序非递归遍历/ InOrder( BiTree *bt ) /中序非递归遍历int MaxSize = 100, top = 0;BiTree *StackMaxSize, *p = bt;if( bt = NULL ) return;while( !( p = NULL & top = 0 ) ) while( p != NULL ) visite( p-date ); /visite()在此表示先序遍历二叉树Stacktop+ = p; p = p-left;if( top != 0 ) p = Stacktop-; visite( p-date ); /visite()在此表示中序遍历二叉树 p = p-right;PreOrder( BiTree *bt ) /先序非递归遍历/ InOrder( BiTree *bt ) /中序非递归遍历int MaxSize = 100, top = 0;BiTree *StackMaxSize, *p = bt;if( bt = NULL ) return;while( !( p = NULL & top = 0 ) ) while( p != NULL ) visite( p-date ); /visite()在此表示先序遍历二叉树Stacktop+ = p; p = p-left;if( top != 0 ) p = Stacktop-; visite( p-date ); /visite()在此表示中序遍历二叉树 p = p-right;二叉树的后序遍历的非递归算法由前面的讨论可知，后序遍历与先序遍历和中序遍历不同，在后序遍历过程中，结点在第一次出栈后，还需再次入栈，也就是说，结点要入两次栈，出两次栈，而访问结点是在第二次出栈时访问。因此，为了区别同一个结点指针的两次出栈，设置一标志flag，令：1 第一次出栈，结点不能访问2 第二次出栈，结点可以访问 flag当结点指针进、出栈时，其标志flag也同时进、出栈。因此，可将栈中元素的数据类型定义为指针和标志flag合并的结构体类型。定义如下：typedef struct BiTree link; int flag;stacktype;后序遍历二叉树的非递归算法如下。在算法中，一维数组stackMAXNODE用于实现栈的结构，指针变量p指向当前要处理的结点，整型变量top用来表示当前栈顶的位置，整型变量sign为结点p的标志量。PostOrder( BiTree *bt ) int MaxSize = 100, top = 0;BiTree *p = bt;stacktype stackMaxSize;if ( bt = NULL ) return;while( !( p = NULL & top = 0 ) ) while( p != NULL ) stacktop.link = p; stacktop.flag = 1; p = p-left; top+; while( top != 0 & stacktop.flag = 2 ) p = stack-top.link; Visite(p-data); if( top != 0 ) stacktop.flag = 2; p = stacktop.link-right; PostOrder( BiTree *bt ) (这种算法和上面那种本质上是一样的，只是换了一种写法)int MaxSize = 100, top = -1, sign;BiTree *p = bt;stacktype stackMaxSize;if ( bt = NULL ) return;while( !( p = NULL & top = -1 ) ) /结点第一次进栈if( p != NULL ) top+; stacktop.link=p; stacktop.flag=1; p=p-left; else p=stacktop.link; sign=stacktop.flag; top-; /结点第二次进栈 if( sign = 1 ) top+; stacktop.link = p; stacktop.flag = 2; p = p-right; else Visite(p-data); p=NULL; PostOrder( BiTree *bt ) (这种算法没有第一种结构清晰和常见，但是它没有用标志位)int MaxSize = 100, top = -1;BiTree *StackMaxSize, *p = bt;/当栈非空或者p指针非空时执行循环while( !( p = NULL & top = -1 ) ) /p非空则进栈，并向左子树深入，若左子树为空则向右子树深入，直到p为空 while( p != NULL ) Stack+top = p; if( p-left ) p = p-left;else p = p-right; /退栈得到的结点可能是叶子，也可能是无右子树的单分支节点p = Stacktop-;Visite(p-data);/若循环条件成立，则表明右子树已经访问完毕，应退栈并输出该节点的值，/此结点必为右子树非空的分支节点while( top != -1 & Stacktop-right = p ) p = Stacktop-; Visite(p-data);/为了向右子树继续遍历而修改p的值if( top != -1 ) p = Stacktop-right;else p = NULL; 求后继结点BiThrTree PostNode(BiThrTree p)/在先序线索二叉树上寻找结点p的后继结点BiThrTree post; if ( p-rtag = 1 ) post p-rchild;else if( p-ltag = 0 ) post = p-lchild;else post = p-rchild; return(post); (1) 求前驱结点BiThrTree PreNode(BiThrTree p)/在先序线索二叉树上寻找结点p的前驱结点 BiThrTree pre;if( p-ltag = 1 ) pre = p-lchild;else /father表示p的父亲结点的指针 if( p = father-lchild ) pre = father;/访问其父亲结点的左子树中先序遍历的最后一个结点else pre = father-lchild; while( pre-ltag = 0 | pre-rtag = 0 ) /有右儿子的先找右儿子，没有右儿子的才找左儿子，始终是 /右儿子优先 if( pre-rtag = 0 ) pre = pre-rchild;else pre = pre-lchild; return( pre );e. 在后序线索二叉树上查找任意节点的后序前驱和后序后继结点（了解）EH21312543412313215423HACFBDEGJKLIGDACFBC 后序线索二叉树示例（ G D L K J H I E B F C A ）（1） 求前驱结点/当p结点有右子树时，在其右子树中找后序遍历的最后一个结点；/无右子树时，在其左子树中找后序遍历的最后一个结点BiThrTree PreNode(BiThrTree p)/在后序线索二叉树上寻找结点p的前驱结点 BiThrTree pre;if( p-ltag = 1 ) pre = p-lchild;else if( p-rtag = 0 ) pre = p-rchild;