HDU_1710_二叉树前序中序确定后序

2018-3-6

按照王道机试书上的思路再做了一遍，先根据先序和中序建树，然后后序遍历。

静态分配数组用于建树，可以返回数组地址当作结点指针。

#include<iostream>

#include<cstdio>

using namespace std;

int pre[],in[],n;

struct Node

{

    Node *lson,*rson;

    int num;

}node[];  //静态分配一个数组用于建树

int cntn;

Node *create(int num)

{

    node[cntn].lson=node[cntn].rson=NULL;

    node[cntn].num=num;

    return &node[cntn++]; //返回数组元素的地址

}

Node *build(int ph,int ih,int len)

{

    Node *now=create(pre[ph]);

    int i;

    for(i=;pre[ph]!=in[i];i++);

    if(i!=ih)

        now->lson=build(ph+,ih,i-ih);

    if(i!=ih+len-)

        now->rson=build(ph+i-ih+,i+,len-(i-ih)-);

    return now;

}

int cnt;

void postOrder(Node *rt)

{

    if(rt==NULL)

        return;

    postOrder(rt->lson);

    postOrder(rt->rson);

    printf("%d",rt->num);

    if(++cnt==n)

        printf("\n");

    else

        printf(" ");

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        cntn=cnt=;

        for(int i=; i<=n; i++)

            scanf("%d",&pre[i]);

        for(int i=; i<=n; i++)

            scanf("%d",&in[i]);

        Node *rt=build(,,n);

        postOrder(rt);

    }

    return ;

}

---

2018-3-3

又做了一遍，这次是自己根据思想自己码了一遍

看了上次的代码，感觉还是上次的好一点

#include<iostream>

#include<cstdio>

using namespace std;

int pre[],in[],cnt,n;

void getPost(int pl,int pr,int il,int ir)

{

    if(pr<pl||ir<il)

        return;

    int loc;

    for(int i=il; i<=ir; i++)

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

        {

            loc=i;

            break;

        }

    if(<loc-il)

        getPost(pl+,pl+loc-il,il,loc-);

    if(<ir-loc)

        getPost(pr-(ir-loc)+,pr,loc+,ir);

    printf("%d",pre[pl]);

    cnt++;

    if(cnt==n)

        printf("\n");

    else

        printf(" ");

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        cnt=;

        for(int i=; i<=n; i++)

            scanf("%d",&pre[i]);

        for(int i=; i<=n; i++)

            scanf("%d",&in[i]);

        getPost(,n,,n);

    }

    return ;

}

---

2018-1-3

研究生考试初试结束一个周了，开始准备复试了，又要开始刷题了。

给定一个二叉树前序和中序，确定后序。

#include<iostream>

#include<cstdio>

using namespace std;

int pre[],in[];

void getPostOrder(int ph,int ih,int len,int flag)

{

    if(len<)

        return;

    int i;

    for(i=; pre[ph]!=in[ih+i]; i++);  //在中序中找到根节点

    getPostOrder(ph+,ih,i,);　　　　　//处理左子树

    getPostOrder(ph+i+,ih+i+,len-i-,);  //处理右子树

    if(flag)

        printf("%d\n",pre[ph]);

    else

        printf("%d ",pre[ph]);

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=; i<n; i++)

            scanf("%d",&pre[i]);

        for(int i=; i<n; i++)

            scanf("%d",&in[i]);

        //cout<<"*"<<endl;

        getPostOrder(,,n,);

    }

    return ;

}