太原理工大学数据结构 实验二.doc

本科实验报告课程名称： 实验项目： 实验地点： 专业班级： 学号： 学生姓名： 指导教师： 年 月 日实验项目一、实验目的和要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。二、 实验内容和原理1. 问题: 编写递归算法，计算二叉树中叶子结点的数目。输入:一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD.EH.CF.I.G.。 输出若为空二叉树，则输出：This is a empty binary tree。若二叉树不空，按后序序列计算，对上例，输出结果为：此二叉树叶节点个数为:4。存储结构采用二叉链表存储。算法的基本思想采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。建立一个全局变量n，后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。当遍历过程中节点的左右孩子为空时n+1。2. 问题: 编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。输入:一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD.EH.CF.I.G.。然后输入k的值，如输入：7. 输出若为空二叉树，则输出：This is a empty binary tree。若二叉树不空，按后序序列计算，对上例，输出结果为：按照先序顺序第7个位置的结点元素为:F。存储结构采用二叉链表存储。算法的基本思想采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。建立一个全局变量n，先序遍历二叉树时，先访问根结点，后遍历左子树，最后遍历右子树。当遍历一个节点时n+1，n=k时不再遍历，输出此时的节点元素。三、主要仪器设备使用的计算机：惠普242G1笔记本电脑，酷睿I5处理器，Windows7旗舰版 64位系统，VC6.0编译器四、操作方法与实验步骤1. 源程序:#include#includestatic int n=0; /定义全局变量 用于计算叶子节点数 /定义树节点的结构体struct nodechar info; /数据类型是字符struct node *llink,*rlink;typedef struct node NODE; /创建树 递归调用NODE *creat()char x;NODE *p;scanf(%c,&x);printf(%c,x); /当输入.代表孩子为空if(x!=.)p=(NODE *)malloc(sizeof(NODE);p-info=x; /采用先序遍历p-llink=creat();p-rlink=creat(); elsep=NULL;return p; /计算叶子节点函数 递归调用void count(NODE *t)if(t) /采用后序遍历count(t-llink);count(t-rlink); if(t-llink=NULL)&(t-rlink=NULL) n+; /主函数void main()NODE *T; printf(请建立二叉树:n);T=creat(); /生成树printf(n);if(!T)printf(此二叉树为空.);count(T);printf(此二叉树叶节点个数为:%dn,n);2. 源程序:#include#includestatic int n=0; /定义全局变量 用于计算循环数 /定义树节点的结构体struct nodechar info; /数据类型是字符struct node *llink,*rlink;typedef struct node NODE; /创建树 递归调用NODE *creat()char x;NODE *p;scanf(%c,&x);printf(%c,x); /当输入.代表孩子为空if(x!=.)p=(NODE *)malloc(sizeof(NODE);p-info=x; /采用先序遍历p-llink=creat();p-rlink=creat(); elsep=NULL;return p; /得到第k个节点函数 递归调用void GetElem(NODE *t,int k,int* x)if(t)n+;if(n=k)*x=t-info; /采用先序遍历else if(nllink,k,x); GetElem(t-rlink,k,x); /主函数void main()NODE *T;int k;char x;printf(请输入要建立的二叉树:n);T=creat(); /生成树printf(n);if(!T)printf(This is a empty binary tree.);printf(请输入K值:); scanf(%d,&k); /输入k的值GetElem(T,k,&x);printf(按照先序顺序第%d个位置的结点元素为: %cn,k,x);五、实验数据记录和处理1. 2.六、实验结果与分析 我认为第一个程序较第二个程序而言，更体现出了结构化程序设计的思路，可移植性更强，但是但是由于采用的是顺序存储的形式，导致算法的时间性能和空间性能不是很好，而且健壮性不是很好,而且第二个程序较第一个程序所占空间更少。第一个程序的时间复杂度T(n)=O(n)，并且两个程序的函数都为原地工作，所占空间小。第二个程序还用了递归的算法，效率较高。七、讨论、心得通过这次的实验，大大的提高了自己的动手能力，亲自编