二叉树--先序中序遍历求后序遍历

先序遍历：根 左 右

中序遍历：左 根 右

后序遍历：左 右 根

我们可以先从先序遍历中找到根节点，由于知道了根节点那么可以依靠中序遍历找到左子树，右子树。这样再去先序遍历中找到左子树的根节点，然后再依靠中序遍历找到左子树的左子树（右子树同理）。这样层层递归就能还原二叉树。之后求出后序遍历。

感谢原博主http://www.cnblogs.com/rain-lei/p/3576796.html 一开始递归不会写，看了博主的发现其实很简单。注意还原二叉树时return root。

#include<stdio.h>
int n;
typedef struct btnode{int data;struct btnode *left;struct btnode *right;
}treenode;  　　　　　　　　　　　　　　　　//定义二叉树节点
int preorder[1001];　　　　　　　　　　　 //先序遍历
int inorder[1001];　　　　　　　　　　　　//中序遍历　　treenode *gettree(int prel,int prer,int inl,int inr){   //根据先序中序还原二叉树if(prel>prer)return NULL;treenode *root;     root=new treenode;root->data=preorder[prel];if(prel==prer){root->left=NULL;root->right=NULL;return root;}int temp;　　//记录根节点在中序遍历中的位置for(int i=1;i<=inr;i++)if(inorder[i]==preorder[prel]){temp=i;break;}root->left=gettree(prel+1,prel+(temp-inl),inl,temp-1); //还原左子树root->right=gettree(prel+(temp-inl)+1,prer,temp+1,inr);//还原右子树return root;
}
void postorder(treenode *t){          //后序遍历二叉树if(t!=NULL){postorder(t->left);postorder(t->right);printf("%d\n",t->data);}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&preorder[i]);for(int i=1;i<=n;i++)scanf("%d",&inorder[i]);treenode *tree=gettree(1,n,1,n);postorder(tree);
}