第三次实验报告书.doc

淮海工学院计算机科学系
实验报告书

课程名： 《数据结构》
题 目： 实验三：树形数据结构试验一
——二叉树的基本操作和应用
班 级： D网络072
学 号： 510713220
姓 名： 田静

评语：

成绩： 指导教师： 朱敏

批阅时间：2008 年 10月29 日

《 数据结构 》实验报告 - 3 -

线性表算法实现与应用报告要求
1目的与要求:
1）熟练掌握二叉树的二叉链表表示创建算法与实现；
2）熟练掌握栈的前序、中序和后序递归遍历算法与实现；
3）熟练掌握前序、中序和后序遍历线索二叉树的基本算法与实现;
4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；
5）认真书写实验报告,并按时提交。
2 实验内容或题目
实验内容:
1）按照先序、中序、后序序列建立下图所示二叉树的二插链表树，结点元素类型取字符型，树的字符序列从键盘逐个动态输入。（第一组、第二组、第三组分别用先序、中序、后序序列建立，第四组可任选一种建立）
2）再上述建立好的二叉链表树上实施前序、中序和后序递归遍历，并输出相应遍历序列。（四个组均同时实现三种遍历）
3）前序、中序、后序遍历线索第1小题建立的二叉链表树。（第一组、第二组、第三组分别用后序、先序、中序遍历线索二叉树，第四组可任选一种遍历线索。）
A
B
C
D
E
F
G

3 实验步骤与源程序
#include <stdio.h>
#include <malloc.h>

typedef struct BiTNode{

int data;
struct BiTNode *lchild;
struct BiTNode *rchild;

}BiTNode,*BiTree;

void PreOrderTraverse(BiTree T)
{
if(T) {
printf(" %d ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
main()
{
BiTNode n1,n2,n3,n4,n5;
BiTree tree1;
n1.lchild=NULL;
n1.rchild=NULL;
n2.lchild=NULL;
n2.rchild=NULL;
n3.lchild=NULL;
n3.rchild=NULL;
n4.lchild=NULL;
n4.rchild=NULL;
n5.lchild=NULL;
n5.rchild=NULL;
n1.data=1;
n2.data=2;
n3.data=3;
n4.data=5;
n5.data=7;
n1.lchild=&n2;
n1.rchild=&n3;
n2.rchild=&n4;
n3.rchild=&n5;
tree1=&n1;
PreOrderTraverse(tree1);
}
4 测试数据与实验结果（可以抓图粘贴）

5 结果分析与实验体会
树属于非线性逻辑结构，线性逻辑结构中结点间具有惟一前驱，惟一后继的关系，而非线性结构中结点间前驱、后继的关系并不具有惟一性。其中，在树型结构中结点间的关系是前驱惟一而后继不惟一，即结点之间是多对多的关系。直观地看，树结构是指具有分支关系的结构。树型结构应用特别广泛，特别是在大量数据处理方面，更显得突出。
中间出过错误，但最后能调试出结果，做完题目。但是整体的技巧灵活性还需要加强，我会在以后的实验中，多多训练，提高灵活性。
通过本次上机实验我更能进一步的了解到树的实质内涵，及其在操作中该如何正确使用，处理。