数据结构B实验报告-单链表的实现.doc

《数据结构B实验报告-单链表的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告（2014/2015学年第二学期）课程名称数据结构B实验名称单链表的实现实验时间2015年5月15日指导单位计算机学院计算机科学与技术系指导教师学生姓名班级学号学院(系)通达学院专业信息管理与信息系统实验报告实验名称二叉树的链接表示指导教师徐鹤实验类型设计实验学时2实验时间2015.5.15一、实验目的和要求1.理解二叉树的数据结构。2.掌握二叉链表上实现二叉树基本运算的方法。3.学会设计基于遍历的、求解二叉树应用问题的方法。二、实验内容:实现教材中二叉树的链接表示，并基于二叉树遍历算法实现其应用。具体如下：（一）实现教材中二叉树的链接表示，实现二

2、叉树ADT的基本运算（先序遍历、中序遍历、后序遍历）。（二）基于二叉树遍历算法实现其应用：①计算一棵二叉树叶子节点个数。②统计一棵二叉树的节点个数。（三）设计main函数，测试实验内容一的运算和实验内容二的算法。三、实验环境(实验设备)VisualC++6.010实验报告四、实验过程描述与结果分析#include#include#includetypedefstructbtnode{charelement;structbtnode*lchild,*rchild;}BTNode;BTNode*PreC

3、reate(BTNode*Bt)//先序创建二叉树{charch;ch=getchar();if(ch=='#')//输入为#表示这里建立一个空二叉树Bt=NULL;else{Bt=(BTNode*)malloc(sizeof(BTNode));10Bt->element=ch;Bt->lchild=PreCreate(Bt->lchild);Bt->rchild=PreCreate(Bt->rchild);}returnBt;}voidPreorder(BTNode*Bt)//先序输出二叉树{if(Bt){printf("%c",Bt->element)

4、;Preorder(Bt->lchild);Preorder(Bt->rchild);}}voidInorder(BTNode*Bt)//中序输出二叉树{if(Bt){10Inorder(Bt->lchild);printf("%c",Bt->element);Inorder(Bt->rchild);}}voidPostorder(BTNode*Bt)//后序输出二叉树{if(Bt){Postorder(Bt->lchild);Postorder(Bt->rchild);printf("%c",Bt->element);}}intSize(BTNode*B

5、t)//求二叉树中的结点数{ints,s1,s2;if(!Bt)//二叉树为空，结点数为0s=0;10else{s1=Size(Bt->lchild);s2=Size(Bt->rchild);s=s1+s2+1;//二叉树的结点数等于左右子树结点数的和在加1（根结点）}returns;}intLeaf(BTNode*Bt)//求二叉树中叶子个数{intll,rl,tl;if(!Bt)//二叉树为空，叶子个数为0tl=0;elseif(!Bt->lchild&&!Bt->rchild)//叶子满足的条件（左右孩子均为空）tl=1;else{ll=Leaf(B

6、t->lchild);10rl=Leaf(Bt->rchild);tl=ll+rl;}returntl;}intDepth(BTNode*Bt)//求二叉树的深度（高度）{intld,rd,td;if(!Bt)td=0;else{ld=Depth(Bt->lchild);rd=Depth(Bt->rchild);if(ld>=rd)//左右子树高度大的加1，即为二叉树的高度td=ld+1;elsetd=rd+1;}10returntd;}voidmain(){BTNode*Bt;ints,tl,td;Bt=NULL;printf("Inputcreat

7、eorder:");Bt=PreCreate(Bt);printf("Thepreorderis:");Preorder(Bt);printf("Theinorderis:");Inorder(Bt);printf("Thepostorderis:");10Postorder(Bt);s=Size(Bt);printf("Thesizeofthetreeis:");printf("%d",s);tl=Leaf(Bt);printf("Theleavesofthetreeis:");printf("%d",

8、tl);td=Depth(Bt);printf("Thedep