【算法练习】数据结构二叉树 百练poj2255:重建二叉树

http://bailian.openjudge.cn/practice/2255

2255:重建二叉树

总时间限制: 

1000ms

 

内存限制: 

65536kB

描述

给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。

输入

输入可能有多组，以EOF结束。
每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。

输出

对于每组输入，用一行来输出它后序遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB

---

题目就是重建二叉树，就是利用前序、中序可以唯一地确定一棵二叉树来进行递归地实现

 

在实现的过程中设置前序/中序遍历的闭区间,不断地修改该闭区间的值进行改变，

注意实现的过程中自己的问题:

1、重建二叉树的时候要记得判断左子树和右子树是否为空再进行递归重建

2、后序遍历的时候也要记得判断左子树和右子树是否为空

 

AC代码：

#include<iostream>
#include <string.h>
using namespace std;

struct Node{
    char c;
    Node *lchild;
    Node *rchild;
}tree[200];
int loc;
char str1[100],str2[100];

//建立新的结点
Node *create(){
    tree[loc].lchild=tree[loc].rchild=NULL;
    return &tree[loc++];
}

Node *build(Node *root,int q1,int q2,int z1,int z2){
    root=create();
    char cr=str1[q1];  //根节点
    root->c=cr;

    int idx=z1;
    for(;idx<=z2;idx++){
        if(str2[idx]==cr)
            break;
    }

    //考虑子树不为空啊
    //如果左子树不为空
    if(idx!=z1){
        root->lchild=build(root->lchild,q1+1,q1+(idx-z1),z1,idx-1);
    }
    if(idx!=z2){
        root->rchild=build(root->rchild,q1+(idx-z1)+1,q2,idx+1,z2);
    }

    return root;

}

void  PostOrder(Node *root){
    //一定要注意是不为空的时候才能进去遍历子树
    if(root->lchild!=NULL){
        PostOrder(root->lchild);
    }
    if(root->rchild!=NULL){
        PostOrder(root->rchild);
    }

    cout<<root->c;
}
int main(){

    while(cin>>str1){
        cin>>str2;
        loc=0;
        //根据前序遍历和中序遍历建立二叉树
        Node *root=NULL;
        int len1=strlen(str1);
        int len2=strlen(str2);
        root=build(root,0,len1-1,0,len2-1);  //前序遍历左边界 有边界
        PostOrder(root);
        cout<<endl;

    }
    return 0;
}