willsun888
9/21/2013 - 3:18 AM

## 根据二叉树的前序和中序求后序

``````//============================================================================
// Name        : test.cpp
// Author      : will
// Version     :
// Description : Hello World in C++, Ansi-style
//============================================================================

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

typedef struct BinaryTreeNode_{
int value;
BinaryTreeNode_* left;
BinaryTreeNode_* right;
}BinaryTreeNode;

BinaryTreeNode* create(int* pre_start,int* pre_end,int* in_start,int* in_end){
int root_value = pre_start[0];
BinaryTreeNode* root = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
root->value = root_value;
root->left = root->right = NULL;

//root只有left的时候
if(pre_start == pre_end){
if(in_start == in_end && *pre_start == *in_start){
return root;
}else{
printf("input is invalid");
return NULL;
}
}

//求得中序中root的位置
int* in_root = in_start;
while(in_root <= in_end && *in_root != root_value){
++in_root;
}

//root只有left的时候
if(in_root == in_end && *in_root != root_value){
printf("input is invalid");
return NULL;
}

int left_len = in_root - in_start;

if(left_len > 0){
root->left = create(pre_start+1,pre_start+left_len,in_start,in_root-1);
}
if(left_len < pre_end - pre_start){
root->right = create(pre_start+left_len+1,pre_end,in_root+1,in_end);
}

return root;
}

BinaryTreeNode* createTree(int* preorder,int* inorder,int len){
if(preorder == NULL || inorder ==NULL || len <= 0){
return NULL;
}
return create(preorder,preorder+len-1,inorder,inorder+len-1);
}

void postOrder(BinaryTreeNode* root){
if(root){
if(root->left){
postOrder(root->left);
}
if(root->right){
postOrder(root->right);
}
printf("%d ",root->value);
}
}

int main(void)
{
int a[] = {1,2,4,7,3,5,6,8};
int b[] = {4,7,2,1,5,3,8,6};

BinaryTreeNode* root = createTree(a,b,8);
postOrder(root);
return EXIT_SUCCESS;
}
``````