由二叉树的前序和中序如何得到二叉树的后序呢？

首先得明白什么是前序、中序、后序。

二叉树前序：遍历顺序为，根节点、左子树、右子树；中序：遍历顺序为，左子树、根节点、右子树；后序：遍历顺序为，左子树、右子树、根节点

可以发现，二叉树前序中的第一个节点为树的根节点root，然后找出root在中序里面的位置，就可以把前序和中序分别划分为左、右子树两个部分，然后递归调用即可。

#include<iostream>usingnamespacestd;template<classT>structBinaryTreeNode{T_data;BinaryTreeNode*_left;BinaryTreeNode*_right;BinaryTreeNode(constT&x):_data(x),_left(NULL),_right(NULL){}};template<classT>classBinaryTree{protected:BinaryTreeNode<T>*_root;protected:void_PreOrder(BinaryTreeNode<T>*root){if(root!=NULL){cout<<root->_data<<"";_PreOrder(root->_left);_PreOrder(root->_right);}return;}BinaryTreeNode<T>*_CreateBinary(char*preOrder,char*inOrder,intlength){BinaryTreeNode<T>*root=NULL;if(length==0)returnNULL;inttmp=*preOrder;intindex=0;while(index<length&&inOrder[index]!=tmp)index++;if(index<length){root=newBinaryTreeNode<T>(tmp-'0');root->_left=_CreateBinary(preOrder+1,inOrder,index);root->_right=_CreateBinary(preOrder+index+1,inOrder+index+1,length-index-1);}returnroot;}void_Clear(BinaryTreeNode<T>*root){if(root){_Clear(root->_left);_Clear(root->_right);deleteroot;}}public:BinaryTree():_root(NULL){}~BinaryTree(){_Clear(_root);_root=NULL;}voidPreOrder(){_PreOrder(_root);cout<<endl;}voidCreateBinaryTree(char*preOrder,char*inOrder){intlength=strlen(preOrder);_root=_CreateBinary(preOrder,inOrder,length);}};voidTest1(){char*preOrder="12473568";char*inOrder="47215386";BinaryTree<int>bt;bt.CreateBinaryTree(preOrder,inOrder);bt.PreOrder();}