繁體中文当前位置: 首页 > 图文教程 > 开发语言 > VC++ > 根据前序和中序序列生成二叉树
- VC++
- 如何有效地使用对话框
- 一个定制CFileDialog对话框的实例
- XP风格复活节彩蛋的实现
- 程序界面多模式显示的实现
- 改变视图单调的背景
- 使窗体拥有透明效果的API
- 《电子尺》V1.02程序开发实例
- 美化你的应用程序的外观界面
- 个人考勤软件开发实例
- 使用VC6.0实现窗口的任意分割
- 如何让一个打开的文档成为活动文档
- 创建非矩形窗口的简单方法
- 轻松实现类VC界面
- 视图的缩放的完整论述
- 如何获得另一个应用程序窗口中的文本
- 如何发送命令到文档对象
- 动画窗口的实现－VC++实例一则
- 如何在其他程序的窗口上创建按钮并使之能响应
- 如何在基于对话框的程序中动态设置鼠标指针
- 扩展COleDropTarget类来支持任意窗口拖放 - 作者:王加宝
VC++ 中的 根据前序和中序序列生成二叉树
出处:互联网 整理: 软晨网（RuanChen.com） 发布: 2009-10-30 浏览: 59 ::
收藏到网摘: n/a
根据前序和中序序列生成二叉树  一、前言:我的一个同事拿来她老公的远程教育的考试题，叫大家帮着做，我写了这道，源码通过VC6编译链接，执行成功，呵呵；）题目就是给出了一个二叉树的前序序列（ABDCEGF）和中序序列(DBAEGCF)，要求根据这两个输入完成一个二叉树，但没有指定用什么方式，所以我用了最笨拙的顺序存储二叉树，不过用了map来保存二叉树。题目还要求形成二叉树后可以遍历这个二叉树，由于三种遍历只是顺序不同，所以我只实现了后序遍历，何况输入就是前序和中序。；）本来应该用template做的，不过同事要求不要用复杂的C++语法，以免姐夫难以应对老师的提问，所以我只用了string来保存数据。本人是数学系毕业的，数据结构当时开课只学了几章，所以请朋友们不要笑话我。:> 我想这个程序唯一能够对您有帮助的地方就是提醒您不要将递归的函数做成inline的，希望大家干活儿的时候多注意这点儿。非常渴望朋友们和我联系email，批评我，让我进步，谢谢。:> 二、代码实现: // BTree3.cpp : Defines the entry point for the console application.//// AUTHOR: Song Ke// EMAIL: [email protected]// 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_BinaryTr |
评论 (0) 