根据前序和中序序列生成二叉树
作者:宋科
我的一个同事拿来她老公的远程教育的考试题，叫大家帮着做，我写了这道，源码通过VC6编译链接，执行成功，呵呵；）题目就是给出了一个二叉树的前序序列（ABDCEGF）和中序序列(DBAEGCF)，要求根据这两个输入完成一个二叉树，但没有指定用什么方式，所以我用了最笨拙的顺序存储二叉树，不过用了map来保存二叉树。题目还要求形成二叉树后可以遍历这个二叉树，由于三种遍历只是顺序不同，所以我只实现了后序遍历，何况输入就是前序和中序。；）本来应该用template做的，不过同事要求不要用复杂的C++语法，以免姐夫难以应对老师的提问，所以我只用了string来保存数据。本人是数学系毕业的，数据结构当时开课只学了几章，所以请朋友们不要笑话我。:>
我想这个程序唯一能够对您有帮助的地方就是提醒您不要将递归的函数做成inline的，希望大家干活儿的时候多注意这点儿。非常渴望朋友们和我联系email，批评我，让我进步，谢谢。:>
// 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 tree
void generate();
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);
}
下面是主函数
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;
}
PREORDER : A B D C E G F
INORDER : D B A E G C F
THE BTREE IS
A 1
B 2
D 4
C 3
E 6
G 13
F 7
POSTORDER : D B G E F C A
