0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 求先序遍历

this_is_bill 2013-11-16 10:30:00 浏览576

```#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;
}
```

```#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;
}
```

this_is_bill
+ 关注