数据结构课程设计内容.doc

《数据结构课程设计内容.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、成绩南京工程学院课程设计说明书(论文)题目中根与后根构造二叉树与二叉树的匹配替换课程名称数据结构院（系、部、中心）计算机工程学院专业计算机科学与技术班级计算机卓越131学生姓名羌秀君学号202130404设计地点信息楼指导教师叶核亚设计起止时间：2016年5月10日至2016年5月20日一、课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题

2、和解决问题的作风和能力。要求：熟练运用C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二、题意说明及分析题目要求采用中根和后根序列构造一颗二叉树，并匹配替换二叉树的子树。中根和后根构造：由于后根可以确定一颗树的根，而中根在知道根的情况下可以确定左右子树的序列，因此这样递归，中根和后根可以确定一颗唯一的二叉树。

3、匹配替换二叉树：1.通过遍历二叉树找到关键树根值在待匹配树中首次出现的位置，返回节点地址。2.判断以找到的节点为根的子树和带匹配的树是否相同，采用递归算法。3.确定以找到根节点的子树与带匹配的树相同，然后删除以此为根节点的子树，然后再将带替换的树复制到删除的节点。三、算法设计与分析算法设计思路、数据结构描述、流程图等中根和后根构造算法：设数组inlist[]和lalist[]分别表示一颗二叉树的中根和后根序列，两序列长度均为n。1.由后根遍历的次序可知，该二叉树的根是lalist[n-1]；改节点必定在中根次

4、序中，设根节点在中根次序的第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]...

5、inlist[n-1]3.以此递归，可唯一确定一颗二叉树。算法实现：templateBinaryTree::BinaryTree(Tlalist[],Tinlist[],intn){this->root=create(lalist,inlist,n-1,n-1,n,root);}templateBinaryNode*BinaryTree::create(Tlalist[],Tinlist[],intend,intinend,intn,BinaryNode

6、*parent){BinaryNode*p=NULL;if(n>0){p=newBinaryNode(lalist[end]);inti=0;while(iparent=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;}匹配替换二叉

7、树算法：通过遍历二叉树找到关键树根值在待匹配树中首次出现的位置，返回节点地址。判断以找到的节点为根的子树和带匹配的树是否相同，采用递归算法。确定以找到根节点的子树与带匹配的树相同，然后删除以此为根节点的子树，然后再将带替换的树复制到删除的节点。算法实现：//查找根节点templateBinaryNode*BinaryTree::searchhead(BinaryNode*q,BinaryNode*p){BinaryNode*m=NULL;if(q!=NULL&&p

8、!=NULL){if(q->data==p->data){returnp;}if((m=searchhead(q->left,p))==NULL)m=searchhead(q->right,p);}returnm;}//查找子树templateBinaryNode*BinaryTree::searchone(BinaryTree&bintree){BinaryNod