下面只是给出第一种情况的程序
#include "stdafx.h"
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <iterator>
using std::vector;
using namespace std;
typedef vector<int>::const_iterator it_vect;
struct node
{
int data;
node* left ;
node* right;
};
node* build_btee(const vector<int>& preorder,const vector<int>& inorder);
int _tmain(int argc, _TCHAR* argv[])
{
//srand((unsigned) time(NULL));
//int a1[]={8,3,1,5,10,11,12};
//int a2[]={1,3,5,8,11,10,12};
//
vector<int> preorder;
copy( istream_iterator<int>(cin) ,istream_iterator<int>(),back_inserter(preorder));
cin.clear();//在STL中，规定需要为每个使用了的输入流迭代器调用cin.clear()将绑定消除*/
vector<int> inorder ;
copy( istream_iterator<int>(cin) ,istream_iterator<int>(),back_inserter(inorder));
//vector<int> postorder(a3,a3+5);
// given preorder and inorder ,rebulding the binary tree;
node* root=build_btee(preorder,inorder);
//系统结束删除new的内存 ，偷懒了
return 0;
}
node* build_btree( it_vect it1,it_vect it1_end,it_vect it2,it_vect it2_end)
{
if(it1==it1_end||it2_end==it2) return 0;
node* root =new node;
root->data =(*it1);
root->left =0;
root->right =0;
int num =0;
while(it2!=it2_end&& root->data!=(*it2))
{
++it2
;
++num;
}
if(it2!=it2_end&&root->data == *it2)//一定要把it2!=it2_end 放在前面 不然后面的*it 越界
{
root->left=build_btree(it1+1,it1+num+1,it2-num,it2);//保持接口的一致性用前闭后开区间
root->right=build_btree(it1+num+1,it1_end,it2+1,it2_end);
}
else
{
cout<<"invalid data"<<endl;
exit(EXIT_FAILURE);
}
return root;
}
node* build_btee(const vector<int>& preorder,const vector<int>& inorder)
{
//assertion
if(preorder.empty() ||inorder.empty()||preorder.size()!=inorder.size())
{
cout<<"invalid input";
exit(EXIT_FAILURE);
}
//改变接口便于递归
return build_btree( preorder.begin(),preorder.end(), inorder.begin(),inorder.end());
}