二叉链表创建

《二叉链表创建》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本科学生设计性实验报告项目组长＿＿刘正军＿学号＿＿0123921＿＿＿成员刘正军，章成（0123925）专业＿软件工程班级＿126＿实验项目名称＿二叉链表的创建________指导教师及职称＿严军勇讲师＿＿＿开课学期2013至2014年＿第一学期上课时间2013年11月11日至12月20日一、实验设计方案实验名称：自己选题后填上实验时间：小组合作：是否○小组成员：1、实验目的：通过实现某复杂算法，使学生理解数据结构基本概念、掌握栈、队列、树、图等的应用等，熟练使用C或者C++。巩固同学们在课堂上所学的知识

2、激发同学们主动学习和应用新知识的意识。本设计性实验由学生在下列题目中任选，或自拟题目：一元多项式加减乘法求解；哈夫曼编码实现；二叉链表的创建（以中序与后序，或中序与先序为输入）；迷宫求解；24点游戏设计（表达式求值）；银行排队系统模拟；最小生成树程序实现；拓扑排序程序实现；最短路劲程序实现；关键路径程序实现2、实验场地及仪器、设备和材料：实验场地：实验室仪器设备：联想台式机一台，MicrosoftVisualC++6.03、实验思路（实验内容、数据处理方法及实验步骤等）：其先序序列的第一个元素为根节点，接

3、下来即为其左子树先序遍历序列，紧跟着是右子树先序遍历序列，固根节点已可从先序序列中分离。在中序序列中找到确定的根节点，根据中序遍历特性，在巾序序列中，根节点前面的序列即为左子树的中序遍历序列，根节点后面的即为右子树的中序遍历序列。由左右子树的中序序列长度，在该二又树的先序序列中即可找到左右子树的先序序列的分界点，从而得到二叉树的左右子树的先序序列。递归实现：递归函数输入：二叉树的先序序列和中序序列；返回-、建好的二叉树的根节点。算法思想：1)若二叉树空，返回空；2)若不空，取先序序列第一个元素，建立根节点

4、；3)在中序序列中查找根节点，以此确定左右子树的先序序列和中序序列；4)递归调用自己，建左子树；5)递归调用自己，建右子树。6）输出后序用来检验树建立是否正确.7）同理可得中序与后续的递归算法。流程图指导老师对实验设计方案的意见：方案可行，请安本方案编程实现。指导老师签名：严军勇2013年12月10日二、实验结果与分析1、实验目的、场地及仪器、设备和材料、实验思路等见实验设计方案2、源程序清单、实验数据及结果截图代码如下BinaryLinkTree.cpp#includeusingna

5、mespacestd;#include"BinaryLinkTree.h"voidBinaryLinkTree::PreOrder(BNode*R)//先序递归遍历算法{if(R!=NULL){cout<data;PreOrder(R->LChild);PreOrder(R->RChild);}}voidBinaryLinkTree::InOrder(BNode*R)//中序递归遍历算法{if(R!=NULL){InOrder(R->LChild);cout<data;InOrder(R-

6、>RChild);}}voidBinaryLinkTree::PostOrder(BNode*R)//后序递归遍历算法{if(R!=NULL){PostOrder(R->LChild);PostOrder(R->RChild);cout<data;}}BinaryLinkTree.h#pragmaoncestructBNode{chardata;//数据域BNode*LChild;//左孩子指针BNode*RChild;//右孩子指针};classBinaryLinkTree{public:BNo

7、de*root;//根指针BNode*GetRoot(void)//返回根指针{returnroot;}voidPreOrder(BNode*R);//先序递归遍历算法voidInOrder(BNode*R);//中序递归遍历算法voidPostOrder(BNode*R);//后序递归遍历算法};Main.cpp#includeusingnamespacestd;#include"BinaryLinkTree.h"BNode*trans(char*pre,char*inorder,i

8、ntlen){char*p,*q;BNode*root=newBNode;inti;if(len<=0)returnNULL;root->data=pre[0];//根节点root->LChild=NULL;root->RChild=NULL;i=0;//i表示根节点在中序中的位置while(i