根中与后根构造二叉树与二叉树的匹配替换数据结构课程设计.docx
《根中与后根构造二叉树与二叉树的匹配替换数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《根中与后根构造二叉树与二叉树的匹配替换数据结构课程设计.docx（18页珍藏版）》请在冰点文库上搜索。
根中与后根构造二叉树与二叉树的匹配替换数据结构课程设计
成绩
南京工程学院
课程设计说明书（论文）
题目中根与后根构造二叉树与二叉树的匹配替换
课程名称数据结构
院（系、部、中心）计算机工程学院
专业计算机科学与技术
班级计算机卓越131
学生姓名羌秀君
学号202130404
设计地点信息楼
指导教师叶核亚
设计起止时间：
2016年5月10日至2016年5月20日
一、课程设计目的和要求
目的：
深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。
在实践中培养独立分析问题和解决问题的作风和能力。
要求：
熟练运用C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。
通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。
二、题意说明及分析
题目要求采用中根和后根序列构造一颗二叉树，并匹配替换二叉树的子树。
中根和后根构造：
由于后根可以确定一颗树的根，而中根在知道根的情况下可以确定左右子树的序列，因此这样递归，中根和后根可以确定一颗唯一的二叉树。
匹配替换二叉树：
1.通过遍历二叉树找到关键树根值在待匹配树中首次出现的位置，返回节点地址。
2.判断以找到的节点为根的子树和带匹配的树是否相同，采用递归算法。
3.确定以找到根节点的子树与带匹配的树相同，然后删除以此为根节点的子树，然后再将带替换的树复制到删除的节点。
三、算法设计与分析
算法设计思路、数据结构描述、流程图等
中根和后根构造算法：
设数组inlist[]和lalist[]分别表示一颗二叉树的中根和后根序列，两序列长度均为n。
1.由后根遍历的次序可知，该二叉树的根是lalist[n-1]；改节点必定在中根次序中，设根节点在中根次序的第i个位置即inlist[i]=lalist[n-1]。
2.由中根遍历次序知，inlist[i]节点前的节点在根的左子树上，inlist[i]后的所有节点在根节点的右子树上。
因此，根的左子树由i个节点组成，子序列为：
左子树的后根次序lalist[0]....lalist[i-1]
左子树的中根次序inlist[0]...inlist[i-1]
根的右子树由n-j-1个节点，子序列为：
右子树的后根次序lalist[i]...lalist[n-2]
右子树的中根次序inlist[i+1]...inlist[n-1]
3.以此递归，可唯一确定一颗二叉树。
算法实现：
template
BinaryTree:
:
BinaryTree（Tlalist[],Tinlist[],intn）{
this->root=create（lalist,inlist,n-1,n-1,n,root）;
}
template
BinaryNode*BinaryTree:
:
create（Tlalist[],Tinlist[],intend,intinend,intn,BinaryNode*parent）{
BinaryNode*p=NULL;
if（n>0）
{
p=newBinaryNode（lalist[end]）;
inti=0;
while（i=inlist[inend-i]）
i++;
p->parent=parent;
p->right=create（lalist,inlist,end-1,inend,i,p）;
p->left=create（lalist,inlist,end-i-1,inend-i-1,n-i-1,p）;
}
returnp;
}
匹配替换二叉树算法：
通过遍历二叉树找到关键树根值在待匹配树中首次出现的位置，返回节点地址。
判断以找到的节点为根的子树和带匹配的树是否相同，采用递归算法。
确定以找到根节点的子树与带匹配的树相同，然后删除以此为根节点的子树，然后再将带替换的树复制到删除的节点。
算法实现：
//查找根节点
template
BinaryNode*BinaryTree:
:
searchhead（BinaryNode*q,BinaryNode*p）{
BinaryNode*m=NULL;
if（q!
=NULL&&p!
=NULL）{
if（q->data==p->data）
{
returnp;
}
if（（m=searchhead（q->left,p））==NULL）
m=searchhead（q->right,p）;
}
returnm;
}
//查找子树
template
BinaryNode*BinaryTree:
:
searchone（BinaryTree&bintree）{
BinaryNode*p=searchhead（root,bintree.root）;
if（p!
=NULL）{
if（matchtree（p,bintree.root））
returnp;
else
returnNULL;
}
else
returnp;
}
//匹配子树
template
boolBinaryTree:
:
matchtree（BinaryNode*p,BinaryNode*q）{
return（p==NULL&&q==NULL）||（（q!
=NULL&&p!
=NULL）&&（p->data==q->data））&&（matchtree（p->left,q->left）&&matchtree（p->right,q->right））;
}
四、源程序
1.二叉树节点类
template
classBinaryNode{
public:
Tdata;//数据域
BinaryNode*left,*right,*parent;//指针域，分别指向左右孩子节点
//构造函数
BinaryNode（Tdata,BinaryNode*left=NULL,BinaryNode*right=NULL,BinaryNode*parent=NULL）{
this->data=data;
this->left=left;
this->right=right;
this->parent=parent;
}
};
二叉树类
#include
usingnamespacestd;
#include"BinaryTreeNode.h"
template
classBinaryTree{
public:
BinaryNode*root;
BinaryTree（）;//构造空二叉树
BinaryTree（Tlalist[],Tinlist[],intn）;//以中根和后根序列构造二叉树
~BinaryTree（）;//析构
boolempty（）;//判断是否为空二叉树
friendostream&operator<<<>（ostream&out,BinaryTree&）;//输出
voidpreOrder（）;//输出先根次序遍历序列
stringgetinOrder（BinaryNode*）;//获得中根次序遍历的字符串
stringgetpostOrder（BinaryNode*）;//获得后根次序遍历的字符串
voidremove（BinaryNode*parent,boolleftchild）;//删除parent节点的左或右子树
BinaryNode*searchone（BinaryTree&）;//查找子树
BinaryNode*searchhead（BinaryNode*q,Tkey）;//查找头结点
boolmatchtree（BinaryNode*p,BinaryNode*q）;
voiddestroy（BinaryNode*p）;
boolreplace（BinaryTree&key,BinaryTree&re）;
private:
voidpreOrder（BinaryNode*p）;//先根次序遍历以p节点为根的子树
voidpostOrder（BinaryNode*p,string&str）;//后根
voidinOrder（BinaryNode*p,string&str）;//中根次序遍历以p节点为根的子树
BinaryNode*create（Tlalist[],Tinlist[],intend,intinend,intn,BinaryNode*）;
BinaryNode*copy（BinaryNode*）;
};
//析构
template
BinaryTree:
:
~BinaryTree（）
{
destroy（root）;
}
//判断树是否为空
template
boolBinaryTree:
:
empty（）
{
returnthis->root==NULL;
}
//构造空二叉树
template
BinaryTree:
:
BinaryTree（）
{
this->root=NULL;
}
//输出先根次序遍历的序列
template
ostream&operator<<<>（ostream&out,BinaryTree&btree）
{
out<<"先根次序遍历二叉树";
btree.preOrder（btree.root）;
out<returnout;
}
template
voidBinaryTree:
:
preOrder（BinaryNode*p）
{
if（p==NULL）
{
cout<<"^";
}
else
{
cout<data<<"";
preOrder（p->left）;
preOrder（p->right）;
}
}
//中根和后根构造二叉树
template
BinaryTree:
:
BinaryTree（Tlalist[],Tinlist[],intn）
{
this->root=create（lalist,inlist,n-1,n-1,n,root）;
}
template
BinaryNode*BinaryTree:
:
create（Tlalist[],Tinlist[],intend,intinend,intn,BinaryNode*parent）
{
BinaryNode*p=NULL;
if（n>0）
{
p=newBinaryNode（lalist[end]）;
inti=0;
while（i=inlist[inend-i]）
i++;
p->parent=parent;
p->right=create（lalist,inlist,end-1,inend,i,p）;
p->left=create（lalist,inlist,end-i-1,inend-i-1,n-i-1,p）;
}
returnp;
}
//删除子树
template
voidBinaryTree:
:
destroy（BinaryNode*p）
{
if（p!
=NULL）
{
destroy（p->left）;
destroy（p->right）;
deletep;
}
}
//查找根节点
template
BinaryNode*BinaryTree:
:
searchhead（BinaryNode*q,Tkey）
{
BinaryNode*m=NULL;
if（q!
=NULL）
{
if（q->data==key）
{
returnq;
}
if（（m=searchhead（q->left,key））==NULL）
m=searchhead（q->right,key）;
}
returnm;
}
//查找子树
template
BinaryNode*BinaryTree:
:
searchone（BinaryTree&bintree）
{
BinaryNode*p=searchhead（root,bintree.root->data）;
if（p!
=NULL）
{
if（matchtree（p,bintree.root））
returnp;
else
returnNULL;
}
else
returnp;
}
//匹配子树
template
boolBinaryTree:
:
matchtree（BinaryNode*p,BinaryNode*q）
{
if（q==NULL&&p==NULL）
returntrue;
if（p==NULL||q==NULL）
returnfalse;
if（p->data!
=q->data）
returnfalse;
return（matchtree（p->left,q->left）&&matchtree（p->right,q->right））;
}
//替换
template
boolBinaryTree:
:
replace（BinaryTree&key,BinaryTree&re）
{
BinaryNode*p=searchone（key）;
if（p!
=NULL）
{
//替换（搜到的头不销毁）
destroy（p->left）;
destroy（p->right）;
p->data=re.root->data;
p->left=copy（re.root->left）;
p->right=copy（re.root->right）;
returntrue;
}
else
returnNULL;
}
//二叉树复制
template
BinaryNode*BinaryTree:
:
copy（BinaryNode*p）
{
BinaryNode*q=NULL;
if（p!
=NULL）
{
q=newBinaryNode（p->data）;
q->parent=p->parent;
q->left=copy（p->left）;
q->right=copy（p->right）;
}
returnq;
}
//获得中根遍历下的字符串
template
stringBinaryTree:
:
getinOrder（BinaryNode*p）
{
stringstr;
inOrder（p,str）;
returnstr;
}
template
voidBinaryTree:
:
inOrder（BinaryNode*p,string&str）
{
if（p!
=NULL）
{
inOrder（p->left,str）;
str+=p->data;
inOrder（p->right,str）;
}
}
//获得后根遍历下的字符串
template
stringBinaryTree:
:
getpostOrder（BinaryNode*p）
{
stringstr;
postOrder（p,str）;
returnstr;
}
template
voidBinaryTree:
:
postOrder（BinaryNode*p,string&str）
{
if（p!
=NULL）
{
postOrder（p->left,str）;
postOrder（p->right,str）;
str+=p->data;
}
}
主cpp文件
#include"BinaryTree.h"
#include
#include
#include
usingnamespacestd;
intmain（）{
charlalist[]="GDBEHFCA";
charinlist[]="DGBAECHF";
charinkey[]="ECHF";
charlakey[]="EHFC";
charinrep[]="LJMIK";
charlarep[]="LMJKI";
BinaryTreetree（lalist,inlist,8）;
BinaryTreekeytree（lakey,inkey,4）;
BinaryTreereptree（larep,inrep,5）;
cout<cout<<"二叉关键子树"<cout<<"待替换的子树"<cout<<"替换后"<tree.replace（keytree,reptree）;
cout<return0;
}
五、结果及分析
结果：
分析：
1.通过中根charlalist[]="GDBEHFCA";后根charinlist[]="DGBAECHF";构造一颗二叉树TREE。
2.通过中根charinkey[]="ECHF";后根charlakey[]="EHFC";构造一颗关键二叉树KEYTREE。
3.通过中根charinrep[]="LJMIK";后根charlarep[]="LMJKI";构造一颗待替换的树REPTREE；
4.通过KEYTREE的根在TREE中找到对应的地址，然后判断通过找到以此地址为根的子树是否与KEYTREE相同。
5.相同将删除以找到的地址为根的子树。
6.复制REPTREE到TREE删除的子树上。
六、总结与思考
1，首先一开始对这个题目没有思路，可能是书上代码不熟悉的原因，所以我在做实验之前，把书上老师上课讲的二叉树这边的功能都实现了一遍，对二叉树的操作有了最基本的操作了解之后，慢慢入门。
2，然后我仔细分析了这条题目，要用到的函数都写了下来，把要实现的操作都用草图的形式画了出来，这样我就对我该先做什么，后做什么，这种目的实现的方法有了自己的思路。
3，我在着手写程序的时候，出现了很多问题，在中后根构造上花了不少时间，总之还是自己不够细心。
4，经过自己的努力，我把那些应该用到的功能函数都实现好了。
还有其他地方也进行了改进，实验终于成功了。
5，总的来说，做实验还是要边写代码边画图，这样思路清晰，还要细心一点，不能忘记任何一个步奏，仔细思考了一下，觉得一方面要多写多实践增加自己的经验，另一方面要多思考，多调试，要能看懂错误，并迅速想到解决方案，这需要长时间的积累。
还有就是实在想不出来的问题，可以和同学进行交流探讨，说不定问题就解决了。
毕竟一个人的能力是有限的，通过交流可以共同学习，互相进步。
教师评语：
目录
第1章项目概况与项目建设的必要性1
1.1项目概况1
1.1.1项目名称1
1.1.2项目主管单位1
1.1.3项目建设单位1
1.1.4项目建设单位负责人1
1.1.5项目建设性质1
1.1.6项目建设地点1
1.1.7项目建设期2
1.1.8项目建设内容和规模2
1.1.9项目投资估算2
1.1.10项目资金筹措方案3
1.1.11项目建设效益3
1.2项目建设背景3
1.2.1地理气候条件3
1.2.2工业园区发展规划4
1.2.3工业区已具产业规模5
1.2.4项目提出的理由与过程6
1.3项目建设必要性分析9
1.3.1某某市“十一五发展规划”的要求9
1.3.2某某市总体规划的要求10
1.3.3某某市经济发展的要求11
1.3.4园区发展的要求12
1.4项目社会效益分析13
1.4.1扩大内需，促进经济增长13
1.4.2改善工业园区投资环境14
1.4.3促进生产发展和提高人民生活水平15
1.4.4促进园区的可持续发展15
1.4.5带动园区周边土地增值及房地产发展16
1.5项目建设可行性分析17
1.5.1政府支持17
1.5.2资金支持17
1.5.3建设条件满足18
1.6结论18
第2章项目建设内容及方案19
2.1项目建设内容19
2.1.1项目建设地点19
2.1.2项目建设内容19
2.1.3项目建设规模19
2.2项目建设方案20
2.2.1项目建设目标20
2.2.2项目建设方案20
2.2.3项目功能分析23
2.3项目建设原则26
2.3.1以人为本与可持续发展的原则26
2.3.2集聚发展原则27
2.3.3因地制宜原则27
2.3.4环境保护原则27
2.3.5节能降耗原则27
2.3.6抗震原则28
2.4建筑造型28
第3章项目建设和进度安排29
3.1项目工程建设管理29
升级会员 