2023年6月22日发(作者：)

《数据结构》课程实验报告

（实验4二叉树）

学生姓名

班 级

实验名称

实

验

概

述

学 号

指导老师

实验成绩

实验报告

实验目的：

（1）根据数组tree，建立与该二叉树对应的链式存储结构。

（2）对该二叉树采用中序遍历法显示遍历结果。

实验要求：

（1）在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。

（2）设计子函数，其功能为将顺序结构的二叉树转化为链式结构。

（3）设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。

（4）通过实例判断算法和相应程序的正确性。

实验基本原理：

（1）顺序存储的二叉树转化为链式存储结构，采用递归算法，递归函数的形式为Creab(tree,n,i,b)，其中形参：tree为顺序存储二叉树的数组，n为二叉树的结点数，i是二叉树某结点在数组tree中的下标（初始值为1），b为要建立的链式存储二叉树结点指针。转化时，首先建立*b结点，将tree[i]的值赋给*b的数据域，再调用递归函数分别构造左子树和右子树。

（2）中序遍历采用递归算法，即中序遍历左子树、访问根结点、中序遍历右子树。

程序代码：

/*实验3.1 二叉树的顺序存储结构和链式存储结构*/

实

验

内

容

#include

#include

#define MaxSize 20

/*二叉树链式存储结构结点定义*/

typedef struct BTreeNode

{

char data;

struct BTreeNode * left;

struct BTreeNode * right;

}BTreeNode;

BTreeNode * Creab(char *tree,int n,int i,BTreeNode *b); /*建立二叉树链式结构*/

void Inorder(BTreeNode *BT); /*中序遍历二叉树*/

void main()

{

BTreeNode *BT; /*根结点指针*/

char tree[MaxSize],c;

int n=0; /*二叉树的结点数*/

int i=1; /*结点在数组tree中的下标*/

printf("请输入完全二叉树的结点值（连续输入字符，以回车结束输入）:");