哈工大数据结构-树形结构及其应用.doc

《哈工大数据结构-树形结构及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：树形结构及其应用实验题目：树型结构的建立与遍历设计成绩报告成绩指导老师一、实验目的1.学会二叉树这一数据结构的用法，掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。2.熟练掌握二叉树与广义表之间的相互转换方法。3.熟练掌握二叉树的先序、中序、后序，递归与非递归遍历算法。4.学会二叉树线索化方法，并掌握线索二叉树的存储结构。5.熟练掌握线索二叉树的先序、中序、后序的遍历算法。二、实验要求及实验环境1.实验要求：(1)至少用两种方法，编写建立二叉树的二叉链表存储结构的程序

2、，并用广义表的形式显示并保存二叉树；(2)采用二叉树的二叉链表存储结构，编写程序实现二叉树的先序、中序和后序遍历的递归和非递归算法以及层序遍历算法，并显示二叉树和相应的遍历序列；(3)在二叉树的二叉链表存储结构基础上，编写程序实现二叉树的先序、中序和后序线索链表存储结构建立的算法，并用广义表的形式显示和保存二叉树的线索链表；(4)在二叉树的线索链表存储结构上，编写程序分别实现求一个结点的先序（中序、后序）的后继结点的算法；(5)在(4)基础上，编写程序实现对线索二叉树进行先序、中序和后序遍历的非递归算法，并显示线索二叉树和相应的遍历序列。 2.实验环境：Windows下的

3、dev-c++.三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）Createabit-tree1．逻辑设计主程序流程递归中序线索化·线索化递归中序线索化递归先序线索化以广义表格式输出树递归非递归先序遍历递归非递归中序遍历递归非递归后序遍历输出节点的后继节点遍历后序线索化遍历中序线索化遍历先序线索化线索二叉树链式结构定义typedefstructbitnode{chardata;structbitnode*lchild,*rchild;boolLTag,RTag;}bnode,*btree;2．物理设计Btreecreate()创

4、建一棵树并赋值应用数组栈btreea[MAX]VoidprintBTree(btreeT)以广义表形式打印树Voidpreorder(btreet)先序递归遍历Voidinorder(btreet)中序递归遍历Voidpostorder(btreet)后序递归遍历btreecopy(btreet)复制二叉树Intmain（）主函数Voidpreorder2(btreet)先序非递归遍历Voidinorder2(btreet)中序非递归遍历Voidpostorder2(btreet)后序非递归遍历层序遍历voidlevelorder(btreet)voidprethread

5、ing(btreep)先序线索化Btreepreorderthreading(btreeprehead,btrreeT);先序线索化voidprethreading(btreep)先序线索化Btreeinorderthreading(btreeprehead,btrreeT);中序线索化voidprethreading(btreep)先序线索化Btreepostorderthreading(btreeprehead,btrreeT);后序线索化寻找字符X处于线索树中位置btreelocate(chara,btreet)中序线索化后继节点Btreeinnext(btreep

6、);输出后继节点先序线索化后继节点Btreeprenext(btreep)Voidprintlist(btreet,boola)广义表形式输出线索化后的二叉树四、测试结果五、系统不足与经验体会不能连续输入多个广义表。函数设计不够简洁。没有实现非递归线索化加注释后修改代码方便六、附录：源代码（带注释）#include#include#defineMAX100typedefstructbitnode{chardata;structbitnode*lchild,*rchild;boolLTag,RTag;}bnode,*btree;//建立

7、树线索化结构体structbitnode*s[MAX];structbitnode*pre=NULL;btreecreate(){charch;scanf("%c",&ch);if(ch=='#')returnNULL;else{btreebt=(btree)malloc(sizeof(bnode));if(bt==NULL)returnNULL;else{bt->data=ch;bt->lchild=create();bt->rchild=create();returnbt;}}}btreecreate2(){inti,j;