中根与后根构造二叉树与二叉树的匹配替换数据结构课程设计Word.docx
《中根与后根构造二叉树与二叉树的匹配替换数据结构课程设计Word.docx》由会员分享，可在线阅读，更多相关《中根与后根构造二叉树与二叉树的匹配替换数据结构课程设计Word.docx（17页珍藏版）》请在冰点文库上搜索。
中根与后根构造二叉树与二叉树的匹配替换数据结构课程设计Word
成绩
南京工程学院
课程设计说明书（论文）
题目中根与后根构造二叉树与二叉树的匹配替换
课程名称数据结构
院（系、部、中心）计算机工程学院
专业计算机科学与技术
班级计算机卓越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，总的来说，做实验还是要边写代码边画图，这样思路清晰，还要细心一点，不能忘记任何一个步奏，仔细思考了一下，觉得一方面要多写多实践增加自己的经验，另一方面要多思考，多调试，要能看懂错误，并迅速想到解决方案，这需要长时间的积累。
还有就是实在想不出来的问题，可以和同学进行交流探讨，说不定问题就解决了。
毕竟一个人的能力是有限的，通过交流可以共同学习，互相进步。
教师评语：
（本资料素材和资料部分来自网络，仅供参考。
请预览后才下载，期待您的好评与关注！
）
升级会员 