给定二叉树的先序遍历和中序遍历，输出它的后序遍历序列。
这里没再用到先申请大Node数组的方法了，想练练写动态内存分配和释放的，一次OK了，也没怎么出错啊，开心~
方法二 - Code：
//给出一个二叉树的先序遍历和中序遍历，输出它的后序遍历
//直接构造的方法白书已给出。这里是先递归构造二叉树，然后进行后序遍历。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 1000
typedef struct node
{
char data;
struct node *left,*right;
}Node;
void postorder(Node *root);
Node* build(int n,char *s1,char *s2);
Node* newNode();
void remove_tree(Node* root);
char s1[MAXN],s2[MAXN];
int main()
{
while(scanf("%s%s",s1,s2)==2)
{
int n=strlen(s1);
Node *root=build(n,s1,s2);
postorder(root);
printf("\n");
remove_tree(root);
}
}
void postorder(Node *root)
{
if(root==NULL) return;
postorder(root->left);
postorder(root->right);
printf("%c",root->data);
}
Node* build(int n,char *s1,char *s2)
{
if(n<=0) return NULL;
Node *r=newNode();
r->data=s1[0];
int p=strchr(s2,s1[0])-s2;
r->left=build(p,s1+1,s2);
r->right=build(n-1-p,s1+1+p,s2+p+1);
return r;
}
Node* newNode()
{
Node* u=(Node*)malloc(sizeof(Node));
if(u!=NULL)
{
u->data=0;
u->left=u->right=NULL;
}
return u;
}
void remove_tree(Node* root)
{
if(root!=NULL)
{
remove_tree(root->left);
remove_tree(root->right);
free(root);
}
}
方法一 - Code：
#include<stdio.h>
#include<string.h>
#define MAXN 256
void build(int n,char *s1,char *s2,char *s);
int main()
{
char s1[MAXN],s2[MAXN],ans[MAXN];
while(scanf("%s%s",s1,s2)==2)
{
int n=strlen(s1);
build(n,s1,s2,ans);
ans[n]='\0';
printf("%s\n",ans);
}
return 0;
}
void build(int n,char *s1,char *s2,char *s)
{
if(n<=0) return;
int p=strchr(s2,s1[0])-s2;
build(p,s1+1,s2,s);
build(n-p-1,s1+p+1,s2+p+1,s+p);
s[n-1]=s1[0];
}
在Java中实现的二叉树结构