根据先序遍历和中序遍历输出后序遍历

根据先序遍历和中序遍历输出后序遍历

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

上一篇:PostOrder_Traversal 二叉树的非递归后序遍历


下一篇:106从中序和后序遍历序列构造二叉树