数据结构重要算法

hongjuntu

贡献于2011-12-29

字数:33681 关键词:

版权:wuliming_sc 修改:Air_sky 说明:本资料是Air_sky修改wuliming_sc整理的数据结构材料.仅供各位考研师弟师妹们方便之用,如有什么疑议,请通知Air_sky(iceman0481@163.com)本人即删除!!! 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共享存储空间c[1…m],其中的一个栈s1的栈底设在c[1]处,另一个栈s2的栈底设在c[m]处。分别编写s1和s2的进栈push(i, x)、退栈pop(i)和设置栈空setnull(i)的函数,其中i=1、2,分别表示对栈1或者栈2进行设置(注意:仅当整个空间c[1…m]占满时才产生溢出)。 top1 = 1; top2 = m; ... int push( ElemType x, int i ) {//上溢出 if( top1 == top2 - 1 ) { return -1; } //对第一个栈进行进栈操作 else if( i == 1 ) { top1++; c[top1] = x; } //对第二个栈进行进栈操作 else { top2--; c[top2] = x; } return 0; } int pop( ElemType *x, int i ) { //对第一个栈进行出栈操作 if( i == 1 ) { if( top1 == 0 )//栈1下溢出 { return -1; } else { x = c[top1]; top1--; } } //对第二个栈进行出栈操作 else { if( top2 == m + 1 )//栈2下溢出 { return -1; } else { x = c[top2]; top2++; } } return 0; } void setnull( int i ) { if( i == 1 ) { top1 = 1; } else { top2 = m + 1; } } 补充说明:top1是s1的栈指针;top2是s2的栈指针,当top2=top1+1时出现上溢出,当top1=0时出现下溢出,当top2=m+1时出现下溢出。 4、假设一个算数表达式中包含圆括号、方括号、花括号三种类型的括号。编写一个判别表达式中括号是否正确配对的函数correct(exp, tag);其中exp为字符串类型的变量,表示被判别的表达式,tag为布尔型变量。 解题思路:利用一个栈进行判断,将‘(’、‘[’、‘{’进栈,当遇到‘)’、‘]’或‘}’时,检查当前栈顶元素是否是对应的‘(’、‘[’、‘{’,若是则退栈,否则表示不配对。当整个算数表达式检查完毕时栈为空,表示括号正确配对,否则不配对。 5、编写一个算法,利用队列和栈的基本运算将指定队列中的内容进行逆转。 解题思路:假设是否循环顺序队列。建立一个临时的栈,将指定队列中的所有元素出队列到临时的栈中,然后再将栈中的所有元素出栈并入队列,这样队列中的内容就发生了逆转 6、编写一个算法,利用队列的基本运算返回指定队列中的最后一个元素。 解题思路:假设是循环顺序队列,没有取对尾元素的基本运算。建立一个临时的队列tmpqu,将指定队列qu中的所有元素出队并入队到tmpqu对中,这样qu为空,再将队列tmpqu中的所有元素出队并入队到qu中,这是最后入队的一个元素即为所求。 7、编写一个算法,利用栈的基本运算返回指定栈中栈底元素。 解题思路:假定栈采用顺序结构。先退栈s中的所有元素,利用一个临时的栈存放从s栈中退出来的元素,最后的一个元素即为所要返回的元素。然后将临时栈中的元素逐一出栈,压栈到s中,恢复到s栈中原来的顺序。 串、稀疏矩阵、广义表 串的常考知识点: 利用串的几个基本操作解决其它的问题: 串的基本操作有:求串的长度、串的赋值、串的连接、求指定位置的子串、返回子串在主串中的起始位置、判断串是否等价、串的比较…… 串的模式匹配: 很少考察该问题,最多考察一下求next[j]he nextval[j]的值 〔模式匹配待参照教材进一步总结〕 稀疏矩阵常考知识点: 对称矩阵的压缩存储; 上三角、下三角矩阵的压缩存储; 对角矩阵;多维数组; 以上主要考察下标的变换关系。 广义表常考知识点: 广义表的定义;广义表的取头取尾;广义表的做图(头尾表示法、孩子兄弟表示法)。 字符串的模式匹配算法 古典的模式匹配算法: int Index( S, T, pos ) { i = pos; j = 1; while( i <= length( S ) && j <= length( T ) ) { if( S[i] == T[j] ) { i++; j++; } else { i = i – j + 2; j = 1; } } if( 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指针,而是利用已经得到得“部分匹配”的结果将模式向右“滑动”尽可能远得一段距离后,继续进行比较。 假设主串为‘S1S2S3……Sn’,模式串为‘P1P2P3……Pn’。当主串中的第i个字符与模式串中的j个字符不相等时,主串中的第i个字符(i指针不回溯)应该和模式串中的那个字符再比较?假设此时应与模式串的第K(K < j)个字符继续比较,则模式串中前K-1个字符必须满足以下关系,且不可能存在K’ > K满足下列关系式: ‘P1P2P3…Pk-1’=‘S i-k+1S i-k+2Si-k+3…Si-1’ (1) 而已经得到的“部分匹配”的结果是(匹配的模式串中从后向前取k-1个字符): ‘Pj-k+1Pj-k+2Pj-k+3…Pj-1’=‘S i-k+1S i-k+2Si-k+3…Si-1’ (2) 从而个得到下列等式: ‘P1P2P3…Pk-1’=‘Pj-k+1Pj-k+2Pj-k+3…Pj-1’ (3) 反之,若模式串中存在满足(3)的两个子串,则在匹配过程中,当主串的第i个字符与模式串的第j个字符比较不等时,仅需将模式串向右滑动至模式串中第k个字符和主串中第i个字符对齐,此时,模式中头K-1个字符的子串‘P1P2P3…Pk-1’必定与主串中第i个字符之前的长度为K-1的子串‘S i-k+1S i-k+2Si-k+3…Si-1’相等,由此,匹配仅需从模式中第k个字符与主串的第i个字符开始继续往下比较。 若令next[j] = k,则next[j]表明当模式中第j个字符与主串中相应字符比较失配时,在模式中需要重新和主串中该字符进行比较的字符的位置。由此引入模式串的next函数的定义: 0 当j = 1时 next[j] = Max{ k | 1 < K < j 且‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’} 当此集合不为空时 1 其他情况时 KMP算法如下所示: int Index_KMP( SString S, SString T, int pos ) { i = pos; j = 1; While( i <= length( S ) && j <= length( T ) ) { if( j == 0 || S[i] == T[j] ) { i++; j++; } else { j = next[j]; } } if( j > length( T ) ) { return i – length( T ); } else { return 0; } } 说明:在匹配的过程中产生失配时,指针i不变,指针j退回到next[j]所示的位置上重新进行比较,并且当指针j退至零时,指针i和j需同时增加1。即若主串的第i个字符和模式串的第1个字符不等,应从主串的第i+1个字符起重新进行匹配。 KMP算法中next以及nextval函数值的求解 void GetNext( SString t, int next[] ) /*求模式t的next值并存入next数组中*/ {  int i = 1, j = 0; next[1] = 0; while( i < length(t) ) { if( j == 0 || t[i] == t[j] ) { i++; j++; next[i] = j; } else j = next[j]; } } void GetNextval( SString t, int nextval[] ) /*求模式t的nextval值并存入nextval数组中*/ { int i = 1, j = 0; nextval[1] = 0; while( i < length(t) ) { if( j == 0 || t[i] == t[j] ) { i++; j++; if(t[i] == t[j] ) nextval[i] = nextval[j]; else nextval[i] = j; } else j = nextval[j]; } } 举例说明怎样求得next[j]和nextval[j]的值 求模式串‘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 next[j] . 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 nextval[j] . 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 ---------------------------------------------------------------------------------- 下面用比较直观的方法求得next[j]和nextval[j]的值: next[j]的求法: 用公式表示即为: 0 当j = 1时 next[j] = Max{ k | 1 < K < j 且‘P1P2…Pk-1’=‘Pj-k+1Pj-k+2…Pj-1’} 当此集合不为空时 1 其他情况时 用平实的话表述,就是说第一个字符的next[j]为0,第二个字符的next[j]为1。剩下字符的next[j]按下面的规则确定:取从开始到j前面一个字符为止的子串,然后从这个子串的开始和末尾查找两个完全相同的子串,这两个子串应满足以下条件:前面的子串必须从P1开始、后面的子串必须以Pj-1结尾,找到的两个子串必须是能找到的最长的相等的子串。然后以找到的子串的长度值加上1,即为其next[j]的值(如果从0开始编号,则不加1)。 以j = 15的字符为例说明: 在从1到14的这一个子串中,从头到尾所能找到的最长的匹配的子串是‘abcaab’,所以next[15] =7;同时在这14个字符中再也找不到比abcaab更长的相等的子串了。 nextval[j]的求法(依据个人理解) 得出nextval[j]的值要以next[j]为基础。nextval[j]是在next[j]的基础上推出来的。 以j=12的字符为例说明: next[12]=4,而s[12]和s[4]字符相同,这是next[4]=1,而s[1]和s[12]字符也相同,再往前则不能递推了。所以nextval[12]就取next[1]的值0。 以j=14的字符为例说明: next[14]=6,s[14]和s[6]相同;这时next[6]=2,而s[2]和s[14]也相同;next[2]=1,但s[1]和s[14]不同,所以nextval[14]取最后一个其字符和它相同的s[2]的next值1。 字符串的一些比较典型的算法: 1、s=‘s1s2s3s4…sn’是一个长度为n的字符串,存放在一个数组当中,编程序将s改造之后输出:将s的偶数下标的字符按原来的相对顺序放在s的后半部分;将s的奇数下标的字符按原来相对顺序的逆序放在s的前半部分。例如,字符串s=‘ABCDEFGHIJKL’经改造后为‘ACEGIKLJHFDB’。 解题思路:这一类的改造数组中元素排列的题目,往往需要用到栈或者队列来解决。本题思路如下:自首到尾扫描数组,对偶数号字符,将它们逐个入栈保存;对奇数号字符,直接前移到指定的位置,最后将栈中的字符逐个置入指定位置。 2、采用顺序结构存储串,编写一个函数求串s中出现的第一个最长重复子串的下标和长度。 解题思路:先给最长重复子串的下标index和长度length均赋值为0。设s =‘a1a2a3a4…an’,扫描串s,对于当前字符ai,判定其后是否有相同的字符,若有记为aj,再判定ai+1是否等于aj+1,ai+2是否等于aj+2,…,如此找到一个不同的字符为止,即找到了一个重复出现的子串,把其下标index1和长度length1,将length1与length比较,保留较长的子串;再从aj+length1之后找重复子串。然后对ai+1之后的字符重复上述过程…… 最后得到的index和length即纪录了最长重复子串的下标和长度。LCB110 3、采用顺序结构存储串,编写一个函数,求串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; i++ ) { for( j = i, k = 0; substr[k] == str[j] || substr[k] == '?'; j++, k++ ) { continue; } if( k > substr.length ) return i; } return -1; } 二叉树的存储结构 顺序存储 所谓二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系,然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点,这种存储才有意义。因此,依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映出结点之间的逻辑关系,这样既能够最大可能地节省存储空间,又可以利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。下图给出了一完全二叉树的顺序存储示意。 A B E D F G H I J 对于一般的二叉树,如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中,则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系,只有增添一些并不存在的空结点,使之成为一棵完全二叉树的形式,然后再用一维数组顺序存储。如下图给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然,这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时,会造成空间的大量浪费。 (a) 一棵完全二叉树 A B C D E F G H I J 数组下标 0 1 2 3 4 5 6 7 8 9 完全二叉树的顺序存储示意图 A A C B C B E D D E G F F G (b) 一棵二叉树 (c) 改造后的完全二叉树 A B C ∧ D E ∧ ∧ ∧ F ∧ ∧ G (d) 改造后完全二叉树顺序存储状态 一般二叉树及其顺序存储示意图 链式存储 所谓二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示着元素的逻辑关系。通常有下面两种形式: (1)二叉链表存储 链表中每个结点由三个域组成,除了数据域外,还有两个指针域,分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为: lchild data rchild 其中,data域存放某结点的数据信息;lchild与rchild分别存放指向左孩子和右孩子的指针,当左孩子或右孩子不存在时,相应指针域值为空(用符号∧或NULL表示)。下图所示为一棵二叉树的二叉链表示(二叉链表也可以带头结点的方式存放,如b所示)。 头指针bt 头结点指针bt A A C ∧ B C ∧ B ∧ F ∧ ∧ E ∧ D ∧ ∧ F ∧ ∧ E ∧ D ∧ ∧ G ∧ ∧ G ∧ (a) 带头指针的二叉链表 (b) 带头结点的二叉链表 (2)三叉链表存储 每个结点由四个域组成,具体结构为: lchild data rchild parent 其中,data、lchild以及rchild三个域的意义同二叉链表结构;parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点,又便于查找双亲结点;但是,相对于二叉链表存储结构而言,它增加了空间开销。下图为一棵二叉树的三叉链表示。 A ∧ C ∧ B ∧ F ∧ ∧ ∧ E ∧ D ∧ ∧ G ∧ 二叉树的三叉链表表示示意图 尽管在二叉链表中无法由结点直接找到其双亲,但由于二叉链表结构灵活,操作方便,对于一般情况的二叉树,甚至比顺序存储结构还节省空间。因此,二叉链表是最常用的二叉树存储方式。在后面所涉及到的二叉树的链式存储结构不加特别说明的都是指二叉链表结构。 在二叉树的链式存储结构中,不带双亲指针的节点类型可定义如下: struct BTreeNode { ElemType data; struct BTreeNode *lchild; struct BTreeNode *rchild; }BiTree; 带双亲指针的节点类型可定义如下: struct PBTreeNode { ElemType data; struct PBTreeNode *lchild; struct PBTreeNode *rchild; struct PBTreeNode *parent; }PBiTree; 二叉树转换成树和森林 树和森林都可以转换为二叉树,二者不同的是树转换成的二叉树,其根结点无右分支,而森林转换后的二叉树,其根结点有右分支。显然这一转换过程是可逆的,即可以依据二叉树的根结点有无右分支,将一棵二叉树还原为树或森林的具体方法如下: (1)若某结点是其双亲的左孩子,则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来; (2)删去原二叉树中所有的双亲结点与右孩子结点的连线; (3)整理由(1)、(2)两步所得到的树或森林,使之结构层次分明。 下图给出了一棵二叉树还原为森林的过程示意: C A A A B B E E B E C C F G G F G F D H H D H D I I I (a) 一棵二叉树 (b) 加连线 (c) 去掉与右孩子的连线 G E A I H D B C F (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 ); //访问根结点 } } 树的存储结构 树有多种存储方法,这里仅讨论最常用的孩子兄弟表示法。即以二叉树链表作为树的存储结构。链表中结点的两个指针域分别指向该结点的第一个孩子结点和下一个兄弟结点。下图左边的树采用孩子兄弟表示法表示成右边的形式: B A E D C I H F G A B C D E F G I H 二叉树的4种非递归遍历算法 二叉树的层次遍历算法 所谓二叉树的层次遍历,是指从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。由层次遍历的定义可以推知,在进行层次遍历时,对一层结点访问完后,再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问,这样一层一层进行,先遇到的结点先访问,这与队列的操作原则比较吻合。因此,在进行层次遍历时,可设置一个队列结构,遍历从二叉树的根结点开始,首先将根结点指针入队列,然后队头取出一个元素,每取一个元素,执行下面两个操作: (1) 访问该元素所指结点; (2) 若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行,当队列为空时,二叉树的层次遍历结束。 在下面的层次遍历算法中,二叉树以二叉链表存放,一维数组Queue[MaxSize]用以实现队列,变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。 void LevelOrder( BiTree *bt ) { int MaxSize = 100; BiTree *Queue[MaxSize],*p; //定义队列的头指针和尾指针 int front = 0, rear = 0; if( bt == NULL ) return; Queue[rear++] = bt; //当队列非空时执行循环 while( front != rear ) { p = Queue[front++]; //访问队列的首节点的数据域 Visite(p->data); //若节点存在左孩子,则左孩子节点指针进入队列 if( p->left != NULL ) { Queue[rear++] = p->left; } //若节点存在右孩子,则右孩子节点指针进入队列 if( p->right != NULL ) { Queue[rear++] = p->right; } } } 层次遍历二叉树时,统计二叉树的每一层的信息(比如说统计每一层的结点中大于50的有多少个,或者统计每一层的结点的和是多少,或者统计每一层有多少个元素等等) int LevelOrder( BiTree *bt ) { BiTree *queue[100], *p; int front = rear = 0; int level = count = 1; //level表示当前的层数;count表示当前层元素的个数 if( bt == NULL ) return -1; queue[rear++] = bt; while( front != rear ) { int temp = 0;//暂时保存当前层结点的个数 for( int i = 1; i <= count; i++ ) { p = queue[front++]; /***************************/ /* 统计p所指结点的相关信息 */ /***************************/ if( p->lchild != NULL ) { temp++; queue[rear++] = p->lchild; } if( p->rchild != NULL ) { temp++; queue[rear++] = p->rchild; } } count = temp; level++; } } 二叉树先序(中序)遍历的非递归算法 如图所示的二叉树,对其进行先序、中序和后序遍历都是从根结点A开始的,且在遍历过程中经过结点的路线是一样的,只是访问的时机不同而已。图中所示的从根结点左外侧开始,由根结点右外侧结束的曲线,为遍历二叉树的路线。沿着该路线按△标记的结点读得的序列为先序序列,按*标记读得的序列为中序序列,按⊕标记读得的序列为后序序列。 然而,这一路线正是从根结点开始沿左子树深入下去,当深入到最左端,无法再深入下去时,则返回,再逐一进入刚才深入时遇到结点的右子树,再进行如此的深入和返回,直到最后从根结点的右子树返回到根结点为止。先序遍历是在深入时遇到结点就访问,中序遍历是在从左子树返回时遇到结点访问,后序遍历是在从右子树返回时遇到结点访问。 ⊕ △ A * △ ⊕ △ C B ⊕ * * △ ⊕ ⊕ △ △ D F E ⊕ * * * ⊕ G * △ 在这一过程中,返回结点的顺序与深入结点的顺序相反,即后深入先返回,正好符合栈结构后进先出的特点。因此,可以用栈来帮助实现这一遍历路线。其过程如下: 在沿左子树深入时,深入一个结点入栈一个结点,若为先序遍历,则在入栈之前访问之;当沿左分支深入不下去时,则返回,即从堆栈中弹出前面压入的结点,若为中序遍历,则此时访问该结点,然后从该结点的右子树继续深入;若为后序遍历,则将此结点再次入栈,然后从该结点的右子树继续深入,与前面类同,仍为深入一个结点入栈一个结点,深入不下去再返回,直到第二次从栈里弹出该结点,才访问之(中序遍历的非递归算法只需将visite(p->date)移到p=Stack[top--]和p=p->right之间即可)。 PreOrder( BiTree *bt ) //先序非递归遍历 // InOrder( BiTree *bt ) //中序非递归遍历 { int MaxSize = 100, top = 0; BiTree *Stack[MaxSize], *p = bt; if( bt == NULL ) return; while( !( p == NULL && top == 0 ) ) { while( p != NULL ) { visite( p->date ); //visite()在此表示先序遍历二叉树 Stack[top++] = p; p = p->left; } if( top != 0 ) { p = Stack[top--]; visite( p->date ); //visite()在此表示中序遍历二叉树 p = p->right; } } } PreOrder( BiTree *bt ) //先序非递归遍历 // InOrder( BiTree *bt ) //中序非递归遍历 { int MaxSize = 100, top = 0; BiTree *Stack[MaxSize], *p = bt; if( bt == NULL ) return; while( !( p == NULL && top == 0 ) ) { while( p != NULL ) { visite( p->date ); //visite()在此表示先序遍历二叉树 Stack[top++] = p; p = p->left; } if( top != 0 ) { p = Stack[top--]; visite( p->date ); //visite()在此表示中序遍历二叉树 p = p->right; } } } 二叉树的后序遍历的非递归算法 由前面的讨论可知,后序遍历与先序遍历和中序遍历不同,在后序遍历过程中,结点在第一次出栈后,还需再次入栈,也就是说,结点要入两次栈,出两次栈,而访问结点是在第二次出栈时访问。因此,为了区别同一个结点指针的两次出栈,设置一标志flag,令: { 1 第一次出栈,结点不能访问 2 第二次出栈,结点可以访问 flag= 当结点指针进、出栈时,其标志flag也同时进、出栈。因此,可将栈中元素的数据类型定义为指针和标志flag合并的结构体类型。定义如下: typedef struct { BiTree link; int flag; }stacktype; 后序遍历二叉树的非递归算法如下。在算法中,一维数组stack[MAXNODE]用于实现栈的结构,指针变量p指向当前要处理的结点,整型变量top用来表示当前栈顶的位置,整型变量sign为结点p的标志量。 PostOrder( BiTree *bt ) { int MaxSize = 100, top = 0; BiTree *p = bt; stacktype stack[MaxSize]; if ( bt == NULL ) return; while( !( p == NULL && top == 0 ) ) { while( p != NULL ) { stack[top].link = p; stack[top].flag = 1; p = p->left; top++; } while( top != 0 && stack[top].flag == 2 ) { p = stack[--top].link; Visite(p->data); } if( top != 0 ) { stack[top].flag = 2; p = stack[top].link->right; } } PostOrder( BiTree *bt ) (这种算法和上面那种本质上是一样的,只是换了一种写法) { int MaxSize = 100, top = -1, sign; BiTree *p = bt; stacktype stack[MaxSize]; if ( bt == NULL ) return; while( !( p == NULL && top == -1 ) ) { //结点第一次进栈 if( p != NULL ) { top++; stack[top].link=p; stack[top].flag=1; p=p->left; } else { p=stack[top].link; sign=stack[top].flag; top--; //结点第二次进栈 if( sign == 1 ) { top++; stack[top].link = p; stack[top].flag = 2; p = p->right; } else { Visite(p->data); p=NULL; } } } } PostOrder( BiTree *bt ) (这种算法没有第一种结构清晰和常见,但是它没有用标志位) { int MaxSize = 100, top = -1; BiTree *Stack[MaxSize], *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 = Stack[top--]; Visite(p->data); //若循环条件成立,则表明右子树已经访问完毕,应退栈并输出该节点的值, //此结点必为右子树非空的分支节点 while( top != -1 && Stack[top]->right == p ) { p = Stack[top--]; Visite(p->data); } //为了向右子树继续遍历而修改p的值 if( top != -1 ) { p = Stack[top]->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. 在后序线索二叉树上查找任意节点的后序前驱和后序后继结点(了解) E H 2 1 3 1 2 5 4 3 4 1 2 3 1 3 2 1 5 4 2 3 H A C F B D E G J K L I G D A C F B C 后序线索二叉树示例( 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; } else { pre = p->lchild; } } return( pre ); } (2) 求后继结点 BiThrTree PostNode(BiThrTree p) //在后序线索二叉树上寻找结点p的后继结点 { BiThrTree post; if( p->rtag == 1 ) { post = p->lchild; } else { if( p == father->rchild ) { post = father->rchild; } else { post = father->rchild; while( post->ltag == 0 || post->rtag == 0 ) { if( post->ltag == 0 ) { post = post->lchild; } else { post = post->rchild; } } } } return( post ); } f. 在中序线索二叉树中查找结点p的父亲结点father 中序线索二叉树具有如下性质: 若p是father的左孩子,则father是p的最右子孙的右线索; 若p是father的右孩子,则father是p的最左子孙的左线索。 (在前序和后序线索二叉树上,应该不能找父亲结点吧?) BiThrTree FatherNode( BiThrTree p ) { //在中序线索二叉树上寻找结点p的父亲结点(根结点除外),由于不知道p结点是其父亲结点的左孩子//还是右孩子,所以需要查找两次,如果最左子孙的左线索所指的结点不是其父亲结点,则查找最右子孙//的右线索所指的结点 BiThrTree fahter; //查找p的最左子孙的左线索 father = p; while( father->ltag == 0 ) { father = father->lchild; } father = father->lchild; if( father && father->rchild == p ) { return(father); } //查找p的最右子孙的右线索 father = p; while( father->rtag == 0 ) { father = father->rchild; } father = father->rchild; if( father && father->lchild == p ) { return(father); } ruturn(NULL); } g. 在中序线索二叉树上查找任意结点在前序序列下的后继 中序线索二叉树的示例(D B G E H A C F ) 若x的左孩子不是线索,那么x的左孩子就是x的前序序列的后继。如图1中,结点2的前序后继是3。 若x的左孩子是线索,且x的右孩子不是线索,那么x的右孩子就是x的前序序列的后继。如图2中,结点2的前序后继是3。 若x的左右孩子都是线索,那么由右线索向上,直到某个结点的右孩子不是线索为止,这个结点的右孩子就是x的前序序列的后继。如图3中,结点4的后继是5。 图1 图2 图3 BiThrTree PostNode( BiThrTree head, BiThrTree p ) { //在中序线索二叉树上寻找结点p的先序的后继结点,head为线索树的头结点 //可以利用该函数来实现对中序线索二叉树的先序遍历,不过没有下面另外一种方法好 //在中序线索二叉树上利用这些线索寻找先序的前驱结点(由于找结点的父亲结点比较麻烦,所以暂时//省略这种情况) BiThrTree post; if( p->ltag == 0 ) { post=p->lchild; } else { post=p; while( post->rtag == 1 && post->rchild != head ) post=post->rchild; post=post->rchild; } return(post); } typedef struct BiThrNode { elemtype data; struct BiThrNode *lchild; struct BiThrNode *rchild; int ltag; int rtag; }BiThrTree; void Traverse(BiThrTree T ) { //前序遍历中序线索二叉树T,T是带头结点的中序线索二叉树 BiThrTree p = T->lchild; //头结点的左孩子是根结点 while( p != T ) //若回到头结点,则遍历结束 { while( p->ltag == 0 ) //前序遍历到最左端 { visit(p->date); p = p->lchild; } visit(p->date); //访问此最左结点,然后考虑向右转 while( p->rtag == 1 ) //由右线索向上 { p = p->rchild; } if( p->rtag == 0 ) //右孩子存在则转向右孩子,继续对此右子树前序遍历 { p = p->rchild; } } } h.在中序线索二叉树上查找任意结点在前序序列下的前驱 这时需要知道该结点的父亲结点相关的信息,分三种情况讨论: (1)该结点是father的左孩子,则father结点就是其前驱; (2)该结点是father的右孩子,father的左孩子为空,则father结点是其前驱; (3)该结点是father的右孩子,father的左孩子也存在,则father的左子树中前序遍历最后遍历到的结点为其前驱; i. 在中序线索二叉树上查找任意结点在后序下的前驱 参照下面的算法理解如何实现在中序线索二叉树上实现查找后序遍历下某个结点的前驱结点: BiThrTree PretNode(BiThrTree head, BiThrTree p) { //在中序线索二叉树上寻找结点p的后序下的前驱结点,head为线索树的头结点 BiThrTree pre; if( p->rtag == 0 ) { pre=p->rchild; } else { pre=p; while( pre->ltag == 1 && post->rchild != head ) { pre=pre->lchild; } pre=pre->lchild; } return(pre); } j 在中序线索二叉树上查找任意结点在后序序列下的后继 由于后序序列遍历二叉树需要知道的很重要的信息是当前访问结点的父亲结点,因此只要中序线索二叉树能够提供这个信息,就能够在中序线索二叉树中查找到给定结点的后序序列的后继。 若x是father的右孩子,则father结点就是x的后序序列的后继结点,如图1中结点1的后继是结点2。 若x是father的左孩子,且father的右孩子是线索,则father就是x的后序序列的后继结点。如图2中结点2的后继是结点3。 若x是father的左孩子,且father的右孩子也存在,则father的右子树中最左边一个左右孩子均为线索的结点就是x的后序序列的后继结点。如图3中结点2的后继是结点3。 5 4 3 1 2 图1 图2 图3 后序遍历中序线索二叉树,算法中不许使用栈和递归(全真题解148页,上面还有另外一种算法,可以参照理解) BiThrTree LeftMost( BiThrTree T ) { //返回T的最左子孙的左线索 BiThrTree p = T; While( p->ltag == 0 ) P = p->lchild; Return p->lchild; } BiThrTree RightMost( BiThrTree T ) { //返回T的最右子孙的右线索 BiThrTree p = T; While( p->rtag == 0 ) P = p->rchild; Return p->rchild; } BiThrTree Traverse( BiThrTree T ) { //后序遍历中序线索二叉树,设置访问标记tag,仅当tag=2时才访问当前结点 BiThrTree p = T, q; int tag; //待访问标记,表示当前结点从左孩子还是右孩子返回 while( p != NULL ) { while( p->ltag == 0 ) //向左到尽头 p = p->lchild; if( p->rtag == 0 ) //左孩子为线索,右孩子为链,则相当于从左返回,tag值为1 tag = 1; else //当前结点是叶子结点,tag值为2 tag = 2; while( tag == 2 ) { visit(p); q = LeftMost( p ); if( q && q->rchild == p )//测试p是否是q的右孩子 { p = q; //从右孩子返回,需要访问q,使p指向父亲结点 tag = 2; } else //p是其父亲结点的左孩子 { p = RightMost( p ); //找到其父亲结点 if( p && p->rtag == 0 ) tag = 1; else tag = 2; } } if( tag == 1 && p ) //由左孩子返回,向右孩子转 p = p->rchild; } } 在中序线索二叉树上查找值为x的结点 利用在中序线索二叉树上寻找后继结点和前驱结点的算法,就可以遍历到二叉树的所有结点。比如,先找到按某序遍历的第一个结点,然后再依次查询其后继;或先找到按某序遍历的最后一个结点,然后再依次查询其前驱。这样,既不用栈也不用递归就可以访问到二叉树的所有结点。 在中序线索二叉树上查找值为x的结点,实质上就是在线索二叉树上进行遍历,将访问结点的操作具体写为那结点的值与x比较的语句。下面给出其算法: BiThrTree PostNode(BiThrTree p) //在中序线索二叉树上寻找结点p的中序后继结点 { BiThrTree post; if ( p->rtag == 1 ) { post = p->rchild; } else { post = p->rchild; while( post->ltag == 0 ) post=post->lchild; } return(post); } BiThrTree Search (BiThrTree head,elemtype x) //在以head为头结点的中序线索二叉树中查找值为x的结点 { BiThrTree p; p = head->lchild; while( p->ltag == 0 && p != head ) p = p->lchild; while( p != head && p->data != x ) p=PostNode( p ); //PostNode为求p的后继结点的函数,如上面所示 if( p == head ) { printf(“Not Found the data!\n”); return(0); } else return(p); } 在中序线索二叉树上的更新 线索二叉树的更新是指,在线索二叉树中插入一个结点或者删除一个结点。一般情况下,这些操作有可能破坏原来已有的线索,因此,在修改指针时,还需要对线索做相应的修改。一般来说,这个过程的代价几乎与重新进行线索化相同。这里仅讨论一种比较简单的情况,即在中序线索二叉树中插入一个结点p,使它成为结点s的右孩子。下面分两种情况来分析: (1)若s的右子树为空,如图(a)所示,则插入结点p之后成为图(b)所示的情形。在这种情况中,s的后继将成为p的中序后继,s成为p的中序前驱,而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。 (2)若s的右子树非空,如图(c)所示,插入结点p之后如图(d)所示。S原来的右子树变成p的右子树,由于p没有左子树,故s成为p的中序前驱,p成为s的右孩子;又由于s原来的后继成为p的后继,因此还要将s原来的本来指向s的后继的左线索,改为指向p。 NULL NULL s s s p s p (a) (b) (c) (d) 中序线索树更新位置右子树为空 中序线索树更新位置右子树不为空 下面给出上述操作的算法。 void InsertThrRight( BiThrTree s, BiThrTree p ) //在中序线索二叉树中插入结点p使其成为结点s的右孩子 { BiThrTree w; p->rchild=s->rchild; p->rtag=s->rtag; p->lchild=s; p->ltag=1; //将s变为p的中序前驱 s->rchild=p; s->rtag=0; //p成为s的右孩子 if(p->rtag==0) //当s原来右子树不空时,找到s的后继w,变w为p的后继, //p为w的前驱 { w = PostNode(p); //PostNode为求p的中序后继结点的函数 w->lchild=p; } } 由遍历序列恢复二叉树 从前面讨论的二叉树的遍历知道,任意一棵二叉树结点的先序序列和中序序列都是唯一的。反过来,若已知结点的先序序列和中序序列,能否确定这棵二叉树呢?这样确定的二叉树是否是唯一的呢?回答是肯定的。 根据定义,二叉树的先序遍历是先访问根结点,其次再按先序遍历方式遍历根结点的左子树,最后按先序遍历方式遍历根结点的右子树。这就是说,在先序序列中,第一个结点一定是二叉树的根结点。另一方面,中序遍历是先遍历左子树,然后访问根结点,最后再遍历右子树。这样,根结点在中序序列中必然将中序序列分割成两个子序列,前一个子序列是根结点的左子树的中序序列,而后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序序列中找到对应的左子序列和右子序列。在先序序列中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。这样,就确定了二叉树的三个结点。同时,左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列,如此递归下去,当取尽先序序列中的结点时,便可以得到一棵二叉树。 同样的道理,由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。因为,依据后序遍历和中序遍历的定义,后序序列的最后一个结点,就如同先序序列的第一个结点一样,可将中序序列分成两个子序列,分别为这个结点的左子树的中序序列和右子树的中序序列,再拿出后序序列的倒数第二个结点,并继续分割中序序列,如此递归下去,当倒着取取尽后序序列中的结点时,便可以得到一棵二叉树。 下面通过一个例子,来给出右二叉树的先序序列和中序序列构造唯一的一棵二叉树的实现算法。 已知一棵二叉树的先序序列与中序序列分别为: A B C D E F G H I B C A E D G H F I 试恢复该二叉树。 首先,由先序序列可知,结点A是二叉树的根结点。其次,根据中序序列,在A之前的所有结点都是根结点左子树的结点,在A之后的所有结点都是根结点右子树的结点,由此得到下图所示的状态。然后,再对左子树进行分解,得知B是左子树的根结点,又从中序序列知道,B的左子树为空,B的右子树只有一个结点C。接着对A的右子树进行分解,得知A的右子树的根结点为D;而结点D把其余结点分成两部分,即左子树为E,右子树为F、G、H、I,如图(b)所示。接下去的工作就是按上述原则对D的右子树继续分解下去,最后得到如图(c)的整棵二叉树。 A A A D B D B FG I H DEFGHI F B C C E C E I G H (a) (b) (c) 一棵二叉树的恢复过程示意 上述过程是一个递归过程,其递归算法的思想是:先根据先序序列的第一个元素建立根结点;然后在中序序列中找到该元素,确定根结点的左、右子树的中序序列;再在先序序列中确定左、右子树的先序序列;最后由左子树的先序序列与中序序列建立左子树,由右子树的先序序列与中序序列建立右子树。 下面给出用C语言描述的该算法。假设二叉树的先序序列和中序序列分别存放在一维数组preod[ ]与inod[ ]中,并假设二叉树各结点的数据值均不相同 (需要说明的是,数组preod和inod的元素类型可根据实际需要来设定,这里设为字符型。另外,如果只知道二叉树的先序序列和后序序列,则不能唯一地确定一棵二叉树) void ReBiTree(char preod[],char inod[],int n,BiTree root) /*n为二叉树的结点个数,root为二叉树根结点的存储地址*/ { if( n ≤ 0 ) root=NULL; else PreInOd(preod,inod,1,n,1,n,root); } void PreInOd( char preod[], char inod[], int i,j,k,h,BiTree *t) { t = (BiTree*)malloc(sizeof(BiTree)); t->data = preod[i]; int m = k; while (inod[m] != preod[i] ) m++; if( m == k ) t->left = NULL; else PreInOd( preod, inod, i+1, i+m-k, k, m-1, t->left ); if( m == h ) t->right = NULL; else PreInOd( preod, inod, i+m-k+1, j, m+1, h, t->right); } 二叉树的顺序存储结构和链式存储结构的相互转换 1. 假设一棵完全二叉树用顺序方法存储在数组tree中,请编写算法,根据数组tree建立与之对应的链式存储结构(LCB223)。 void creat( char tree[], int n, int i, BiTree *b ) { if( i > n || tree[i] == 'Φ' ) b == NULL; else { b = (BiTree *)malloc( sizeof( BiTree ) ); b->data = tree[i]; creat( tree[], n, 2*i, b->lchild ); creat( tree[], n, 2*i + 1, b->rchild ); } } 2. 链式存储结构转换成顺序存储结构(以下举例说明) C B E D F G A H 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 C A B ∧ D E ∧ F ∧ ∧ G ∧ ∧ ∧ H ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ creat( BiTree *bt, char tree[], int i ) //假设tree[]数组足以存下所有的结点,并已经初始化为空 { if( bt != NULL ) { tree[i] = bt->data; creat( bt->lchild, tree, 2*i );creat( bt->rchild, tree, 2*i+1 ); } } 另外一种递归算法为: int creat( BiTree *bt, BiTree *tree[], int n ) { int length = 1, current = 1; BiTree *p; tree[current] = bt; while( current <= length ) { p = tree[current]; if( p != NULL && p->lchild != NULL ) { tree[2*current] = p->lchild; length = 2*current; } else { tree[2*current] = NULL; } if( p != NULL && p->rchild != NULL ) { tree[2*current+1] = p->rchild; length = 2*current+1; } else { tree[2*current+1] = NULL; } current++; } return length; } 二叉树相关的算法 1. 统计二叉树总的结点数 解:计算一颗二叉树的所有结点的递归模型如下: f(b) = 0 若 b = NULL f(b) = f(b->lchild)+f(b->rclild)+1 其它情况 相应的算法: int count(BiTree *b) { int num1, num2; if( b == NULL ) return 0; else { num1 = count(b->lchild); num2 = count(b->rchild); return( num1 + num2 + 1 ); } } 2. 统计二叉树的叶子结点数 解:计算一颗二叉树的叶子结点数的递归模型如下: f(b) = 0 若 b = NULL f(b) = 1 若b->lchild == NULL && b->rchild == NULL f(b) = f(b->lchild)+f(b->rclild)+1 其它情况 相应的算法: int count(BiTree *b) { int num1, num2; if( b == NULL ) return 0; else if(b->lchild == NULL && b->rchild == NULL ) return 1; else { num1 = count(b->lchild); num2 = count(b->rchild); return( num1 + num2 + 1 ); } } 3. 统计二叉树中单孩子结点数 解:计算一颗二叉树的单孩子结点数的递归模型如下: f(b) = 0 若 b = NULL f(b) = f(b->lchild)+f(b->rclild)+1 若b->lchild != NULL && b->rchild == NULL 或b->lchild == NULL && b->rchild != NULL f(b) = f(b->lchild)+f(b->rclild) 其它情况 相应的算法: int OneChild(BiTree *b) { int num1, num2, n = 0; if( b == NULL ) return 0; else if((b->lchild != NULL && b->rchild == NULL ) ||b->lchild == NULL && b->rchild != NULL ) return 1; num1 = count(b->lchild); num2 = count(b->rchild); return( num1 + num2 + n ); } 4.编写算法,将二叉树的叶子结点串联起来 5. 从根结点到指定结点的路径问题:假设二叉树采用链式存储结构进行存储,root指向根结点, p所指结点为任一给定的结点,编写一个算法求从根结点到p所指结点之间的路径。 解题思路:本题采用非递归后序遍历树root,当后序遍历访问到p所指结点时,此时栈中所有结点均为p所指结点的祖先,由这些祖先便构成了一条从根结点到p所指结点之间的路径。LCB224 6. 已知二叉树采用链式存储结构,设计一个算法输出二叉树中从根结点到每个孩子结点的路径。 解题思路:本题也可以采用非递归后序遍历的方式解决,当遍历到的结点是叶子结点时,就输出此时栈里面的结点,常考同上算法(利用该算法的思想,也可以求出从根结点到每一个结点的路径)。 7. 共同祖先问题:假设二叉树采用链式存储结构进行存储,root指向根结点,p所指结点和q所指结点为二叉树中的两个结点,编写算法求它们最近的共同祖先r所指的结点。 解题思路:本题采用非递归后序遍历的方法解决。不失一般性,假设p所指结点在q所指结点的左边,当后序遍历访问到p所指结点时,此时stack中所有结点均为p所指结点的祖先,此时将该stack复制到一个数组中;然后继续后序遍历访问到q所指结点,同样此时stack中所有结点均为q所指结点的祖先。再将其于先前数组中的结点依次比较,找出它们最近的共同祖先。 8.求二叉树的最长或者最短路径 解题思路:求二叉树的最长路径,还是可以采用非递归后序遍历的方法解决;求最短路径,有什么更好的方法呢? 9.二叉树相似或等价的问题:判断两颗二叉树是否相似,所谓二叉树t1和t2是相似的指的是t1和t2都是空的二叉树;或者t1和t2的根结点相似,t1的左子树和t2的左子树是相似的且t1的右子树和t2的右子树是相似的。 解题思路:本题的递归模型如下 f( t1, t2 ) = true 若t1=t2=NULL = false 若t1、t2之一为NULL,另一个不为NULL = f( t1->lchild, t2->lchild ) && f( t1->rchild, t2->rchild ) 其它情况 其它情况 int like( BiTree *b1, BiTree *b2 ) { int like1, like2; if( b1 == NULL && b2 == NULL ) return 1; else if( b1 == NULL || b2 == NULL ) return 0; //如果要判断是否等价,在这里再加上一个判断 else if( b1->data != b2->data ) return 0; else { like1 = like( b1->lchild, b2->lchild ); like2 = like( b1->rchild, b2->rchild ); return ( like1 && like2 ); } } 10. 求二叉树的深度 解题思路:若一颗二叉树为空,则其深度为0,否则其深度等于左子树和右子树的最大深度加1,递归模型如下所示: depth(b) = 0 若b = NULL depth(b) = max( depth( b->lchild, depth->rchild ) + 1 ) 其它情况 int depth( BiTree *b ) { if( b == NULL ) return 0; else { dep1 = depth( b->lchild ); dep2 = depth( b->rchild ); if( dep1 > dep2 ) return dep1 + 1; else return dep2 + 1; } } 11. 求二叉树指定结点的深度 解题思路:本题可以用后序遍历,层次遍历的方法。下面提供另外一种算法: int level( BiTree *t, BiTree *p, int lh ) { if( t == NULL ) return 0; else if( t == p ) return lh; else { tag = level( t->lchild, p, lh+1 ); if( tag != 0 ) return tag; else return( level( t->rchild, p, lh+1 ) ); } } 12. 释放二叉树的所有结点 解题思路:本题通过后序遍历来实现,先释放根结点的左子树和右子树,最后释放根结点。不能用前序和中序的办法解决。 void release( BiTree *b ) { if( b != NULL ) { release( b->lchild ); //释放左子树占用的存储空间 release( b->lchild ); //释放右子树占用的存储空间 free( b ); //释放根结点占用的存储空间 } } 13. 判定一个树是否是完全二叉树 解题思路:本题可以采用层次遍历的方法解决;也可以把二叉树转存在顺序结构里面,然后再判断。同样,判断一棵树是否是满二叉树,也可以采用类似的方法。 14. 把一棵树拆分成两棵树:假定二叉树T中至多有一个结点的值为x,试设计一个算法拆去以该结点为根的子树,使原二叉树分成两棵二叉树。 解题思路:先判断二叉树的根结点是否是要找的结点,若是,则直接拆开;否则在左子树中寻找该结点被拆分;若左子树中未找到,则在右子树中查找(两颗二叉树合并为一颗二叉树的方法:先将这两个二叉树存入对应的顺序结构中,然后通过顺序存储结构为中介合并,最后恢复该二叉树)。 BiTree *dislink( BiTree *t, int x ) { BiTree *p, *find; if( t == NULL ) return NULL; else if( t->data == x ) { p = t; t = NULL; return p; } else { find = dislink( t->lchild, x ); if( !find ) return( dislink( t->rchild, x ) ); } } 15. 判定一棵树是否是二叉排序树 二叉排序树或者是一棵空树;或者是具有下列性质的二叉树: ⑴ 若左子树不空,则左子树上所有结点的值均小于根结点的值;若右子树不空,则右子树上所有结点的值均大于根结点的值。 ⑵ 左右子树也都是二叉排序树。 解题思路:可以中序遍历该二叉树,将遍历得到的结点值存入一个数组里面,然后判断数组是否有序。另外一种方法:中序遍历该二叉树,在访问当前结点时,把当前结点的值和最近已经访问的结点的值进行比较,如果当前结点的值小于其前序结点的值,则可判断该二叉树是无序的,因为二叉树的中序遍历是递增有序的。 16. 交换二叉树的左右子树(LNZT123) 解题思路:要将二叉树的左右子树交换过来,采用前序、中序、后序遍历算法都可以?只要保证对每个结点的左右孩子的指针,只交换一次?(在LNZT123上说,利用后序遍历的方法最合适) 17. 根据二叉树输出对应的算数表达式 解题思路:由二叉树输出相应的表达式实际上是一个中序遍历的过程,同时要判断运算符的优先级,若左右子树运算符的优先级小于父结点,则要加括号。 //比较两个操作符的优先级 int compare( op1, op2 ) { if(op1的优先级高于op2) 返回 1; else if( op1的优先级等于op2 ) 返回 0; else 返回 -1; } void printexp( BiTree *t ) { int tmp; if( t->lchild != NULL) { tmp = compare( t->op, t->lchild->op ); if( tmp != 0 ) printf(“(”); printexp( t->lchild ); if( tmp != 0 ) printf(“)”); } print(t->op); if( t->rchild != NULL) { tmp = compare( t->op, t->rchild->op ); if( tmp != 0 ) printf(“(”); printexp( t->rchild ); if( tmp != 0 ) printf(“)”); } } 18. 根据算数表达式构造相应的二叉树:试用c语言编写一个递归函数,函数的输入为一个带括号的包括加减乘除四则运算表达式的字符串,例如“(a+b)*(c+d)”,该函数根据运算符优先级来构造一颗二叉树,树的根结点为优先级最低的运算符。该函数最终返回二叉树的根结点。(东北大学99试题) 图的存储方式-邻接矩阵 下面介绍图的邻接矩阵存储表示。在用邻接矩阵存储图时,除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组来存储顶点信息,另外还有图的顶点数和边数。故可将其形式描述如下: #define Num 100 /*最大顶点数设为100*/ #define Max 1000000 /*设max为最大权值*/ typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct { VertexType Vertexs[Num]; /*顶点表*/ EdgeType edges[Num][Num]; /*邻接矩阵,即边表*/ int n, e; /*顶点数和边数*/ }MGgragh; /*Maragh是以邻接矩阵存储的图类型*/ 建立一个图的邻接矩阵存储的算法如下: void CreateMGraph ( MGraph *G ) { /*建立有向图G的邻接矩阵存储*/ int i,j,k,w; char v1,v2; scanf("%d,%d",&(G->n),&(G->e)); /*输入顶点数和边数*/ for( i=0; in; i++ ) scanf("\n%c",&(G->Vertexs[i]));/*输入顶点信息,建立顶点表*/ for( i=0; in; i++ ) for ( j=0; jn; j++ ) G->edges[i][j] = Max; /*初始化邻接矩阵*/ for( k=0; ke; k++ ) /*输入e条边,建立邻接矩阵*/ { scanf("\n%d,%d",&v1,&v2,&w); /*输入和一条边相关的信息*/ i = location( g, v1 ); j = location( g, v2 ); G->edges[i][j]=w; /*若加入G->edges[j][i]=w*/ //G->edges[j][i]=w; /*则为无向图的邻接矩阵存储建立*/ } }/*CreateMGraph*/ 在邻接矩阵存储结构上实现基本操作: int location ( MGgragh g, VertexType v ) { int i = 0; while( i < g->n && g->Vertexs[i] != v ) i++; if( i >= g->n ) return -1; else return i; } int firstadj ( MGgragh g, VertexType v ) { int i, j; i = location( g, v ); j = 0; While( j < g->n && g->edges[i][j] == Max ) j++; if( j >= g->n ) return -1; else return j; } int nextadj ( MGgragh g, VertexType v, VertexType w ) { int i, j, k; i = location( g, v ); j = location( g, w ); k = j+1; While( k < g->n && g->edges[i][k] == Max ) k++; if( k >= g->n ) Return -1; else Return k; } 十字链表 在十字链表上实现基本操作: int location ( OLGraph *g, VertexType v ) { int i = 0; while( i < g->n && g->xlist[i].vertex != v ) i++; if( i >= g->n ) Return -1; else Return i; } int firstadj ( OLGraph *g, VertexType v ) { i = location( g, v ); if( g->xlist[i].firstout == NULL ) return –1; else return g->xlist[i].firstout.headvex; } int nextadj ( OLGraph *g, VertexType v, VertexType w ) { i = location( g, v ); j = location( g, w ); p = g->xlist[i].firstout; while( p != NULL && p->headvex != j ) p = p->tlink; p = p->tlink; if( p == NULL ) return –1; else return p->headvex; } int degree (OLGraph *g, VertexType v ) { indegree = 0, outdegree = 0; I = location(v); p = g->xlist[i].firstout; while( p != NULL ) { outdegree++; p = p->tlink; } p = g->xlist[i].firstin; while( p != NULL ) { indegree++; p = p->hlink; } return ( indegree + outdegree ); } 深度优先算法的非递归算法 void DFS(ALGraph *G, int v ) //非递归算法 { int stack[G->n]; int top = -1; stack[++top] = 0; while( top > -1 ) { tag = stack[top--]; visited[tag] = 1; visit( G->adjlist[tag] ); p = G->adjlist[tag].firstadf; while( p != NULL && visited[p->adjvex] == 1 ) p = p->next; if( p == NULL ) top--; else stack[++top] = p->adjvex; } } 分析上述算法,在遍历时,对图中每个顶点至多调用一次DFS 函数,因为一旦某个顶点被标志成已被访问,就不再从它出发进行搜索。因此,遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,查找每个顶点的邻接点所需时间为O(n 2) ,其中n为图中顶点数。而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),其中e为无向图中边的数或有向图中弧的数。由此,当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e) 广度优先搜索非递归算法 BFS( Graph *G, int v ) { int front = 0, rear = 0; int queue[G->n]; if( visited[v] ==0 ) { queue[rear++] =v; while( front != rear ) { tag = queue[front++]; visited[tag] = 1; visit( G->adjlist[tag] ); for( w = firstadj( G, tag ); w != NULL; w = nextadj( G, tag, w ) ) if( visited[w] == 0 ) queue[rear++] = w; }//while }//if }//BFS void Topo_Sort (AlGraph *G) {/*对已带入度的邻接链表为存储结构的图G,输出其一种拓扑序列*/ int top = -1; /* 栈顶指针初始化*/ for ( i = 0;i < n;i++ ) /* 依次将入度为0的顶点压入链式栈*/ { if ( G->adjlist[i].Count == 0 ) { G->adjlist[i].count = top; top = i; } } for( i = 0; i < n; i++ ) { if( top == -1 ) { printf(“The network has a cycle”); return; } j = top; top = G->adjlist[top].count; /*从栈中退出一个顶点并输出*/ printf(“%c”,G->adjlist[j].vertex); ptr = G->adjlist[j].firstedge; while( ptr != null ) { k = ptr->adjvex; G->adjlist[k].count--; /*当前输出顶点邻接点的入度减1*/ if( G->adjlist[k].count == 0 ) /*新的入度为0的顶点进栈*/ { G->adjlist[k].count = top; top=k; } ptr=ptr->next; /*找到下一个邻接点*/ } } } 对有向图进行拓扑排序的算法大致有以下几种: (1) 无前驱顶点优先法: 在有向图中选择一个没有前驱的顶点输出; 在图中删除该顶点和所有以它为尾的弧; 重复以上两步,直到所有没有前驱的结点均输出,该算法得到一个拓扑有序序列(若此时还有结点未输出, 表明图中存在环) (2)无后继结点优先法: 在有向图中选择一个没有后继的顶点输出; 在图中删除该顶点和所有以它为头的弧; 重复以上两步,直到所有没有后继的顶点均输出,该算法得到逆向的拓扑有序序列 (3)深度优先算法 对图进行深度优先遍历,在退出DFS函数时输出顶点,该算法输出的是逆向的拓扑有序序列 下面以十字链表为例说明拓扑排序的算法(邻接表和逆邻接表和这个类似) TopSort( OLGraph *G ) { int count = 0; int stack[max], top = -1; int indegree[G->n]; for( int i = 0; i < G->n; i++ ) //确定每一个顶点的入度 { indegree[i] = 0; p = G->xlist[i].firstout; while( p != NULL ) { p = p->tlink; indegree[i]++; } } for( int i = 0; i < G->n; i++ ) //入度为0的进栈 if( indegree[i] == 0 ) stack[++top] = i; while( top != -1 ) //栈不为空时循环 { tag = stack[top--]; count++; p = G->xlist[tag]->firstout; while( p ) { if( --indegree[p->headvex] == 0 ) stack[++top] = p->headvex; p = p->tlink; } } if( count != G->n ) 存在回路; }//end AOE图与关键路径 1.AOE网(Activity on edge network) 在带权的有向图中,以顶点表示事件,以有向边表示活动,边上的权值表示活动的开销(如该活动持续的时间),则此带权的有向图称为AOE网。 如果用AOE网来表示一项工程,那么,仅仅考虑各个子工程之间的优先关系还不够,更多的是关心整个工程完成的最短时间是多少;哪些活动的延期将会影响整个工程的进度,而加速这些活动是否会提高整个工程的效率。因此,通常在AOE网中列出完成预定工程计划所需要进行的活动,每个活动计划完成的时间,要发生哪些事件以及这些事件与活动之间的关系,从而可以确定该项工程是否可行,估算工程完成的时间以及确定哪些活动是影响工程进度的关键。 AOE网具有以下两个性质: ①只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。 ②只有在进入一某顶点的各有向边所代表的活动都已经结束,该顶点所代表的事件才能发生。 图8.37给出了一个具有15个活动、11个事件的假想工程的AOE网。v1,v2,… v11分别表示一个事件;,,…,分别表示一个活动;用a1,a2, …,a15代表这些活动。其中,v1称为源点,是整个工程的开始点,其入度为0;v11为终点,是整个工程的结束点,其出度为0 。 对于AOE网,可采用与AOV网一样的邻接表存储方式。其中,邻接表中边结点的域为该边的权值,即该有向边代表的活动所持续的时间。 V4 a7=6 a3=23 a11=7 a1=3 a4=1 a8=8 V7 V2 V1 a2=43 a5=3 a9=4 V5 V11 V8 a12=4 a15=6 a6=5 V3 a13=10 a10=2 V6 V10 a14=1 V9 图8.37 一个AOE网实例 2.关键路径 由于AOE网中的某些活动能够同时进行,故完成整个工程所必须花费的时间应该为源点到终点的最大路径长度(这里的路径长度是指该路径上的各个活动所需时间之和)。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。关键路径长度是整个工程所需的最短工期。这就是说,要缩短整个工期,必须加快关键活动的进度。 利用AOE网进行工程管理时要需解决的主要问题是: ①计算完成整个工程的最短路径。 ②确定关键路径,以找出哪些活动是影响工程进度的关键。 3.关键路径的确定 为了在AOE网中找出关键路径,需要定义几个参量,并且说明其计算方法。 (1)事件的最早发生时间ve[k] ve[k]是指从源点到顶点的最大路径长度代表的时间。 (2)事件的最迟发生时间vl[k] vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。 (3)活动ai的最早开始时间e[i] 若活动ai是由弧表示,根据AOE网的性质,只有事件vk发生了,活动ai才能开始。也就是说,活动ai的最早开始时间应等于事件vk的最早发生时间。 (4)活动ai的最晚开始时间l[i] 活动ai的最晚开始时间指,在不推迟整个工程完成日期的前提下, 必须开始的最晚时间。 根据每个活动的最早开始时间e[i]和最晚开始时间l[i]就可判定该活动是否为关键活动,也就是那些l[i]=e[i]的活动就是关键活动,而那些l[i]>e[i]的活动则不是关键活动,l[i]-e[i]的值为活动的时间余量。关键活动确定之后,关键活动所在的路径就是关键路径。 下面以图8.37所示的AOE网为例,求出上述参量,来确定该网的关键活动和关键路径。 首先,按照 (8-1)式求事件的最早发生时间ve[k]。 ve (1)=0 ve (2)=3 ve (3)=4 ve (4)=ve(2)+2=5 ve (5)=max{ve(2)+1,ve(3)+3}=7 ve (6)=ve(3)+5=9 ve (7)=max{ve(4)+6,ve(5)+8}=15 ve (8)=ve(5)+4=11 ve (9)=max{ve(8)+10,ve(6)+2}=21 ve (10)=max{ve(8)+4,ve(9)+1}=22 ve (11)=max{ve(7)+7,ve(10)+6}=28 其次,按照 (8-2)式求事件的最迟发生时间vl[k]。 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21 vl (8)=min{ vl (10)-4, vl (9)-10}=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19 vl (5)=min{ vl (7)-8,vl (8)-4}=7 vl (4)= vl (7)-6=15 vl (3)=min{ vl (5)-3, vl (6)-5}=4 vl (2)=min{ vl (4)-2, vl (5)-1}=6 vl (1)=min{vl (2)-3, vl (3)-4}=0 再按照 (8-3)式和(8-4)式求活动ai的最早开始时间e[i]和最晚开始时间l[i]。 活动a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活动a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活动a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活动a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6 活动a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活动a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活动a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活动a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活动a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活动a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活动a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活动a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活动a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活动a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活动a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =22 最后,比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动,关键路径如图8.38所示。 V1 V11 V5 a2=4 a9=4 a5=3 V8 a15=6 V10 a13=4 a14=1 V9 V3 图8.38 一个AOE网实例 实践证明,用AOE-网来估算某些工程完成的时间是非常有用的。但是,由于网中各项活动是相互牵涉的,因此,影响关键活动的因素也是多方面的,任何一项活动持续时间的改变都会影响到关键路径的改变。所以关键活动的速度提高是有限度的。只有在不改变网的关键路径的情况下,提高关键活动的速度才有效。另一方面,若网中有几条关键路径,单是提高一条关键路径上的关键活动的速度还不能导致整个工程缩短工期,必须提高同时在几条关键路径上的活动的速度。 (补充说明:在求活动的最早开始时间和最迟开始时间以及事件的最早发生时间和最迟发生事件时,可以先在图上画出关键路径,然后参照图形根据实际情况得出相关的数据) 求ASL成功和ASL不成功 设一组关键字为35、27、38、26、45、55、57、63,表长为10、哈希函数为H(key) = key % 7,线性探测再散列解决冲突。求ASL成功和ASL不成功 0 1 2 3 4 5 6 7 8 9 ….. 35 27 63 38 45 26 27 55 1 1 3 1 2 1 1 2 ASL成功=(1/8)* ( 1+1+3+1+2+1+1+2 ) ASL不成功=(1/7)* ( 9+8+7+6+5+4+3 ) (其中的分母取7而不取10。这里取7表示用该哈希函数能定为到的从0到6这7个位置。) 哈希表的删除(05年辅导班笔记) 用除留余数法作为哈希函数,用线性探测再散列解决冲突,设计算法删除关键字并将所有可以前移的元素前移填空位置,以尽量保证不断裂 解题思路: 先计算关键字的地址,若为空则空操作; 若不空,则与给定的关键字比较,若不等,按解决冲突的函数规则继续往下查找; 若相等,则在剩下的元素中查找和要查找的关键字是同义词的最后一个关键字,将其填入要删除的关键字的位置,并将该位置置空。 相关算法如下: HashDelete( ElemType s[], int m, int key ) { H = hash(key); if( s[H] == 空 ) return -1; else if( s[H] == key ) delete( s, H, H, key ); else { H1 = (H+1)%m; while( s[H1] != key && s[H1] != 空 && H1 != H ) H1 = (H1+1)%m; } if( s[H1] == key ) delete( s, H, H1, key ); else return -1 } delete( ElemType s[], int i, int j, int key ) //i为hash(key)得到的值;j为key在s中的位置;本函数的作用是将s中和关键字key是同义词的关键字找到并确定其 最后一个位置,然后将最后一个填充到j的位置,将最后一个的置空 { last = j; H1 = (j+1)%m; while( H1 != i ) { if( s[H1] == 空 ) break; else if( hash(s[H1] == i ) ) last = H1; H1 = (H1+1)%m; } s[j] = s[last]; //将最后一个同义词前移 s[last] = 空; //置空 } 排序 void shellsort ( sqlist r, int n ) //本算法的步长是2的整数倍 { int i,j,gap; gap = n/2; while( gap>0 ) { for( i = gap+1; i<=n; i++ ) { if( r[i].key < r[i-gap].key ) { r[0] = r[i]; for( j=i-gap; j>0 && r[0].key

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ]
2 人已下载

下载文档

相关文档