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

《中根与后根构造二叉树与二叉树的匹配替换-数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《中根与后根构造二叉树与二叉树的匹配替换-数据结构课程设计.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流中根与后根构造二叉树与二叉树的匹配替换-数据结构课程设计南京工程学院课程设计说明书(论文)题 目中根与后根构造二叉树与二叉树的匹配替换课 程 名 称 数据结构 院（系、部、中心） 计算机工程学院 专 业 计算机科学与技术 班 级 计算机卓越131 学 生 姓 名 羌秀君 学 号 202130404 设 计 地 点 信息楼 指 导 教 师 叶核亚 设计起止时间：2016年5月10日至2016年5月20日一、课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方

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

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

4、nlisti节点前的节点在根的左子树上，inlisti后的所有节点在根节点的右子树上。因此，根的左子树由i个节点组成，子序列为：左子树的后根次序 lalist0.lalisti-1左子树的中根次序inlist0.inlisti-1根的右子树由n-j-1个节点，子序列为：右子树的后根次序 lalisti.lalistn-2右子树的中根次序 inlisti+1.inlistn-13. 以此递归，可唯一确定一颗二叉树。算法实现：templateBinaryTree:BinaryTree(T lalist,T inlist,int n)this-root=create(lalist,inlist,n-

5、1,n-1,n,root);templateBinaryNode* BinaryTree:create(T lalist,T inlist,int end,int inend,int n,BinaryNode*parent)BinaryNode*p=NULL;if (n0)p=new BinaryNode(lalistend);int i=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);retur

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

