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