二叉树的遍历 hdu1710

二叉树的遍历主要是三种遍历，前序中序后序
前序：父节点 左节点 右节点的顺序遍历
中序：左节点 父节点 右节点的顺序遍历
后序：左节点 右节点 父节点的顺序遍历
因为遍历顺序 得到的最后的结果有以下特点
假设一个前序遍历的结果是ABCD
A一定是根节点，父节点一定在子节点前面
假设一个中序遍历的结果是ABCDE
假设C是根节点 那么AB一定在C的左子树上，DE一定在C的右子树上
假设一个后序遍历的结果是ABCD
D一定是根节点，父节点一定在子节点后面

就是写一个简单的递归就可以遍历

void preorder(node* root){           //求前序遍历    post数组储存前序遍历结果  
    if(root!=NULL){
        pre[k++] = root->value;
        preorder(root->l);
        preorder(root->r);
    }
}

void inorder(node* root){           //求中序遍历
    if(root!=NULL){
        inorder(root->l);
        in[k++] = root->value;
        inorder(root->r);
    }
}

void postorder(node *root){        //求后序遍历
    if(root!=NULL){
        postorder(root->l);
        postorder(root->r);
        post[k++] = root->value;
    }
}

例题：hdu1710
给出前序和中序遍历结果，要求后序遍历
首先通过前序和中序建树
根据前面说到的特性，我们安排一个指针遍历前序，前序遍历到的第一个数字，就是根节点，然后再中序中找到这个数字的位置，再遍历前序的下一个，再遍历中序找到这个数字在之前那个数字的前面还是后面，这样就可以确定他是根节点的左子树还是右子树，后面的都这样处理，
核心代码

void buildtree(int l,int r,int &t,node* &root){
    int flag=-1;
    for(int i = 1;i<=r;++i){
        if(in[i]==pre[t]){
            flag = i;
            break;
        }
    }
    if(flag == -1)return;
    root =new node(in[flag]);
    t++;
    if(flag>l) buildtree(l,flag-1,t,root->l);
    if(flag<r) buildtree(flag+1,r,t,root->r);
}

建树完之后后序遍历以下储存一下就好了
ac代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=1e3+5;
int pre[MAXN],in[MAXN],post[MAXN];
int k;
struct node{
    int value;
    node *l,*r;
    node(int value = 0,node *l = NULL,node *r = NULL):value(value),l(l),r(r){}
};

void buildtree(int l,int r,int &t,node* &root){
    int flag=-1;
    for(int i = 1;i<=r;++i){
        if(in[i]==pre[t]){
            flag = i;
            break;
        }
    }
    if(flag == -1)return;
    root =new node(in[flag]);
    t++;
    if(flag>l) buildtree(l,flag-1,t,root->l);
    if(flag<r) buildtree(flag+1,r,t,root->r);
}

void postorder(node *root){
    if(root!=NULL){
        postorder(root->l);
        postorder(root->r);
        post[k++] = root->value;
    }
}

void remove_tree(node *root){
    if(root==NULL) return;
    remove_tree(root->l);
    remove_tree(root->r);
    delete root;
}

int main(void){
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;++i) scanf("%d",&pre[i]);
        for(int i=1;i<=n;++i) scanf("%d",&in[i]);
        node *root;
        int t=1;
        buildtree(1,n,t,root);
        k=0;
        postorder(root);
        for(int i=0;i<n;++i) printf("%d%c",post[i],i==n-1?'\n':' ');
        remove_tree(root);
    }
    return 0;
}