二叉树和KMP代码

二叉树的非递归遍历二叉树的非递归遍历二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。1.递归实现voidpreOrder1(BinTree*root)//递归前序遍历{if(root!=NULL){coutroot-data;preOrder1(root-lchild);preOrder1(root-rchild);}}2.非递归实现根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：对于任一结点P：1)访问结点P，并将结点P入栈;2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;3)直到P为NULL并且栈为空，则遍历结束。voidpreOrder2(BinTree*root)//非递归前序遍历{stackBinTree*s;BinTree*p=root;while(p!=NULL||!s.empty()){while(p!=NULL){coutp-data;s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();s.pop();p=p-rchild;}}}二.中序遍历中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。1.递归实现voidinOrder1(BinTree*root)//递归中序遍历{if(root!=NULL){inOrder1(root-lchild);coutroot-data;inOrder1(root-rchild);}}2.非递归实现根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：对于任一结点P，1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；3)直到P为NULL并且栈为空则遍历结束voidinOrder2(BinTree*root)//非递归中序遍历{stackBinTree*s;BinTree*p=root;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p-lchild;}if(!s.empty()){p=s.top();coutp-data;s.pop();p=p-rchild;}}}三.后序遍历后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。1.递归实现voidpostOrder1(BinTree*root)//递归后序遍历{if(root!=NULL){postOrder1(root-lchild);postOrder1(root-rchild);coutroot-data;}}2.非递归实现后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。第一种思路（看第二种思路）：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。voidpostOrder2(BinTree*root)//非递归后序遍历{stackBTNode*s;BinTree*p=root;BTNode*temp;while(p!=NULL||!s.empty()){while(p!=NULL)//沿左子树一直往下搜索，直至出现没有左子树的结点{BTNode*btn=(BTNode*)malloc(sizeof(BTNode));btn-btnode=p;btn-isFirst=true;s.push(btn);p=p-lchild;}if(!s.empty()){temp=s.top();s.pop();if(temp-isFirst==true)//表示是第一次出现在栈顶{temp-isFirst=false;s.push(temp);p=temp-btnode-rchild;}else//第二次出现在栈顶{couttemp-btnode-data;p=NULL;}}}}第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。voidpostOrder3(BinTree*root)//非递归后序遍历{stackBinTree*s;BinTree*cur;//当前结点BinTree*pre=NULL;//前一次访问的结点s.push(root);while(!s.empty()){cur=s.top();if((cur-lchild==NULL&&cur-rchild==NULL)||(pre!=NULL&&(pre==cur-lchild||pre==cur-rchild))){coutcur-data;//如果当前结点没有孩子结点或者孩子节点都已被访问过s.pop();pre=cur;}else{if(cur-rchild!=NULL)s.push(cur-rchild);if(cur-lchild!=NULL)s.push(cur-lchild);}}}从头到尾彻底理解KMP（2014年8月22日版）2.暴力匹配算法假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？如果用暴力匹配的思路，并假设现在文本串S匹配到i位置，模式串P匹配到j位置，则有：如果当前字符匹配成功（即S[i]==P[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0。相当于每次匹配失败时，i回溯，j被置为0。理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：1.intViolentMatch(char*s,char*p)2.{3.intsLen=strlen(s);4.intpLen=strlen(p);5.6.inti=0;7.intj=0;8.while(isLen&&jpLen)9.{10.if(s[i]==p[j])11.{12.//①如果当前字符匹配成功（即S[i]==P[j]），则i++，j++13.i++;14.j++;15.}16.else17.{18.//②如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=019.i=i-j+1;20.j=0;21.}22.}23.//匹配成功，返回模式串p在文本串s中的位置，否则返回-124.if(j==pLen)25.returni-j;26.else27.return-1;28.}举个例子，如果给定文本串S“BBCABCDABABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：1.S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）2.S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i=i-(j-1)，j=0”，i从2变到4，j一直为0）3.直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i]==P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）4.S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i]==P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去5.直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0”，相当于S[5]跟P[0]匹配（i=5，j=0）6.至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5]=P[1]=B，而P[0]=A，即P[1]!=P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i不往回退，只需要移动j即可呢？答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i不回溯，通过修改j的位置，让模式串尽量地移动到有效的位置。3.KMP算法3.1定义Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法由DonaldKnuth、VaughanPratt、JamesH.Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：假设现在文本串S匹配到i位置，模式串P匹配到j位置o如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），都令i++，j++，继续匹配下一个字符；o如果j!=-1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j-next[j]位。换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置-失配字符对应的next值（next数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j-next[j]，且此值大于等于1。很快，你也会意识到next数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next[j]=k，代表j之前的字符串中有