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

《太原理工大学数据结构 实验二.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本科实验报告课程名称：实验项目：实验地点：专业班级：学号：学生姓名：指导教师：年月日实验项目一、实验目的和要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。二、实验内容和原理1.[问题]:编写递归算法，计算二叉树中叶子结点的数目。[输入]:一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD..EH...CF.I..G..。[输出]若为空二叉树，则输出：Thisisaemptybinarytree。若二叉树不空，按后序

2、序列计算，对上例，输出结果为：此二叉树叶节点个数为:4。　[存储结构]采用二叉链表存储。[算法的基本思想]采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。建立一个全局变量n，后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。当遍历过程中节点的左右孩子为空时n+1。2.[问题]:编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。[输入]:一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD..EH...CF.I

3、..G..。然后输入k的值，如输入：7.[输出]若为空二叉树，则输出：Thisisaemptybinarytree。若二叉树不空，按后序序列计算，对上例，输出结果为：按照先序顺序第7个位置的结点元素为:F。[存储结构]采用二叉链表存储。[算法的基本思想]采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。建立一个全局变量n，先序遍历二叉树时，先访问根结点，后遍历左子树，最后遍历右子树。当遍历一个节点时n+1，n>=k时不再遍历，输出此时的节点元素。三、主要仪器设备使用的计算机：惠普242G1笔记本电

4、脑，酷睿I5处理器，Windows7旗舰版64位系统，VC6.0编译器四、操作方法与实验步骤1.[源程序]:#include#includestaticintn=0;//定义全局变量用于计算叶子节点数//定义树节点的结构体structnode{charinfo;//数据类型是字符structnode*llink,*rlink;};typedefstructnodeNODE;//创建树递归调用NODE*creat(){charx;NODE*p;scanf("%c",&x);printf("%c",x)

5、;//当输入"."代表孩子为空if(x!='.'){p=(NODE*)malloc(sizeof(NODE));p->info=x;//采用先序遍历p->llink=creat();p->rlink=creat();}elsep=NULL;returnp;}//计算叶子节点函数递归调用voidcount(NODE*t){if(t){//采用后序遍历count(t->llink);count(t->rlink);if((t->llink==NULL)&&(t->rlink==NULL))n++;}}//主函数voidmain(){NODE

6、*T;printf("请建立二叉树:");T=creat();//生成树printf("");if(!T)printf("此二叉树为空.");count(T);printf("此二叉树叶节点个数为:%d",n);}2.[源程序]:#include#includestaticintn=0;//定义全局变量用于计算循环数//定义树节点的结构体structnode{charinfo;//数据类型是字符structnode*llink,*rlink;};typedefstructnodeNODE

7、;//创建树递归调用NODE*creat(){charx;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;returnp;}//得到第k个节点函数递归调用voidGetElem(NODE*t,intk,int*x){if(t){n++;if(n==k){*x=t->info;/

8、/采用先序遍历}elseif(nllink,k,x);GetElem(t->rlink,k,x);}}}//主函数voidmain(){NODE*T;