二叉树的三种先序后序中序遍历的互相推出（例UVA 536 - Tree Recovery）

本文主要是介绍二叉树的三种先序后序中序遍历的互相推出（例UVA 536 - Tree Recovery），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关于树的先序中序后序遍历

由先序中序推后序

因为 先序：根 左 右

        中序：左 根 右

        后序：右 根 左

根据他们的对应关系推出树

1，先序遍历 中序遍历推后序遍历：

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn=50;
void tree(int n,char *s1, char *s2,char *s)  //构建树
{if(n<=0)return;int p= strchr(s2,s1[0])-s2;  // 在中序遍历中寻找根的位置tree(p,s1+1,s2,s);      // 生成左子树，tree(n-p-1,s1+p+1,s2+p+1,s+p); // 生成右子树s[n-1]=s1[0];  // 将先序的前值赋给后序的末值
}
int main()
{char s[maxn],s1[maxn],s2[maxn];while(~(scanf("%s%s",&s1,&s2))){int n=strlen(s1);tree(n,s1,s2,s);s[n]='\0';printf("%s\n",s);}return 0;
}

以上为 UVA 536 - Tree Recovery 点击打开链接 (二叉树)ac代码

但是。。。

由后序 中序去推前序崩掉了 。。。。可能是因为推的不行吧

从网上看了看思路思考一番，蒙出来了

2，先序遍历 中序遍历推后序遍历：

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn=50;
int l;
void tree(int n,char *s1, char *s2,char *s)
{if(n<=0)return;int p=0;for(;p<n;p++){if(s2[p]==s1[n-1])break;}tree(p,s1,s2,s+1);tree(n-p-1,s1+p,s2+p+1,s+p+1);s[0]=s1[n-1];}
int main()
{char s[maxn],s1[maxn],s2[maxn];while(~(scanf("%s%s",s2,s1))){memset(s,0,sizeof(s));int l=strlen(s1);tree(l,s1,s2,s);s[l]='\0';printf("%s\n",s);}return 0;
}

关于借鉴的大神的代码

    /***************************************************************************/  /*已知中序、后序遍历，求前序遍历*/  /***************************************************************************/  #include <iostream>  #include <fstream>  #include <string>  using namespace std;  struct TreeNode  {  struct TreeNode* left;  struct TreeNode* right;  char  elem;  };  TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length)  {  if(length == 0)  {  return NULL;  }  TreeNode* node = new TreeNode;//Noice that [new] should be written out.  node->elem = *(aftorder+length-1);  cout<<node->elem;  int rootIndex = 0;  for(;rootIndex < length; rootIndex++)//a variation of the loop  {  if(inorder[rootIndex] ==  *(aftorder+length-1))  break;  }  node->left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex);  node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1));  return node;  }  int main(int argc, char** argv)  {  printf("Question: 已知中序、后序遍历，求前序遍历\n\n");  char* in="ADEFGHMZ";    //中序  char* af="AEFDHZMG";    //后序  cout<<"中序是："<<in<<endl;  cout<<"后序是："<<af<<endl<<endl;  cout<<"前序是：";  BinaryTreeFromOrderings(in, af, 8);   printf("\n\n");  return 0;  }  

/***************************************************************************/  /*已知前序、中序遍历，求后序遍历*/  
/***************************************************************************/  #include <iostream>    
#include <fstream>    
#include <string>    using namespace std;  struct TreeNode  
{  struct TreeNode* left;  struct TreeNode* right;  char  elem;  
};  void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)  
{  if(length == 0)  {  //cout<<"invalid length";  return;  }  TreeNode* node = new TreeNode;//Noice that [new] should be written out.  node->elem = *preorder;  int rootIndex = 0;  for(;rootIndex < length; rootIndex++)  {  if(inorder[rootIndex] == *preorder)  break;  }  //Left  BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);  //Right  BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));  cout<<node->elem;  return;  
}  int main(int argc, char* argv[])  
{  printf("Question: 已知前序、中序遍历，求后序遍历\n\n");  char* pr="GDAFEMHZ";//前序  char* in="ADEFGHMZ";//中序  cout<<"前序是："<<pr<<endl;  cout<<"中序是："<<in<<endl<<endl;  cout<<"后序是：";  BinaryTreeFromOrderings(in, pr, 8);  printf("\n\n");  return 0;  

来源 点击打开链接

还有非递归求法（点击打开链接）

完美，以后再细看一次

这篇关于二叉树的三种先序后序中序遍历的互相推出（例UVA 536 - Tree Recovery）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---