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

　2007-03-16 21:57:38　来源：WEB开发网　　　

核心提示：本文示例源代码或素材下载一、前言:我的一个同事拿来她老公的远程教育的考试题，叫大家帮着做，根据前序和中序序列生成二叉树，我写了这道，源码通过VC6编译链接，批评我，让我进步，执行成功，呵呵；）题目就是给出了一个二叉树的前序序列（ABDCEGF）和中序序列(DBAEGCF)

本文示例源代码或素材下载

一、前言:

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

下面是主函数

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