求先序遍历

代码如下：

#include <stdio.h>

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char  elem;
};

TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length)
{
    if(length == 0)
    {
        return NULL;
    }

    TreeNode* node = new TreeNode;		//新建一个树节点
    node->elem = *(aftorder+length-1);

	printf("%c ",node->elem);

    int rootIndex = 0;

    for(;rootIndex < length; rootIndex++)		//找这个根节点
    {
        if(inorder[rootIndex] ==  *(aftorder+length-1))
            break;
    }

    node->left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex);
    node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1));

    return node;
}

int main()
{
	char* in="42513";		//中序
    char* af="45231";		//后序
    BinaryTreeFromOrderings(in, af, 5); 

	printf("\n");

    return 0;
}

暂时无法判断非法输入的代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#define MAXN 5005

using namespace std;

char in[MAXN];       //中序
char af[MAXN];       //后序
char ans[MAXN];		//最后输出的前序序列
int count=0;

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char  elem;
};

TreeNode* BinTree(char* inorder, char* aftorder, int length)
{
    if(length == 0)
    {
        return NULL;
    }

    TreeNode* node = new TreeNode;		//新建一个树节点
    node->elem = *(aftorder+length-1);

	ans[count++]=node->elem;		//存入答案

    int rootIndex = 0;

    for( ;rootIndex<length;rootIndex++)		//找这个根节点
    {
        if(inorder[rootIndex]==*(aftorder+length-1))
            break;
    }

    node->left = BinTree(inorder,aftorder,rootIndex);
    node->right = BinTree(inorder+rootIndex+1 , aftorder+rootIndex , length-(rootIndex+1));

	return node;
}

int main()
{
	int n;
	scanf("%d",&n);

	int i;
	for(i=0;i<n;i++)
		cin>>in[i];

	for(i=0;i<n;i++)
		cin>>af[i];

    BinTree(in, af, n);

	for(i=0;i<strlen(ans)-1;i++)
		printf("%c ",ans[i]);
	printf("%c\n",ans[i]);

    return 0;
}

改用int型：

#include <stdio.h>
#include <stdlib.h>
#define MAXN 5005

int in[MAXN];       //中序
int af[MAXN];       //后序
int ans[MAXN];		//最后输出的前序序列
int count=0;

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    int elem;
};

TreeNode* BinTree(int inorder[], int aftorder[], int length)
{
	if(length == 0)
    {
        return NULL;
    }

    TreeNode* node = new TreeNode;		//新建一个树节点
    node->elem = *(aftorder+length-1);

	ans[count++]=node->elem;		//存入答案

    int rootIndex=0;

    for( ;rootIndex<length;rootIndex++)		//在中序遍历中找这个根节点
    {
        if(inorder[rootIndex]==*(aftorder+length-1))
            break;
    }
	if(rootIndex>=length)
	{
		printf("-1\n");
		exit(0);
	}

    node->left = BinTree(inorder,aftorder,rootIndex);
    node->right = BinTree(inorder+rootIndex+1 , aftorder+rootIndex , length-(rootIndex+1));

	return node;
}

int main()
{
	int n;
	scanf("%d",&n);

	int i;
	for(i=0;i<n;i++)
		scanf("%d",&in[i]);

	for(i=0;i<n;i++)
		scanf("%d",&af[i]);

    BinTree(in,af,n);

	for(i=0;i<count-1;i++)
		printf("%d ",ans[i]);
	printf("%d\n",ans[i]);

    return 0;
}