《实验五树及其应用.docx》由会员分享，可在线阅读，更多相关《实验五树及其应用.docx（8页珍藏版）》请在金锄头文库上搜索。
1、貌件孕陇散据偌构实掘若（本实验项目方案受“教育部人才培养模式创新实验区（X31O8OO5）”项目资助）实验难度：A 口序号学号姓名成绩123指导教师.（签名）学 期：任课教师：实验题目：树及其应用小组长:联系电话:电子邮件：完成提交时间：一、【实验构思(Conceive) (10%)(本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设 计、算法等相关知识)本次实验的目的在于继续突出数据结构+操作构成抽象数据类型的程序设计观点， 根据树结构非线性的特点，建立二叉树，再进一步实现树的存储结构生成和各种顺序遍历， 熟悉树结构的逻辑特性，应用树结构解决具体问题。口具体要求如下
2、：用C语言建立二叉 树，并实现二叉树的先序、中序、后序遍历。基本思路：根据二叉树的层次遍历方法建立二叉树的二叉链表，选用链式存储结构作 为二叉树的存储结构，根据用户的意愿按照层次遍历的顺序分别输入结点的序号和值，其 中空结点不输入任何信息，直接输入下一个结点的信息。二叉树建立存储好以后，再根据 各个遍历顺序的先后顺序对二叉树的左右子树进行递归遍历。算法思想：在这个程序中主要用到线/性链表和函数的递归的基本操作。首先定义一个 二叉链表，将用户输入的信息存储在该链表中，建立二叉树。然后分别根据二叉树的遍历 顺序访问各个结点。二叉树的先序遍历，先访问二叉树的根结点，然后递归访问结点的左 右子树；二叉
3、树的中序遍历，先访问二叉树的根结点的左子树，然后访问根结点，最后访 问根结点的右子树，如此递归直至访问到所有的结点；二叉树的后序遍历，先访问二叉树 的根结点的左右子树，然后根访问结点并如此递归循环直至访问到所有的结点。二、【实验设计(Design) (20%)(本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明， 主程序模块与各子程序模块间的调用关系)抽象数据类型：typedef struct btnode(char cdata;/结点信息即结点的值struct btnode *lch, *rch;/定义左右子树BTNode;/定义一个线性链表，存储二叉树int ma
4、inO主函数，主要就是调用各函数建立二叉树并按先序、中序和后序遍历BTNode *Create_BTree ()/二叉树的建立函数，用数组建立二叉树，根据用户的输入用线性链表进行存储，void PreOrder (BTNode *bt) 先序遍历函数，按照先序遍历的顺序依次访问二叉 树的各结点，并应用递归的思想void InOrder (BTNode *bt) 中序遍历函数，按照中序遍历的顺序依次访问二叉 树的各结点，并应用递归的思想void PostOrder (BTNode *bt) /后序遍历函数，按照后序遍历的顺序依次访问二 叉树的各结点，并应用递Q的思想函数的调用关系：MainOCr
5、eate_BTree ()PreOrder ()InOrd ()PostOrder ()三、【实现描述(Implement) (30%)(本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函 数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。) 函数设计：BTNode *Create_BTree()/二叉树的建立，用辅助数组建立二叉树int i, j;char ch;BTNode *s,*t,*pMAXSIZE；pr i ntf (ntt 请输入结点：)；scanf (%d,%c,&i, &ch);whi le(i !=0 &ch!=#)/建立
6、二叉树的存储结构(s= (BTNode *)ma I Ioc(s i zeof(BTNode);s-cdata=ch;s-lch二s-rch二NULL;pi=s;if (i=1)t二s;/判断输入结点是根结点、左孩子还是右孩子e I sej=i/2;if (i%2=0)pj-lch=s;Elsepj_rch=s;pr i ntf (ntt 请输入结点:);scanf (%d, %c, &i, &ch);/wh iIereturn t;)/ Create_BTree1 建立二叉树vo i d PreOrder (BTNode *bt)if(bt)pr i ntf (%c,bt-cdata);Pr
7、eOrder (btI ch);PreOrder(bt-rch);)/Preorder先序递归遍历 vo i d InOrder(BTNode *bt)(i f (bt)(InOrder (btIch); pr intf (%c, bt-cdata);InOrder (bt-rch);)/Inorder,中序递归遍历 vo i d PostOrder (BTNode *bt)if (bt)PostOrder (bt-lch);PostOrder (btrch); pr i ntf (%c,btcdata);)/ Postorder,后序递归遍历 void main () /主函数，调用各子函数
8、int i=1;BTNode *t;/*功能菜单*/prntf (nntt*); printf (ntt* 用 户 选 择 *H)；printf(nttt);printf（nntW I1 .二叉树的建立| ”）；printf （”nttt |2.二叉树的前序遍历|”）;printf（nnttt |3.二叉树的中序遍历|”）;pr intf （nttt |4.二叉树的后序遍历|”）;printf（Hnttt |0 .退 出程序| ”）；pr intf （nttt |说明：输入结点信息的格式为（i,ch）; | ）; printf （nttt | i为结点数，ch为结点的信息; | ）; prin
9、tf（Hnttt | 输入（0,#）时结束二叉树的建立；| ）; pr intf （nttt |若该结点为空，则不输入任何信息| ）;pr intf （nttt）;pr i ntf （ntt*）； whi le（i）printf（Hnnt 请选择操作：”）； scanf （%d,&i）;switch（i）case 0: pr intf （ t 程序退出！n ） ;break;case 1: t=Create_BTree（）;break；case 2: pr intf （ntt 前序遍历结果：”）；PreOrder （t） ; /调用先序遍历函数 break；case 3: pr intf （n
10、tt 中序遍历结果：）；InOrder （t） ;/调用中序遍历函数break；case 4: pr intf （ntt 后序遍历结果：”）；PostOrder （t） ; /调用后序遍历函数 break;default : printf （aaantt 输入无效，请重新选择操作！n）； break；/switch1/wh iIe关键算法的时间复杂度：这个程序的目的是遍历二叉树，即访问二叉树的各个结点, 因此时间的复杂度取决于二叉树结点个数的多少，所有这个程序的时间复杂度为0 (n), 为二叉树结点的个数。四、【测试结果(Testing) (10%)(本部分应包括：对实验的测试结果，应具体列出
11、每次测试所输入的数据以及输出的数据,并对测试结果进行分析总结)| 甘 G:WINDOWSsystem32and.exe用户选择1二二叉村的建立2 .二叉利的前庄遍历3 .二叉咬的申序遍历4 二叉树的后序遍历0 .退出程庞说明：输入结点蓿息的格式为i,ch)；的刖序遍加的中序遍历请后点遍历i为结点数，ch为*兽的信息； 黜?瞄请选择操作：1请输入结点：l,d请输入结点：21请输入结点：4,k请输入结点：5.p请输入结点:请选择操作：2前序遍历结果：drkp请选择操作：3中序遍历结果：krpd请选择操作：4后序遍历结果：kprd请选择操作：经过对实验结果的分析和验证表明，该出现运行后得到的结果正确
12、，程序编写符合题 目A难度的要求，能够建立一个二叉树并进行先序、中序和后序遍历，并且能够正常运行。四、【实验总结】(10%)(本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至 少一项接口的实现：对所完成实验的经验总结、心得)在这次实验中，我所编写的程序符合题目A难度的基本要求。这次使用递归编程最后 实现了题目中二叉树的建立和遍历，加深了对二叉树的逻辑结构属性的了解，并掌握了二 叉树的存储和遍历等基本操作。但是这个程序没有能够实现二叉树与树的相互转换，这主 要是由于自己对二叉树与树的相互转换没有深刻的理解，不能通过程序演示这个转换过程, 而且不能实现一个简单的译码器。
13、本次实验没有完成CDI0项目要求的任务，仅仅只能够实 现一个简单的二叉树的建立和遍历，没有完成实验的一些较高难度的要求，需要在今后的 学习中加深对二叉树相关知识的学习，尤其是二叉树与树的相互转换，并不断改进实验的 基本思路和难度，完善程序。五、【项目运作描述(Operate) (10%)(本部分应包括：项目的成本效益分析，应用效果等的分析。)由于这个程序难度较低也不是界面模式运行，几乎没有成本效益，应用效果也欠佳。六、【代码】(10%)(本部分应包括：完整的代码及充分的注释。注意纸质的实验报告无需包括此部分。格式 统一为，字体：Georgia ,行距：固定行距12,字号：小五)#include #inchide #define MAXSIZE lootypedef stnict btnodechar cdata;/结点信息struct btnode *lch,*rch;定义孩子结点BTNode;BTNode *Create_BTree()/-叉树的建立，用辅助数组建立二叉树int i,j；char ch;BTOodc *s,*t,*pMAXSIZE;printf(ntt 请输入结点：”)；scanf(%d,%c”,&i,&ch);while(i!=o &ch!=#) 建立二叉树的存储纬构s=(BTNode *)ma】loc(sizeof(BTNode);s-cdata=ch;s-
