数据结构课程设计二叉树.docx
《数据结构课程设计二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计二叉树.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构课程设计二叉树
数据结构课程设计报告
题目：
前序+中序构造二叉树的算法演示
学生姓名：
卜崇宇
学号：
2012014312
专业：
计算机科学与技术
班级：
计科1202
指导教师：
刘勇
2013年12月30日
目录
目录2
任务书3
【摘要】4
1．程序主要功能6
2.程序总体设计6
1）文件结构6
2）主要类7
3）程序结构7
3.程序详细设计8
3.1主窗体（CMylog:
:
Dialog）:
8
3.2窗体2_二叉树的后序输出和树的高度（D2:
:
Dialog）:
9
3.3窗体3_辅助功能（D11:
:
Dialog）:
9
3.4窗体4_构造过程（XP:
:
Dialog）:
9
4.运行结果9
5.附录：
（代码）14
任务书
课程名称
数据结构课程设计
设计题目
前序+中序构造二叉树的算法演示
指导教师
刘勇
时间
2013.12.30——2014.1.3
一、教学要求
二、设计资料及参数
三、设计要求及成果
学号最后2位%21+1所得结果对应的课设题目
如2012014452将选择20题
1 中国象棋
2 五子棋
3 链表的算法（构造、插入、删除、反转）演示
4 栈的算法（构造、入栈、出栈）演示
5 四则运算表达式的算法演示（用栈实现）
6 走迷宫的算法演示（用栈实现）
7 前序+中序构造二叉树的算法演示
8 哈夫曼树的算法演示
9 图的拓扑排序算法演示
10 图的关键路径算法演示
11 图的最短路径算法演示-迪杰斯特拉算法
12 图的最短路径算法演示-弗洛伊德算法
13 OJ做题情况分析：
班级总AC排名、宿舍总AC排名、2-8定律、做题时间点分布排名、周末做题比例
14 快速排序的算法演示
15 堆排序的算法演示
16 坦克大战
17 最小生成树算法演示-迪杰斯特拉算法
18 最小生成树算法演示-普利姆算法
19 平衡二叉树的算法演示
20 二叉排序树的算法演示
21 排序算法性能分析（选择、冒泡、插入、快速、堆排序、希尔排序、未排序因子）
以最短路径算法举例：
成绩 完成情况
D,C- 基本没有完成
C,C+ 用DOS界面基本完成算法，有明显BUG
B- 用DOS界面完成算法，数据量较小，没有明显BUG
B 用DOS界面完成算法，数据量较大，没有明显BUG
B+,A- 用MFC或者C#完成界面，数据量较大，没有明显BUG
A 用MFC或者C#完成界面，数据量较大，有应用背景，没有明显BUG，既能一步出结果，也能单步看过程
A+ 满足A的基础上，没有任何BUG，数据量大，功能完备，界面美观大方、考虑到代码重用性
以上是程序成绩，结合报告的成绩：
如果报告写得不好，降低1到2个档次
如果报告写的很好，则提升1到2个档次
报告写得好的标准有：
格式一致、分章分节有目录、没有错别字、有图有表有题注、图表在文字中有引用、有关键代码、有设计
算法20 功能20 界面15 问题3×5 报告30
四、进度安排
第一天选择课程设计题目，分析课题的要求，设计程序结构
第二天编程
第三天编程，写报告
第四天提交课程设计报告（打印稿及电子稿）
五、评分标准
1.根据平时上机考勤、表现和进度，教师将每天点名和检查
2.根据课程设计完成情况，必须有可运行的软件。
3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。
六、建议参考资料
【摘要】
本次课程设计我主要采用了树和二叉树，递归和非递归等的知识。
我采用MFC进行实现的，计算过程展现的活灵活现、操作方便和通俗易懂等，是本课设的主要特点。
通过本次课程设计，我对数据结构和MFC语言有了更深的理解，让我把学到的理论应用于具体实践中，锻炼了我各方面的能力，从而让我更快提高，本次课设很大程度上增加了我的自学能力和提高了专业知识水平。
前序+中序构造二叉树的算法演示具有以下功能：
1.通过前序和中序单步实现二叉树的构造，不符合的输入会有提示。
2.通过前序和中序一步实现二叉树的构造，不符合的输入会有提示。
3.在遍历过程中可以返回单步构造时的上一步。
4.一首轻音乐或者一个搞笑的图片会让人轻松片刻。
5.显示代码执行的过程。
6.操作方便，直接鼠标右击可点击菜单栏，选择不同的功能。
1．程序主要功能
程序的主要功能包括：
1）输入前序和中序，如果输入前序或者中序不能构成二叉树，不会像某些
程序一样面临崩溃，很人性化的给你提示。
2）通过前序和中序一步实现二叉树的构造，不符合的输入会有提示
3）在遍历过程中可以返回单步构造时的上一步。
4）一首轻音乐或者一个搞笑的图片会让人轻松片刻。
5）显示代码执行的过程。
6）操作方便，直接鼠标右击可点击菜单栏，选择不同的功能。
2.程序总体设计
1）文件结构
2）主要类/数据结构
#include"D2.h"
#include"D11.h"
#include"XP.h"
3）程序结构
classBITree
{
private:
treeroot;
intkeynum;
public:
BITree（）
voidJudge（char*pre,char*in）;//判断不符合的情况
voidSearch（char*pre,char*in）;//建立二叉树
voidPre（）;//前序确定位置
voidPost（）;//后序
intGetHight（）;//树的高度
}
ClassCMyDlg:
publicCDialog
{
public:
CMyDlg（CWnd*pParent=NULL）;//standardconstructor
voidDrawRect（intx1,intx2,intx3,intx4）;//画长方形
voidDrawLine（intx1,intx2,intx3,intx4）;//画线
voidDrawCir（intx1,intx2,intx3）;//画圆
voidFillBack（）;//填充背景
voidOnButton2（）;//一步生成图形
voidOnButton3（）;//单步生成图形
HBRUSHOnCtlColor（CDC*pDC,CWnd*pWnd,UINTnCtlColor）;
voidOnButton4（）;//重置
voidOnButton5（）;//上一步
voidOnMenuitem32774（）;//菜单函数关闭
voidOnMenuitem32786（）;//菜单函数音乐
}
classD2:
publicCDialog
{
public:
D2（CWnd*pParent=NULL）;
virtualvoidOnSetFont（CFont*pFont）;
protected:
virtualvoidDoDataExchange（CDataExchange*pDX）;
protected:
voidOnOK（）;
BOOLOnInitDialog（）;
voidOnPaint（）;
voidOnButton3（）;//关闭窗口
};
classD11:
publicCDialog
{
public:
D11（CWnd*pParent=NULL）;
virtualvoidDoDataExchange（CDataExchange*pDX）;
protected:
voidOnPaint（）;//显示一张图片
virtualBOOLOnInitDialog（）;
};
classXP:
publicCDialog
{
public:
XP（）CWnd*pParet=NULL）;
virtualvoidDoDataExchange（CDataExchange*pDX）;
protected:
voidOnPaint（）;//显示构造过程
virtualBOOLOnInitDialog（）;
};
3.程序详细设计
3.1主窗体:
（CMylog:
:
CDialog）
（1）voidDrawRect（intx1,intx2,intx3,intx4）;
根据四个值来画长方形，（x1,x2）长方形代表左上角的坐标，（x3,x4）代表长方形的长和宽。
此函数用于实现上一步的功能。
（2）voidDrawLine（intx1,intx2,intx3,intx4）;
根据直线的起始点和终止点来画直线。
其中，（x1,x2）是起始点坐标，（x3,x4）是终止点坐标。
（3）voidDrawCir（intx1,intx2,intx3）;
根据圆的圆心（x1,x2）和圆的半径x3画圆。
（4）voidFillBack（）;
自动填充背景，主要实现重置功能。
（5）voidOnButton2（）;
步生成图形的按钮函数，调用DrawRect（）,DrawLine（）,DrawCir（）数实现功能。
（6）voidOnButton3（）;
单步生成图形，调用DrawRect（）,DrawLine（）,DrawCir（）函数实现功能。
（7）voidOnButton4（）;
清空编辑框中的内容，重置二叉树。
调用MFC的类函数。
（8）voidOnButton5（）;
实现上一步
（9）voidOnMenuitem32774（）;
打开子对话框，其他的类似函数不在现实。
（10）voidOnMenuitem32786（）;
实现声音的关闭。
3.2窗体2:
（D2:
:
CDialog）
（1）voidOnPaint（）;
显示树的高度和后序遍历。
（2）voidOnButton3（）;
退出函数。
3.3窗体3：
（D11:
:
CDialog）
voidOnPaint（）;
显示恶搞图片。
3.4窗体4:
（XP:
:
CDialog）
voidOnPaint（）;
用于显示构造过程。
4.运行结果
各运行功能的截图。
图1.单步生成
图2.一步生成
图3.上一步
（1）
图4.上一步
（2）
图5.后序的实现
图6.人性化的提示
（1）
图7.人性化的提示
（2）
图8.比较过程
图9.帮助对话框
5.附录：
（关键代码）
/****（CMylog:
:
CDialog）****/
文件内容：
classBITree
{
private:
treeroot;
intkeynum;
public:
BITree（）
{
root=NULL;
keynum=1;
}
voidJudge（char*pre,char*in）
{
for（inti=0;i<100;i++）
po[i]='\0';
if（strlen（pre）!
=strlen（in））
{
MessageBox（NULL,"二叉树","您的输入有误！
请核查后继续！
",MB_OK）;
keynum=0;
}
}
voidMessage（）
{
MessageBox（NULL,"二叉树","您的输入有误！
请核查后继续！
",MB_OK）;
}
treeGetRoot（）
{
returnroot;
}
voidSearch（char*pre,char*in）
{
if（keynum!
=1）
Message（）;
else
root=Search（pre,in,strlen（in））;
}
treeSearch（char*pre,char*in,intn）
{
if（n==0||kx==0）
returnNULL;
treehead;
head=newBINode;
head->data=pre[0];
strcpy（pr1[pi],pre）;
strcpy（in1[pi],in）;
pi++;
inti;
for（i=0;iif（pre[0]==in[i]）
break;
if（i==n&&kx==1）
{
MessageBox（NULL,"二叉树","您的输入有误！
请核查后继续！
",MB_OK）;
keynum=0;
tp=tp1=0;
kx=0;
pi=0;
returnNULL;
}
else
{
treelchild=Search（pre+1,in,i）;
treerchild=Search（pre+i+1,in+i+1,n-i-1）;
head->left=lchild;
head->right=rchild;
returnhead;
}
}
intPow（）
{
intt=GetHight（）,k=1;
for（inti=0;i<=t;i++）
k*=2;
returnk*8;
}
voidPre（）
{
if（keynum!
=1&&kx!
=1）
Message（）;
else
Pre（root,Pow（）,600,200）;
}
voidPost（）
{
if（keynum!
=1&&kx!
=1）
Message（）;
else
Post（root）;
}
voidPost（BINode*&p）
{
if（p!
=NULL）
{
Post（p->left）;
Post（p->right）;
po[poi]=p->data;
poi++;
}
}
voidPre（BINode*&p,intt,intx,inty）
{
if（p!
=0）
{
ty[tp1].x=x;
ty[tp1].y=y;
ty[tp1].d=p->data;
tp1++;
intk=t/2;
if（p->left）
{
tx[tp].x=x;
tx[tp].y=y;
tx[tp].x1=x-k;
tx[tp++].y1=y+50;
}
Pre（p->left,k,x-k,y+50）;
if（p->right）
{
tx[tp].x=x;
tx[tp].y=y;
tx[tp].x1=x+k;
tx[tp++].y1=y+50;
}
Pre（p->right,k,x+k,y+50）;
}
}
intGetHight（）
{
returnGetHight（root）;
}
intGetHight（treep）
{
if（p==NULL||kx!
=1）
{
return0;
}
else
{
intt=GetHight（p->left）;
intt1=GetHight（p->right）;
if（t>t1）
return1+t;
else
return1+t1;
}
}
};
voidCMyDlg:
:
DrawLine（intx1,intx2,intx3,intx4）
{
CClientDCdc（this）;
dc.MoveTo（x1,x2）;//从当前点移动到画图起始点
dc.LineTo（x3,x4）;
dc.ReleaseAttribDC（）;
}
voidCMyDlg:
:
DrawRect（intx1,intx2,intx3,intx4）
{
HDChdc=:
:
GetDC（m_hWnd）;
CClientDCdc（this）;
CBrushbrush（RGB（0,0,0））;
//dc.Rectangle（x1,x2,x3,x4）;
dc.FillRect（CRect（x1,x2,x3,x4）,&brush）;
dc.ReleaseAttribDC（）;
}
voidCMyDlg:
:
DrawCir（intx1,intx2,intx3）
{
HDChdc=:
:
GetDC（m_hWnd）;
CClientDCdc（this）;
dc.Ellipse（x1-x3,x2-x3,x1+x3,x2+x3）;
dc.ReleaseAttribDC（）;
}
voidCMyDlg:
:
FillBack（）
{
CRectrect;
CPaintDCdc（this）;
GetClientRect（rect）;
dc.FillSolidRect（rect,RGB（189,250,200））;
}
voidCMyDlg:
:
OnButton4（）
{
CClientDCdc（this）;
CFontfont;
font.CreatePointFont（200,"楷书",NULL）;
CFont*pOldFont=dc.SelectObject（&font）;
dc.SetTextColor（RGB（0,0,0））;
TEXTMETRICtm;
dc.GetTextMetrics（&tm）;
HDChdc;
hdc=:
:
GetDC（m_hWnd）;dc.SetBkMode（TRANSPARENT）;
chara[100],b[100];
kx=1;
if（x==0）
{
BITreet;
UpdateData（true）;
strcpy（a,m_1）;
strcpy（b,m_2）;
t.Judge（a,b）;
t.Search（a,b）;
if（hight=t.GetHight（）&&t.GetHight（）>=6）
MessageBox（"树的高度需保持在6以内"）;
else
{
t.Pre（）;
hight=t.GetHight（）;
t.Post（）;
UpdateData（false）;
}
}
DrawLine（tx[x1].x,tx[x1].y+25,tx[x1].x1,tx[x1].y1+25）;
x1++;
}
****（D2:
:
CDialog）****/
文件内容：
voidD2:
:
OnPaint（）
{
CPaintDCdc（this）;
CRectrect;
GetClientRect（rect）;
dc.FillSolidRect（rect,RGB（189,250,200））;
harp[100];
CFontfont;
font.CreatePointFont（300,"楷体",NULL）;
CFont*pOldFont=dc.SelectObject（&font）;
dc.SetTextColor（RGB（0,0,0））;
TEXTMETRICtm;
dc.GetTextMetrics（&tm）;
HDChdc;
hdc=:
:
GetDC（m_hWnd）;dc.SetBkMode（TRANSPARENT）;
:
:
SelectObject（hdc,CreatePen（PS_SOLID,2,RGB（0,0,0）））;
dc.TextOut（400,25,"二叉树"）;
UpdateData（true）;
externcharpo[100];
externinthight;
chart[19];
if（hight>=1）
{
itoa（hight-1,t,10）;
m_2=t;
}
else
m_2="空白输入";
m_1=po;
UpdateData（false）;
}
****（D11:
:
CDialog）****/
文件内容：
voidD11:
:
OnPaint（）
升级会员 