• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 2255-树的遍历

POJ解题 第四度 10年前 (2010-08-25) 35次浏览 0个评论 扫描二维码

file

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

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

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;

}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1014.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址