#include
  
   
#include
   
     #include
    
      #include
     
       template
      
        class BinaryTree { public: struct TreeNode { Type data; TreeNode *leftchild, *rightchild; }; BinaryTree() {} ~BinaryTree(){} private: TreeNode *root; static TreeNode *_BuyNode() { TreeNode *p = (TreeNode *)malloc(sizeof(TreeNode)); assert(p != NULL); return p; } static int find(Type *is, const Type &x, int n) { for(int i = 0; i < n; ++i) { if(is[i] == x) return i; } return -1; } static TreeNode *CreatInPost(Type *post, Type *is, int n) { if(post == NULL || is == NULL || n ==0) return NULL; else { TreeNode *s = _BuyNode(); s->data = post[n-1]; int num = find(is, post[n-1], n); if(num == -1) exit(1); s->leftchild = CreatInPost(post, is,num);//此处放进去的是线序遍历的前num个 s->rightchild = CreatInPost(post+num, is+num +1, n-num-1);//此处减1是因为这是从后序遍历中找的每次最后一个数就被使用了，每次到这里就要将它除掉 return s; } } static void PreOrder(TreeNode *root) { if(root != NULL) { cout << root->data << " "; PreOrder(root->leftchild); PreOrder(root->rightchild); } } public: void Creat(Type *post, Type *is, int n) { if(post != NULL && is != NULL) root = CreatInPost(post, is, n); } void PreOrder() { PreOrder(root); cout << endl; } }; int main(void) { BinaryTree
       
         tree; int post[] = {34,56,67,45,23,89,78,12}; int is[] = {34,23,56,45,67,12,78,89}; int n = sizeof(post) / sizeof(post[0]); tree.Creat(post, is, n); tree.PreOrder(); return 0; }