根据前序和中序序列生成二叉树

【 tulaoshi.com - C语言心得技巧 】

根据前序和中序序列生成二叉树
作者:宋科
作者主页:kesongemini.diy.163.com

一、前言:

二、代码实现:

// BTree3.cpp : Defines the entry point for the console application.//// AUTHOR:  Song Ke// EMAIL: kesongemini@vip.163.com// HOMEPAGE: http://kesongemini.diy.163.com// QQ: 123588179// COMPANY: www.etonglian.com// AIM: programmed by SongKe 2002/12/16 night at home //for Sister An Ning''s her husband''s exam-3://known as preorder(ABDCEGF) and inorder(DBAEGCF) sequence//to request for the btree and postorder sequence// STATUS: finished!// METHOD: the binary tree SongKe_BinaryTree with ordinal saving// TEST: succeeded by compile and link// PLATFORM: VC++6.0 + sp5 //MS-STL NOT SGI-STL!//at Windows2000 + sp3 // NOTE: DON''T WRITE THE RECURSION FUNCTION AS INLINE FUNCTION!#include "stdafx.h"#include <vector>#include <string>#include <iostream>#include <utility>#include <map>#include <algorithm>using namespace std;class SongKe_BinaryTree{public:SongKe_BinaryTree() : _i_generate(0) {}~SongKe_BinaryTree() {}void pre_insert(const string& s) { _pre.push_back(s); }void in_insert(const string& s) { _in.push_back(s); }void pre_out(){ _out("PREORDER : ", _pre); }void in_out(){ _out("INORDER : ", _in); }void post_out();// generate the binary treevoid generate();private:// get left or right subtree for iterationvoid _get_subtree(int iNode, vector< pair<string, int> >& v);void _get_subtree(bool bLeft, int iNode, vector< pair<string, int> >& v);void _postorder_iterate(const vector< pair<string, int> >& v);// postorder iteratevoid _inorder_iterate(const vector< pair<string, int> >& v);// using postorder iteratevoid _preorder_iterate(const vector< pair<string, int> >& v);// using postorder iterateint _i_generate; // point to current element of preorder// mark the elements in inorders, and recurse the func in.// bLeft == true or false is rightvoid _kesongemini(bool bLeft, int iNode, const vector<string>& v);void _kesongemini(const string& node, int jj, bool bLeft, int iNode, const vector<string>& v);// print outvoid _out(const string& explain, const vector<string>& vec);vector<string> _pre; // preorder sequence as knownvector<string> _in; // inorder sequence as knownvector<string> _post; // postorder sequence as requestvector< pair<string, int> > _s; // string, position as ordinal savingmap<int, string> _sm; // assistant for making subtree when postorder iteratevector<int> _si; // assistant for making subtree when postorder iterate};void SongKe_BinaryTree::_out(const string& explain, const vector<string>& vec){cout << explain << "t";for(vector<string>::const_iterator i = vec.begin(); i != vec.end(); ++i){cout << *i << " ";}cout << endl;}void SongKe_BinaryTr