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

根据前序和中序序列生成二叉树2010-11-16宋科一、前言:

我的一个同事拿来她老公的远程教育的考试题，叫大家帮着做，我写了这道，源码通过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 << "	";
   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 << "		" << （*（_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）;
}