这个的中序和后序是无法构成二叉树的,如果把后序改为DECBHGFA,此二叉树为
A
B F
C G
D E H
(分支打不出来,就是A是根结点,B、F分别为其左右子树,C为B的右子树,D、E分别为C的左右子树,G为F的右子树,H为G的左子树)
程序代码为
#include
#include
typedef struct node *tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};
tree_pointer tree=NULL;
char inorder[]="BDCEAFHG";
char postorder[]="DECBHGFA";
void in_order(tree_pointer ptr)
{
if(ptr){
in_order(ptr->left_child);
printf("%c",ptr->ch);
in_order(ptr->right_child);
}
}
tree_pointer create(int in_start,int in_end,int post_start,int post_end)
{
int left_in_start,left_in_end,right_in_start,right_in_end;
int left_post_start,left_post_end,right_post_start,right_post_end;
int i;
tree_pointer root=NULL;
if(in_end>=in_start){
root=(tree_pointer)malloc(sizeof(node));
for(i=in_start;i<=in_end;i++){
if(postorder[post_end]==inorder[i])
break;
}
left_in_start=in_start;
left_in_end=i-1;
right_in_start=i+1;
right_in_end=in_end;
left_post_start=post_start;
left_post_end=left_post_start+(left_in_end-left_in_start);
right_post_start=left_post_end+1;
right_post_end=post_end-1;
root->left_child=create(left_in_start,left_in_end,left_post_start,left_post_end);
root->right_child=create(right_in_start,right_in_end,right_post_start,right_post_end);
root->ch=postorder[post_end];
return root;
}
return NULL;
}
void main()
{
tree=create(0,7,0,7);
in_order(tree);
printf("\n");
}