中央广播电视大学实验报告（学科：数据结构 ）
姓名班级学号实验日期
成绩评定教师签名批改日期
实验名称：实验三 二叉树
3.1 二叉树的顺序存储结构和链式存储结构
【问题描述】
设一棵完全二叉树用顺序存储方法存储于数组tree中，编写程序： （1） 根据数组tree，建立与该二叉树对应的链式存储结构。 （2） 对该二叉树采用中序遍历法显示遍历结果。 【基本要求】
（1） 在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。 （2） 设计子函数，其功能为将顺序结构的二叉树转化为链式结构。 （3） 设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。 （4） 通过实例判断算法和相应程序的正确性。 【实验步骤】
（1） 运行PC中的Microsoft Visual C++ 6.0程序，
（2） 点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件
名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，
（3） 输入程序代码， 程序代码如下: #include
void Creab(char *tree,int n,int i,NODE *p)。 void Inorder(NODE *p)。 void main() {
1 / 3
NODE *p。 char tree[MaxSize]。 int n=1。 int i=1。 printf(\请输入完全二叉数的节点值（连续输入字符，以回车结束输入。）:\。 while((tree[n] = getchar( )) != '\\n') n++。 tree[n] ='\\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。 else { p=(NODE *)malloc(sizeof(NODE))。 p->data=tree[i]。 printf(\。 Creab(tree,n,2*i,p->left)。 Creab(tree,n,2*i+1,p->right)。 } }
/*中序遍历树*/
void Inorder(NODE *p) { if(p!=NULL) { Inorder(p->left)。 printf(\。 Inorder(p->right)。 }
}
程序运行结果如下:
2 / 3
3.1 二叉树的遍历
【问题描述】
设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。
【基本要求】
（1） 掌握前序遍历二叉树的步骤，针对任意一棵二叉树能人工完成对二叉树的前序遍历。 （2） 能掌握栈的工作特点，并能正确应用这一特点实现对二叉树的遍历。 【实验步骤】
（1）运行PC中的Microsoft Visual C++ 6.0程序，
点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中（2）输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”， (3) 输入程序代码
程序代码如下:
void FirstOrderAccess1(BTree * header) {
BTree * stack[MAX_NODE]。 BTree *p。 int top。 top = 0。 p = header。 do {
while(p!=NULL) {
printf(\->order,p->data)。 if(p->rchild!=NULL)
stack[++top] = p->rchild。 p = p->lchild。 }
if(top!=0)
p = stack[top--]。
}while((top>0)||(p!=NULL))。 }
3 / 3