二叉树实验报告-5

实验报告课程名称数据结构实验名称二叉树实验类型验证性实验实验地点计304机房实验日期指导教师魏海平专业计算机科学与技术班级计算机1002学号20姓名张森辽宁石油化工大学计算机与通信工程学院数据结构实验报告评分表项目要求分数有无项目（√）得分预习报告（30分）实验目的明确5实验内容理解透彻5实验方案设计完整合理程序总体框架设计完整10完成相关辅助代码5测试方案合理5实验过程（30分）发现问题5问题的分析15问题的解决方法10实验报告（20分）内容翔实无缺漏5如实记录实验过程10撰写规整5实验总结（10分）实验结果的分析5按照结果对原实验方案的改进意见5实验体会（10分）实验的收获5实验内容的发散考虑5总分一．实验内容：实现创建和遍历二叉树的基本操作二．实验目的：（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。三．问题描述：（1）编程实现构造一棵二叉树的算法，适合任意合法输入的二叉树的建立，并进行相应异常处理。（2）编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法可在先序、中序和后序遍历算法中任选其一。四．问题的实现详细设计确定存储结构，并给出所用抽象数据类型的数据结构定义#include<stdio.h>#include<malloc.h>typedefcharDataType;typedefstructNode{DataTypedata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;voidPreOrder(BiTreeroot){//root为根if(root!=NULL){printf("%c",root->data);//所有的VISIT用PRINTF代替PreOrder(root->LChild);PreOrder(root->RChild);}}voidRecurrentInOrder(BiTreeroot)//递归中序{//root为根if(root!=NULL){RecurrentInOrder(root->LChild);printf("%c",root->data);RecurrentInOrder(root->RChild);}}voidPostOrder(BiTreeroot){//root为根if(root!=NULL){PostOrder(root->LChild);PostOrder(root->RChild);printf("%c",root->data);}}voidCreatBiTree(BiTree*bt)//创建二叉树{charch;ch=getchar();if(ch=='.')*bt=NULL;//输入.就结束输入else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));}}voidInOrder(BiTreeroot)//直接非递归算法{inttop=0;BiTreep=root,s[100];while(p!=NULL||top!=0){while(p!=NULL){top++;s[top]=p;p=p->LChild;}if(top!=0){p=s[top];top--;printf("%c",p->data);p=p->RChild;}}}voidPrintTree(BiTreebt,intnLayer){if(bt==NULL)return;PrintTree(bt->RChild,nLayer+1);for(inti=0;i<nLayer;i++)printf("");printf("%c\n",bt->data);PrintTree(bt->LChild,nLayer+1);}intmain(){BiTreeR;CreatBiTree(&R);printf("DoPreOrder(Recurrent)：\n");//递归先序PreOrder(R);printf("\n\n");PrintTree(R,1);printf("DoInOrder(Recurrent)：\n");//递归中序RecurrentInOrder(R);printf("\n\n");printf("DoPostOrder(Recurrent)：\n");//递归后序PostOrder(R);printf("\n\n");printf("DoInOrder(NOTRecurrent)：\n");//非递归中序InOrder(R);printf("\n\n");return0;}测试结果列出典型输入及对应的输出结果。输入：ABC..DE.G..F...（其中.表示空格字符）输出结果：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA总结1．基本上没有什么太大的问题，在调用select（）这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding()，所以把那2个序号设置成了引用