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

VCkbase.com/document/image/paragraph.gif" width=14> 一、前言:
我的一个同事拿来她老公的远程教育的考试题，叫大家帮着做，我写了这道，源码通过VC6编译链接，执行成功，呵呵；）题目就是给出了一个二叉树的前序序列（ABDCEGF）和中序序列(DBAEGCF)，要求根据这两个输入完成一个二叉树，但没有指定用什么方式，所以我用了最笨拙的顺序存储二叉树，不过用了map来保存二叉树。题目还要求形成二叉树后可以遍历这个二叉树，由于三种遍历只是顺序不同，所以我只实现了后序遍历，何况输入就是前序和中序。；）本来应该用template做的，不过同事要求不要用复杂的C++语法，以免姐夫难以应对老师的提问，所以我只用了string来保存数据。本人是数学系毕业的，数据结构当时开课只学了几章，所以请朋友们不要笑话我。:> 我想这个程序唯一能够对您有帮助的地方就是提醒您不要将递归的函数做成inline的，希望大家干活儿的时候多注意这点儿。非常渴望朋友们和我联系email，批评我，让我进步，谢谢。:>

VCkbase.com/document/image/paragraph.gif" width=14> 二、代码实现:

// 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;
}

VCkbase.com/document/image/paragraph.gif" width=14> 三、运行结果:

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