根据先序遍历和中序遍历输出后序遍历
#include <stdio.h>
#include <stdlib.h>
char Pre[100], In[100];
typedef struct Node {
char Data;
struct Node* Left;
struct Node* Right;
}*Tree;
Tree BuildTree(char* Pre, char* In, int n);
void PostOrder(Tree T);
int main()
{
Tree T = NULL;
int n = 0;
char c;
c = getchar();
while (c != '\n')
{
Pre[n++] = c;
c = getchar();
}
n = 0;
c = getchar();
while (c != '\n')
{
In[n++] = c;
c = getchar();
}
T = BuildTree(Pre, In, n);
printf("PostOrder:");
PostOrder(T);
return 0;
}
Tree BuildTree(char* Pre, char* In, int n)
{
if (!n)
return NULL;
char* mid = In;
while (*mid != *Pre)
mid++;
Tree T = (Tree)malloc(sizeof(struct Node));
T->Data = *mid;
T->Left = BuildTree(Pre + 1, In, mid - In);
T->Right = BuildTree(Pre + (mid - In) + 1, mid + 1, n - (mid - In) - 1);
return T;
}
void PostOrder(Tree T)
{
if (T)
{
PostOrder(T->Left);
PostOrder(T->Right);
printf(" %c", T->Data);
}
}