首页 中根与后根构造二叉树与二叉树的匹配替换-数据结构课程设计

中根与后根构造二叉树与二叉树的匹配替换-数据结构课程设计

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

南京工程学院课程设计说明书（论文）成绩题目中根与后根构造二叉树与二叉树的匹配替换课程名称数据结构院（系、部、中心）计算机工程学院专业计算机科学与技术班级计算机卓越131学生姓名羌秀君学号202130404设计地点信息楼指导教师叶核亚设计起止时间：2016年5月10日至2016年5月20日、课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。要求：熟练运用C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二、题意说明及分析题目要求采用中根和后根序列构造一颗二叉树，并匹配替换二叉树的子树。中根和后根构造：由于后根可以确定一颗树的根，而中根在知道根的情况下可以确定左右子树的序列，因此这样递归，中根和后根可以确定一颗唯一的二叉树。匹配替换二叉树：通过遍历二叉树找到关键树根值在待匹配树中首次出现的位置，返回节点地址。判断以找到的节点为根的子树和带匹配的树是否相同，采用递归算法。确定以找到根节点的子树与带匹配的树相同，然后删除以此为根节点的子树，然后再将带替换的树复制到删除的节点。三、算法设计与分析算法设计思路、数据结构描述、流程图等中根和后根构造算法：设数组inlist[]和lalist[]分别表示一颗二叉树的中根和后根序列，两序列长度均为n。由后根遍历的次序可知，该二叉树的根是lalist[n-1]；改节点必定在中根次序中，设根节点在中根次序的第i个位置即inlist[i]=lalist[n-1]。由中根遍历次序知，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.以此递归，可唯一确定一颗二叉树。算法实现：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*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;}匹配替换二叉树算法：通过遍历二叉树找到关键树根值在待匹配树中首次出现的位置，返回节点地址。判断以找到的节点为根的子树和带匹配的树是否相同，采用递归算法。确定以找到根节点的子树与带匹配的树相同，然后删除以此为根节点的子树，然后再将带替换的树复制到删除的节点。算法实现：//查找根节点templateBinaryNode*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;}//查找子树templateBinaryNode*BinaryTree::searchone(BinaryTree&bintree){BinaryNode*p=searchhead(root,bintree.root);if(p!=NULL){if(matchtree(p,bintree.root))returnp;elsereturnNULL;}elsereturnp;}//匹配子树templateboolBinaryTree::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.二叉树节点类templateclassBinaryNode{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;}};二叉树类#includeusingnamespacestd;#include"BinaryTreeNode.h"templateclassBinaryTree{public:BinaryNode*root;BinaryTree();〃构造空二叉树BinaryTree(Tlalist[],Tinlist[],intn);//以中根和后根序列构造二叉树~BinaryTree();//析构boolempty();〃判断是否为空二叉树friendostream&operator<<<>(ostream&out,BinaryTree&);//输出voidpreOrder();〃输出先根次序遍历序列stringgetinOrder(BinaryNode*);//获得中根次序遍历的字符串stringgetpostOrder(BinaryNode*);//获得后根次序遍历的字符串voidremove(BinaryNode*parent,boolleftchild);//删除paren节点的左或右子树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*);};//析构templateBinaryTree::~BinaryTree(){destroy(root);}//判断树是否为空templateboolBinaryTree::empty(){returnthis->root==NULL;}//构造空二叉树templateBinaryTree::BinaryTree(){this->root=NULL;}//输出先根次序遍历的序列templateostream&operator<<<>(ostream&out,BinaryTree&btree){out<<"先根次序遍历二叉树";btree.preOrder(btree.root);out<voidBinaryTree::preOrder(BinaryNode*p){if(p==NULL){cout<<"A";}else{cout<data<<"";preOrder(p->left);preOrder(p->right);}}//中根和后根构造二叉树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*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;}//删除子树templatevoidBinaryTree::destroy(BinaryNode*p){if(p!=NULL){destroy(p->left);destroy(p->right);deletep;}}//查找根节点templateBinaryNode*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;}//查找子树templateBinaryNode*BinaryTree::searchone(BinaryTree&bintree){BinaryNode*p=searchhead(root,bintree.root->data);if(p!=NULL){if(matchtree(p,bintree.root))returnp;elsereturnNULL;}elsereturnp;}//匹配子树templateboolBinaryTree::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));}//替换templateboolBinaryTree::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;}elsereturnNULL;}//二叉树复制templateBinaryNode*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;}//获得中根遍历下的字符串templatestringBinaryTree::getinOrder(BinaryNode*p){stringstr;inOrder(p,str);returnstr;}templatevoidBinaryTree::inOrder(BinaryNode*p,string&str){if(p!=NULL){inOrder(p->left,str);str+=p->data;inOrder(p->right,str);}}//获得后根遍历下的字符串templatestringBinaryTree::getpostOrder(BinaryNode*p){stringstr;postOrder(p,str);returnstr;}templatevoidBinaryTree::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#includeusingnamespacestd;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< 方案，这需要长时间的积累。还有就是实在想不出来的问题，可以和同学进行交流探讨，说不定问题就解决了。毕竟一个人的能力是有限的，通过交流可以共同学习，互相进步。教师评语：

                    本文档为【中根与后根构造二叉树与二叉树的匹配替换-数据结构课程设计】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

中根与后根构造二叉树与二叉树的匹配替换-数据结构课程设计

你可能还喜欢