(中央电大)数据结构实验报告3

《(中央电大)数据结构实验报告3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中央广播电视大学实验报告（学科：数据结构）姓名班级学号实验日期成绩评定教师签名批改日期实验名称：实验三二叉树3.1二叉树的顺序存储结构和链式存储结构【问题描述】设一棵完全二叉树用顺序存储方法存储于数组tree中，编写程序：（1）根据数组tree，建立与该二叉树对应的链式存储结构。（2）对该二叉树采用中序遍历法显示遍历结果。【基本要求】（1）在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。（2）设计子函数，其功能为将顺序结构的二叉树转化为链式结构。（3）设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。（4）通过实

2、例判断算法和相应程序的正确性。【实验步骤】（1）运行PC中的MicrosoftVisualC++6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码，程序代码如下:#include#include#include#include#include#defineMaxSize10typedefstruc

3、tnode{chardata;structnode*left,*right;}NODE;voidCreab(char*tree,intn,inti,NODE*p);voidInorder(NODE*p);voidmain(){NODE*p;chartree[MaxSize];intn=1;inti=1;printf("请输入完全二叉数的节点值（连续输入字符，以回车结束输入。）:");while((tree[n]=getchar())!='')n++;tree[n]='';p=NULL;Creab(tree,n,i,p);Ino

4、rder(p);}voidCreab(char*tree,intn,inti,NODE*p){if(i>=n)p=NULL;else{p=(NODE*)malloc(sizeof(NODE));p->data=tree[i];printf("%c",p->data);Creab(tree,n,2*i,p->left);Creab(tree,n,2*i+1,p->right);}}/*中序遍历树*/voidInorder(NODE*p){if(p!=NULL){Inorder(p->left);printf("%c",p->data);

5、Inorder(p->right);}}程序运行结果如下:3.1二叉树的遍历【问题描述】设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。【基本要求】（1）掌握前序遍历二叉树的步骤，针对任意一棵二叉树能人工完成对二叉树的前序遍历。（2）能掌握栈的工作特点，并能正确应用这一特点实现对二叉树的遍历。【实验步骤】（1）运行PC中的MicrosoftVisualC++6.0程序，点击“文件”→“新建”→对话窗口中“文件”→“c++SourceFile”→在“文件名”中（2）输入“X1.cpp”→在“位置”中选择储存路径为“桌

6、面”→“确定”，(3)输入程序代码程序代码如下:voidFirstOrderAccess1(BTree*header){ BTree*stack[MAX_NODE]; BTree*p; inttop; top=0; p=header; do { while(p!=NULL) {  printf("BTree[%d]=%c“t",p->order,p->data);  if(p->rchild!=NULL)  stack[++top]=p->rchild;  p=p->lchild; } if(top!=0)  p=stack[top-

7、-]; }while((top>0)

8、

9、(p!=NULL));}