本文共 1912 字，大约阅读时间需要 6 分钟。
二叉树后序遍历
接收二叉树前序序列和中序序列(各元素各不相同)，输出该二叉树的后序序列。
格式
输入格式
输入有三行：
第一行为数字n。
第二行有n个数字，表示二叉树的前序遍历。
第三行有n个数字，表示二叉树的中序遍历。
输出格式
输出一行，表示该二叉树的后序遍历序列。
样例
输入
5
1 2 4 5 3
4 2 5 1 3
输出
4 5 2 3 1
#include using namespace std;template struct binaryTreeNode{ T element;int leaves; binaryTreeNode *leftChild,*rightChild; //左子树和右子树 };template void erase(binaryTreeNode *& proot){ if(proot!=NULL) { erase(proot->leftChild); erase(proot->rightChild); delete proot; proot=NULL; }}template class binaryTree{ public: binaryTree(){ root=NULL;}//构造函数 ~binaryTree(){ erase(root);}//析构函数 void postOrder(binaryTreeNode * t); binaryTreeNode * makeTree(T* preOrder,T* inOrder, int P0,int Pn,int I0,int In);//中序遍历和前序遍历数组 private: binaryTreeNode *root; static void (*visit)(binaryTreeNode *); };template void (*binaryTree ::visit)(binaryTreeNode *);template void binaryTree ::postOrder(binaryTreeNode *t){ // Postorder traversal. if (t != NULL) { postOrder(t->leftChild); postOrder(t->rightChild); //binaryTree ::visit(t); cout< element<<" "; }}template binaryTreeNode * binaryTree ::makeTree(T* preOrder,T* inOrder, int P0,int Pn,int I0,int In){ int i; binaryTreeNode *tr=new binaryTreeNode ; tr->element=preOrder[P0]; tr->leftChild= NULL; tr->rightChild = NULL; if(P0==Pn&&I0==In)//只有一个元素时 return tr; //还原一棵树 for(i=I0;i<=In;i++) if(preOrder[P0]==inOrder[i]) break; int leftLength=i-I0;//左孩子数量 int rightLength=In-i;//右孩子数量 if(leftLength>0) tr->leftChild=makeTree(preOrder,inOrder,P0+1,P0+leftLength,I0,i-1); if(rightLength>0) tr->rightChild=makeTree(preOrder,inOrder,P0+leftLength+1,Pn,i+1,In); root=tr; return tr;}int main(){ binaryTree tre; int *preOrder,*inOrder,n; cin>>n; preOrder=new int[n]; inOrder=new int[n]; for(int i=0;i >preOrder[i]; for(int j=0;j >inOrder[j]; binaryTreeNode *p=tre.makeTree(preOrder,inOrder,0,n-1,0,n-1); tre.postOrder(p); return 0;}
转载地址：http://vfwzi.baihongyu.com/