www.gusucode.com > VC++由前序、中序序列生成二叉树并遍历源码程序 > VC++由前序、中序序列生成二叉树并遍历源码程序/code/BTree3.cpp
// BTree3.cpp : Defines the entry point for the console application. // Download by http://www.NewXing.com // 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); } // generate the binary tree void generate(); void post_out(); private: // get left or right subtree for iteration void _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 iterate void _inorder_iterate(const vector< pair<string, int> >& v); // using postorder iterate void _preorder_iterate(const vector< pair<string, int> >& v); // using postorder iterate int _i_generate; // point to current element of preorder // mark the elements in inorders, and recurse the func in. // bLeft == true or false is right void _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 out void _out(const string& explain, const vector<string>& vec); vector<string> _pre; // preorder sequence as known vector<string> _in; // inorder sequence as known vector<string> _post; // postorder sequence as request vector< pair<string, int> > _s; // string, position as ordinal saving map<int, string> _sm; // assistant for making subtree when postorder iterate vector<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_BinaryTree::generate() { cout << "THE BTREE IS " << endl; string node( _pre[_i_generate++] ); // get the first elem of preorder int jj = 1; _kesongemini(node, jj, true, 0, _in); } void SongKe_BinaryTree::_kesongemini(bool bLeft, int iNode, const vector<string>& v) { string node( _pre[_i_generate++] ); // get a elem of preorder in turn int jj = bLeft ? 2*iNode /* left */ : 2*iNode+1 /* right */; _kesongemini(node, jj, bLeft, iNode, v); } void SongKe_BinaryTree::_kesongemini(const string& node, int jj, bool bLeft, int iNode, const vector<string>& v) { _s.push_back( make_pair(node, jj) ); // get a node of the betree in turn _sm[ jj ] = node; // assistant for postorder iterate later :) _si.push_back( jj ); // assistant for postorder iterate later :) cout << "\t\t" << (*(_s.end()-1)).first << " " << (*(_s.end()-1)).second << endl; vector<string> l, r; bool b = false; // to find the node in the inorder sequence for ( vector<string>::const_iterator i = v.begin(); i<v.end(); ++i ) { if ( !b && *i != node ) // left subtree { l.push_back(*i); } else if ( !b && *i == node ) // backbone found here { b = true; } else if ( b && *i != node ) // right subtree { r.push_back(*i); } } if ( !l.empty() ) _kesongemini(true, jj, l); // left subtree if ( !r.empty() ) _kesongemini(false, jj, r); // right subtree } void SongKe_BinaryTree::_get_subtree(int iNode, vector< pair<string, int> >& v) { vector<int>::iterator iter; iter = find( _si.begin(), _si.end(), iNode); // the header node self if ( iter != _si.end() ) { v.push_back( make_pair( _sm[ iNode ], iNode ) ); } int jj = iNode*2; // left subtree iter = find( _si.begin(), _si.end(), jj); if ( iter != _si.end() ) { v.push_back( make_pair( _sm[ jj ], jj ) ); _get_subtree( jj, v ); } ++jj; // e.q. iNode*2+1 // right subtree iter = find( _si.begin(), _si.end(), jj); if ( iter != _si.end() ) { v.push_back( make_pair( _sm[ jj ], jj ) ); _get_subtree( jj, v ); } } void SongKe_BinaryTree::_get_subtree(bool bLeft, int iNode, vector< pair<string, int> >& v) { _get_subtree(bLeft ? iNode*2 : iNode*2+1, v); } void SongKe_BinaryTree::_postorder_iterate(const vector< pair<string, int> >& v) { vector< pair<string, int> > l, r; pair<string, int> f = *v.begin(); // generate the new subtree l and r _get_subtree(true, f.second, l); _get_subtree(false, f.second, r); // postorder algorithm if ( !l.empty() ) _postorder_iterate(l); if ( !r.empty() ) _postorder_iterate(r); _post.push_back( f.first ); } void SongKe_BinaryTree::post_out() { _postorder_iterate( _s ); _out("POSTORDER : ", _post); } // MAIN ENTRANCE int main(int argc, char* argv[]) { SongKe_BinaryTree tree; tree.pre_insert( "A" ); // preorder tree.pre_insert( "B" ); tree.pre_insert( "D" ); tree.pre_insert( "C" ); tree.pre_insert( "E" ); tree.pre_insert( "G" ); tree.pre_insert( "F" ); tree.pre_out(); // preorder to show tree.in_insert( "D" ); // inorder tree.in_insert( "B" ); tree.in_insert( "A" ); tree.in_insert( "E" ); tree.in_insert( "G" ); tree.in_insert( "C" ); tree.in_insert( "F" ); tree.in_out(); // inorder to show tree.generate(); // generate the btree tree.post_out(); // postorder using btree return 0; }