已知一棵二叉树，前序遍历序列为ABECDFGHIJ,中序遍历序列为EBCDAFHIGJ,编程输出该树的后序遍历序列。

Question

实训题目：已知一棵二叉树，前序遍历序列为ABECDFGHIJ,中序遍历序列为EBCDAFHIGJ,编程输出该树的后序遍历序列。
求代码，可重谢。

Answer 1

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef char type;

static int levels = 0;

struct node
{
type key;
node * left;
node * right;
};

node * fun(type arrLevel[], type arrMid[], int length, int beg , int end)
{
if(beg > end)return NULL;
int lb = beg, le, rb, re = end;
bool flag = false;

node * root = (node*)malloc(sizeof(node));
if(beg == end)
{
root->key = arrMid[beg];
root->left = root->right = NULL;
return root;
}
for(levels = 0; levels < length; levels ++)
{
for(int i = beg; i < end; i ++)
{
if(arrMid[i] == arrLevel[levels])
{
le = i -1;
rb = i + 1;
flag = true;
root->key = arrLevel[levels];
break; //找到
}
}
if(flag)break;
}
root->left = fun(arrLevel, arrMid, length, lb, le);
root->right = fun(arrLevel, arrMid, length, rb, re);
return root;
}

/*-----后序遍历------*/
void post_traverse(node *r)
{
if(r){
post_traverse(r->left);
post_traverse(r->right);
printf("%c ",r->key);
}

printf("\n");
}

/*-----后序析构------*/
void post_destroy(node* &r)
{
if(r) {
post_destroy(r->left);
post_destroy(r->right);

free(r);
r = 0;
}
}

int main()
{
const int MAX = 20;

type arrLevel[] = "ABECDFGHIJ";
type arrMid[] = "EBCDAFHIGJ";

int length = strlen(arrLevel);
node * root = fun(arrLevel, arrMid, length, 0, length-1);

printf("后序遍历输出二叉树: ");
post_traverse(root);
post_destroy(root);

getchar();
return 0;
}本回答被提问者和网友采纳