POJ 2255-树的遍历

给定一棵二叉树的先序和中序遍历,求其后序遍历.

先序遍历是先访问根,再遍历左子树,最后遍历右子树,中序遍历是先遍历左子树,再访问根,最后遍历右子树.因而由先序遍历可以确定根,由中序遍历确定左右子树,再在先序遍历中找到对应子树,找到左右子树的根…递归下去,最终确定树的各个节点相对位置,也就找到了树的后序遍历.

D / / B E / / A C G / / F 对于这么一棵二叉树,给出先序中序遍历DBACEGF ,ABCDEFG.寻找后序遍历的过程如下: DBACEGF—->找到根DBACEGF—–>找到子树BAC—>递归地处理(B是左子树的根)….ABCDEFG ABCDEFG ABC


#include <iostream>
using namespace std;

char pre[100];//先序遍历

char in[100];//中序遍历

char post[100];//后序遍历

int len;//节点个数

void solve(int p1,int p2,int m1,int m2)

{

    if(p1>p2)

        return ;

    int i;

    for(i=m1;i<=m2;i++)

        if(in[i]==pre[p1])

            break;

    }

    post[--len]=pre[p1];//根，放到后序遍历的最后面

    if(p1==p2)//叶子节点

        return ;

    solve(p1+i-m1+1,p2,i+1,m2);//递归处理右子树，得到右子树后序遍历

    solve(p1+1,p1+i-m1,m1,i-1);//处理左子树，得到左子树后序遍历

}

int main(int argc, char *argv[])

{

    while (cin>>pre>>in)

    {

        memset(post,0,sizeof(post));

        len=strlen(pre);

        solve(0,len-1,0,len-1);

        cout<<post<<endl;

    }

    return 0;

}

Related Posts