《二叉树数据结构和课程设计.doc》由会员分享，可在线阅读，更多相关《二叉树数据结构和课程设计.doc（12页珍藏版）》请在三一办公上搜索。
1、二叉树 实验报告姓名：姚伍奎 时间：2012-3-91. 实验目的：（1） 掌握二叉树的三种遍历算法（递归和非递归两类）（2） 本实验主要了解二叉树的建立和先序遍历的算法2实验内容:(1) 首先创建一个二叉树,然后进行二叉树的先序遍历.(2) 采用二叉树表结构存储,每个结点有存放字符型数据的字段data，存放左右孩子的指针字段Lchild和Rchild.(3) 二叉树及其对应的二叉树链表如下图： 图1.13 实验步骤 先创建二叉树是否存在 否 是 *T=NULL分配一个二叉树空间分别创建二叉树的左右子树输入一个二叉树是否为空 是 否 输出二叉树 返回return 生成主函数main(); 输入
2、图1.1二叉树图 先序输出二叉树结束 四 试验程序如下：#include stdio.h#include stdlib.h#define MAXSIZE 12500typedef struct BitNodechar data;struct BitNode *lchild,*rchild;*BitTree;typedef struct stackint top;BitTree MaxSizeMAXSIZE;*Stack;void creattree(BitTree *T) char ch ;scanf(%c,&ch);if(ch=.)*T = NULL;else(*T) = (struct B
3、itNode *)malloc(sizeof(struct BitNode);(*T)-data = ch;creattree(&(*T) - lchild);creattree(&(*T) - rchild);void PrintTree(BitTree Boot) if(Boot =NULL)return;elseprintf(%c,Boot-data);PrintTree(Boot-lchild);PrintTree(Boot-rchild); int leaf(BitTree T)if(!T)return 0;else if(!(T)-lchild)& !(T)-rchild)retu
4、rn 1;elsereturn (leaf(T-lchild)+leaf(T-rchild);void main()BitTree T;printf(请先输入二叉树 （.代表空子树）： n);creattree(&T);printf(先序输出为：);PrintTree(T);五 实验结果如下图：数据结构课程设计姓名：姚伍奎一.设计题目： 设计程序按从小到大的次序依次输出函数f(a,b)=2*a*a+b*b的最小的100个函数值及其相应的两个参数的值，其中a和b均为自然数。要求：（1） 作为函数值的存储结构应尽可能节省空间。（2） 所设计算法及整个程序的时间复杂度应尽可能小。二 运行环境：在C环
5、境中运行三 算法设计结构图：先定义一个函数f()设置主函数main()；设置 两个整形变量a、b 设置三个整形参数:count、result、flaga.For循环语句b.For循环语句Temp=result 是否 输出、跳出、计算下一个Tempresult 否Flag=1 是 是 否Count=100 是按倒序输出结果 否A=49 否 是结束 四 算法设计：设计本题算法的构思如下：（1）为得到符合要求的结果数。算法中设计了一个结构体数组struct用于存放a、b和结果值。（2）算法设置两个变量a、b和一个参数result（结果值），算法主要根据选取a、b值来得到结果。需要尽量选取a、b值的时
6、候应尽量小且有顺序选取。（3）分别用一个for循环对和进行选值，把函数赋给结构体数组。用if语句判断结果数与结构体数组中的数值是否相等，如果相等则输出值，然后结果数和计算器数自增；如果不符，跳出，计算下一个。（4）用一个整形参数flag来判断a、b是否可得出结果的标识。当计数器等于100时跳出for循环语句。（5）如果等于49时还未得到100个数，结果数自增，计算下一个，a=-1，跳出。从新计算。（6）输出结果按倒序输出。五 源代码如下：#include #include int f(int a, int b) 待添加的隐藏文字内容2 return 2*a*a+b*b; struct int
7、a;int b;int result;result_temp100;int main() int a,b; int count=0;/已得到的结果数int result=0;/目的结果int flag=0;/判断a b是否可得出结果的标识for (a=0; a50;a+)/50控制循环数，可调，只要能得到个结果，越小越好 for (b=0; bresult) break; if (flag=1) flag=0; a=-1; continue; if (count=100) break; if (a=49)/a时还未得出结果，目的结果自增，从新计算下一个 result+; a=-1; conti
8、nue; for(int i=99;i=0;i-)printf(%d %d %d n,result_tempi.a,result_tempi.b,result_tempi.result);getchar();六 运行结果如图:(截图)七 总结： 程序设计是培养学生综合运用所学知识，发现提出分析和解决实际问题。锻炼实践能力的重要环节，是对我们的实际工作能力的具体训练和考察的过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说是无处不在。而掌握程序开发技术是十分重要的，而数据结构又是程序开发的前提和基础。这次程序课程设计结束了，它不仅检验了我们所学的知识，也培养了我们如何去把握一件事情，
9、如何去做一件事情，又如何完成一件事情的动手能力。通过这次课程设计。我把前面所学的知识又从新温故了一遍。在进行课程设计中，更好的认识了:结构体和伪代码，认识伪代码是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以更容易地以任何一种编程语言实现，因此伪代码必须结构清晰，简单，可读性好。看着简单，但做着难！此句话一点都没有错，自己有点眼高手低了，心太急。不过敢想、敢写、敢去尝试，付出了就会有回报。收获了不少。FOR循环、判定条件的IF语句、continue用法和bread用法、结构体的使用等等，很有体会。做了这个课程设计，我觉得课程设计这种形式真的是我们需要的，可以让我们学到很多，包括书本上的，书外的。可谓是理论永远都需要实践来证明，否则理论永远是理论，不可能等于实践的。在自学的时候，觉得自己对于书本上的知识都会了，但真的到了电脑前编起程序来的时候，却时常遇到出错。比如：循环条件、条件句的判定等等。在和同事一次又一次的修改与调试，最终才运行成功。想想做实验的过程中出现的错误，自己感叹：平常这些都是很容易的，根本就没有理由错的，可是竟然出现了。看来自己真的要从新认识一下自己了，不要眼高手低！