7、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)return p;elsereturn NULL;elsereturn p;/匹配子树templatebool BinaryTree:matchtree(BinaryNode*p,BinaryNode*q)return (p =

8、NULL & q = NULL)|(q != NULL & p != NULL)&(p-data = q-data)&(matchtree(p-left,q-left)&matchtree(p-right,q-right);四、源程序1.二叉树节点类templateclass BinaryNodepublic:T data;/数据域BinaryNode*left,*right,*parent;/指针域，分别指向左右孩子节点/构造函数BinaryNode(T data,BinaryNode*left=NULL,BinaryNode*right=NULL,BinaryNode*parent=NUL

9、L)this-data=data;this-left=left;this-right=right;this-parent =parent;二叉树类#include using namespace std;#include BinaryTreeNode.htemplateclass BinaryTreepublic:BinaryNode* root;BinaryTree();/构造空二叉树BinaryTree(T lalist, T inlist, int n);/以中根和后根序列构造二叉树BinaryTree();/析构bool empty();/判断是否为空二叉树friend ostream

10、 & operator(ostream& out, BinaryTree&);/输出void preOrder();/输出先根次序遍历序列string getinOrder(BinaryNode*);/获得中根次序遍历的字符串string getpostOrder(BinaryNode*);/获得后根次序遍历的字符串void remove(BinaryNode*parent, bool leftchild);/删除parent节点的左或右子树BinaryNode* searchone(BinaryTree&);/查找子树BinaryNode* searchhead(BinaryNode*q,T

11、 key);/查找头结点bool matchtree(BinaryNode*p, BinaryNode*q);void destroy(BinaryNode*p);bool replace(BinaryTree&key, BinaryTree&re);private:void preOrder(BinaryNode*p);/先根次序遍历以p节点为根的子树void postOrder(BinaryNode*p, string &str);/后根void inOrder(BinaryNode*p, string &str);/中根次序遍历以p节点为根的子树BinaryNode* create(T

12、lalist, T inlist, int end, int inend, int n, BinaryNode*);BinaryNode* copy(BinaryNode*);/析构templateBinaryTree:BinaryTree()destroy(root);/判断树是否为空templatebool BinaryTree:empty()return this-root = NULL;/构造空二叉树templateBinaryTree:BinaryTree()this-root = NULL;/输出先根次序遍历的序列templateostream& operator(ostream

13、& out, BinaryTree& btree)out 先根次序遍历二叉树;btree.preOrder(btree.root);out endl;return out;templatevoid BinaryTree:preOrder(BinaryNode*p)if (p = NULL)cout ;elsecout data left);preOrder(p-right);/中根和后根构造二叉树templateBinaryTree:BinaryTree(T lalist, T inlist, int n)this-root = create(lalist, inlist, n - 1, n

14、- 1, n, root);templateBinaryNode* BinaryTree:create(T lalist, T inlist, int end, int inend, int n, BinaryNode*parent)BinaryNode*p = NULL;if (n0)p = new BinaryNode(lalistend);int i = 0;while (iparent = parent;p-right = create(lalist, inlist, end - 1, inend, i, p);p-left = create(lalist, inlist, end -

15、 i - 1, inend - i - 1, n - i - 1, p);return p;/删除子树templatevoid BinaryTree:destroy(BinaryNode*p)if (p != NULL)destroy(p-left);destroy(p-right);delete p;/查找根节点templateBinaryNode* BinaryTree:searchhead(BinaryNode*q, T key)BinaryNode*m = NULL;if (q != NULL)if (q-data = key)return q;if (m = searchhead(q

16、-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)return p;elsereturn NULL;elsereturn p;/匹配子树templatebool BinaryTree:matchtree(BinaryN

17、ode*p, BinaryNode*q)if (q = NULL&p = NULL)return true;if (p = NULL | q = NULL)return false;if (p-data != q-data)return false;return(matchtree(p-left, q-left) & matchtree(p-right, q-right);/替换templatebool BinaryTree:replace(BinaryTree&key, BinaryTree&re)BinaryNode*p = searchone(key);if (p != NULL)/替换

18、(搜到的头不销毁)destroy(p-left);destroy(p-right);p-data = re.root-data;p-left = copy(re.root-left);p-right = copy(re.root-right);return true;elsereturn NULL;/二叉树复制templateBinaryNode* BinaryTree:copy(BinaryNode*p)BinaryNode*q = NULL;if (p != NULL)q = new BinaryNode(p-data);q-parent = p-parent;q-left = copy(

19、p-left);q-right = copy(p-right);return q;/获得中根遍历下的字符串templatestring BinaryTree:getinOrder(BinaryNode*p)string str;inOrder(p, str);return str;templatevoid BinaryTree:inOrder(BinaryNode*p, string &str)if (p != NULL)inOrder(p-left, str);str += p-data;inOrder(p-right, str);/获得后根遍历下的字符串templatestring Bin

20、aryTree:getpostOrder(BinaryNode*p)string str;postOrder(p, str);return str;templatevoid BinaryTree: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 using namespace std;int main()char la

21、list=GDBEHFCA;char inlist=DGBAECHF;char inkey=ECHF;char lakey=EHFC;char inrep=LJMIK;char larep=LMJKI;BinaryTree tree(lalist,inlist,8);BinaryTree keytree(lakey,inkey,4);BinaryTree reptree(larep,inrep,5);couttree;cout二叉关键子树endlkeytree;cout待替换的子树endlreptree;cout替换后endl;tree.replace(keytree,reptree);cou

22、ttree;return 0;五、结果及分析结果：分析：1. 通过中根char lalist=GDBEHFCA; 后根char inlist=DGBAECHF;构造一颗二叉树TREE。2. 通过中根char inkey=ECHF;后根char lakey=EHFC;构造一颗关键二叉树KEYTREE。3. 通过中根char inrep=LJMIK;后根char larep=LMJKI;构造一颗待替换的树REPTREE；4. 通过KEYTREE的根在TREE中找到对应的地址，然后判断通过找到以此地址为根的子树是否与KEYTREE相同。5. 相同将删除以找到的地址为根的子树。6. 复制REPTREE

23、到TREE删除的子树上。六、总结与思考1，首先一开始对这个题目没有思路，可能是书上代码不熟悉的原因，所以我在做实验之前，把书上老师上课讲的二叉树这边的功能都实现了一遍，对二叉树的操作有了最基本的操作了解之后，慢慢入门。2，然后我仔细分析了这条题目，要用到的函数都写了下来，把要实现的操作都用草图的形式画了出来，这样我就对我该先做什么，后做什么，这种目的实现的方法有了自己的思路。3，我在着手写程序的时候，出现了很多问题，在中后根构造上花了不少时间，总之还是自己不够细心。4，经过自己的努力，我把那些应该用到的功能函数都实现好了。还有其他地方也进行了改进，实验终于成功了。5，总的来说，做实验还是要边写代码边画图，这样思路清晰，还要细心一点，不能忘记任何一个步奏，仔细思考了一下，觉得一方面要多写多实践增加自己的经验，另一方面要多思考，多调试，要能看懂错误，并迅速想到解决方案，这需要长时间的积累。还有就是实在想不出来的问题，可以和同学进行交流探讨，说不定问题就解决了。毕竟一个人的能力是有限的，通过交流可以共同学习，互相进步。教师评语：.精品文档.成绩