POJ 2255 Tree Recovery——二叉树的前序遍历、后序遍历、中序遍历规则（递归）

1.前序遍历的规则：（根左右）

（1）访问根节点

（2）前序遍历左子树

（3）前序遍历右子树

对于图中二叉树，前序遍历结果：ABDECF

2.中序遍历的规则：（左根右）

（1）中序遍历左子树

（2）访问根节点

（3）中序遍历右子树

对于图中二叉树，中序遍历结果：DBEAFC

3.后序遍历二叉树的规则：（左右根）

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根节点

对于图中二叉树，后序遍历结果：DEBFCA

例题：POJ2255 给了前、中序遍历，求后序遍历。参考：https://blog.csdn.net/luckcircle/article/details/53327900

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define MAX 50

 using namespace std;

 char a[MAX],b[MAX];

 void build(int n,char *a,char *b){

     if(n<=)return;

     else{                      //先序根左右 中序左根右 后序左右根

         int p=strchr(b,a[])-b;//先序的第一个节点是根 在中序中找到根

         build(p,a+,b);        //并以此分成左右子串 递归求解

         build(n-p-,a+p+,b+p+);

         printf("%c",a[]);

     }

 }

 int main(){

     while(scanf("%s %s",a,b)!=EOF){

         int n=strlen(a);

         build(n,a,b);

         printf("\n");

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

     }

 }

巴特西

POJ 2255 Tree Recovery——二叉树的前序遍历、后序遍历、中序遍历规则（递归）

最新文章

热门文章