599
求先序遍历
代码如下：
#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;
}
最后更新：2017-04-03 14:54:15