PAT A 1020 Tree Traversals (25 分)

一、思路

先中序序列递归建树：
依据二叉树的性质：后续序列（或子序列）的末尾元素即该二叉树（或子树）的根， 且该元素在中序序列中的左侧元素在其左子树上，右侧元素在其右子树上

void create( node *&T, int l1, int r1, int l2, int r2 )
{
    if( l1 <= r1 )
    {
        T = (node  *)malloc( sizeof(node) );
        T->data = post[r1];
        T->lchild = T->rchild = NULL;
        int m;
        for( m = 0; l2 + m <= r2 && in[l2 + m] != T->data; ++m );
        create( T->lchild, l1, l1 + m - 1, l2, l2 + m - 1 );
        create( T->rchild, l1 + m, r1 - 1, l2 + m + 1, r2 );
    }
}

层序遍历（基于队列）输出：

    queue<node*> q;
    q.push(Root);
    while( !q.empty() )
    {
        p = q.front();
        q.pop();
        if( p->lchild )
            q.push( p->lchild );
        if( p->rchild )
            q.push( p->rchild );
        printf("%d%s", p->data, q.empty() ? "":" ");
    }

二、代码

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <queue>
using namespace std;
typedef struct node
{
    int data;
    struct node *lchild, *rchild;
}node;
int N;
vector<int> in(30), post(30);
void create( node *&T, int l1, int r1, int l2, int r2 )
{
    if( l1 <= r1 )
    {
        T = (node  *)malloc( sizeof(node) );
        T->data = post[r1];
        T->lchild = T->rchild = NULL;
        int m;
        for( m = 0; l2 + m <= r2 && in[l2 + m] != T->data; ++m );
        create( T->lchild, l1, l1 + m - 1, l2, l2 + m - 1 );
        create( T->rchild, l1 + m, r1 - 1, l2 + m + 1, r2 );
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    node *Root, *p;
    for( int i = 0; i < N; ++i )
        scanf("%d", &post[i]);
    for( int i = 0; i < N; ++i )
        scanf("%d", &in[i]);
    create( Root, 0, N - 1, 0, N - 1 );
    queue<node*> q;
    q.push(Root);
    while( !q.empty() )
    {
        p = q.front();
        q.pop();
        if( p->lchild )
            q.push( p->lchild );
        if( p->rchild )
            q.push( p->rchild );
        printf("%d%s", p->data, q.empty() ? "":" ");
    }
}