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

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

2、相应程序的正确性。【 实验步骤 】( 1 ) 运行 PC 中的 Microsoft Visual C+ 6.0 程序，(2)点击“文件新建”T对话窗口中“文件 C+ Source File ”宀在“文件 名”中输入“ Xl.cpp在“位置”中选择储存路径为“桌面确定”，( 3 ) 输入程序代码， 程序代码如下 :#include#include#include#include#include#define MaxSize 10typedef struct nodechar data 。struct node *left,*right 。NODE 。void Creab(char *tree,i

3、nt n,int i,NODE *p)。void Inorder(NODE *p)。void main()2/ 3NODE *p。char treeMaxSize。int n=1。int i=1。printf(”请输入完全二叉数的节点值(连续输入字符，以回车结束输入。)while(tree n = getchar( ) != n) n+。treen =n。p=NULL。Creab(tree ,n ,i,p)。Inorder(p)。void Creab(char *tree,int n,int i,NODE *p)if(i=n) p=NULL。elsep=(NODE *)malloc(sizeo

4、f(NODE) 。p-data=treei。prin tf(%c ,p-data )。Creab(tree ,n, 2*i,p-left)。Creab(tree, n, 2*i+1,p-right)。/*中序遍历树*/void In order(NODE *p)if(p!=NULL) Ino rder(p-left)。prin tf(%c ,p-data)。Ino rder(p-right)。程序运行结果如下贋输入完全二叉数的节点憤（连续输入字符，以回车结東输入。Zhc血抽ij abdhiejofg Press nny kesi to conlr inue:)。3/ 33.1二叉树的遍历【 问

5、题描述 】设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。【 基本要求 】( 1) 掌握前序遍历二叉树的步骤，针对任意一棵二叉树能人工完成对二叉树的前序遍历。( 2) 能掌握栈的工作特点，并能正确应用这一特点实现对二叉树的遍历。【 实验步骤 】( 1 )运行 PC 中的 Microsoft Visual C+ 6.0 程序，点击“文件”7“新建”T对话窗口中“文件”7“C+ Source File ”宀在“文件名”中(2 )输入“ X1.CPP”7在“位置”中选择储存路径为“桌面”7“确定”，(3) 输入程序代码程序代码如下 :void FirstOrderACCess1(BTree * header)BTree * staCkMAX_NODE 。BTree *P 。int toP 。toP = 0 。P = header 。dowhile(P!=NULL)Printf(BTree%d = %C“-t,oPrder,P-data) 。if(P-rChild!=NUL