淮海工学院 数据结构 第3次实验-树型数据结构

《淮海工学院 数据结构 第3次实验-树型数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：树型数据结构试验班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日《数据结构》实验报告-8-树结构算法实现与应用报告要求1目的与要求:1）熟练掌握二叉树的二叉链表表示及前序创建算法与实现；2）熟练掌握二叉树的前序、中序和后序递归遍历算法与实现；3）掌握中序遍历线索二叉树的基本算法与实现4）掌握中序遍历线索化二叉树的算法与实现；5）按照实验题目要求独立完成实验内容（提交程序清单及相关实验数据与运行结果）；6）认真书写实验报告,并按时提交（本次实验第9周周三以前提交

2、，不得延误）。2实验内容或题目实验内容:1）按照先序序列建立下图所示二叉树的二插链表树，结点元素类型取字符型，树的字符序列从键盘逐个动态输入。2）在第1）步建立好的二叉链表树上实施前序、中序和后序递归遍历，并输出相应遍历序列。3)在第1)步建立好的二叉链表树上实施前序遍历的叶子结点输出及其个数统计。4）在第1)步建立好的二叉链表树上实施二叉树性质三的验证；5）在第1）步建立好的二叉链表树上实施中序非递归遍历，并输出相应遍历序列(选做)6）中序线索化第1）步所建立的二叉链表树(选做)。7）中序遍历第6）步所建立的线索二叉树，并

3、输出遍历结果(选做)（注释：实验要求完成的任务（各个实验内容）应以菜单机制显示和运行来逐项完成，即整个实验题目写一个主程序完成所有实验内容，并以菜单机制实施交互运行，而不要一个实验内容写一个主程序）《数据结构》实验报告-8-ABCDEFG3实验步骤与源程序#include#include#includetypedefstructNode{chardata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;voidC

4、reateBiTree(BiTree*bt){charch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreateBiTree(&((*bt)->LChild));CreateBiTree(&((*bt)->RChild));}《数据结构》实验报告-8-}voidVisit(charch){printf("%c",ch);}voidPreOrder(BiTreeroot){if(root!=

5、NULL){Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);}}voidInOrder(BiTreeroot){if(root!=NULL){InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);}}voidPostOrder(BiTreeroot){if(root!=NULL){PostOrder(root->LChild);PostOrder(root->RChild);V

6、isit(root->data);}}voidPre(BiTreeroot){if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL){printf("%c",root->data);《数据结构》实验报告-8-}Pre(root->LChild);Pre(root->RChild);}}intLeafCount(BiTree&T){intnum1,num2,num3;if(!T)return0;if(T->LChild==NULL&&T->RChild==NULL)r

7、eturn1;num1=LeafCount(T->LChild);num2=LeafCount(T->RChild);num3=num1+num2;return(num3);}voidmain(){inti;BiTreeT;printf("创建先序遍历序列二插树");CreateBiTree(&T);star:printf("请选择您要进行的操作:");printf("1,显示先序遍历序列");printf("2，显示中序遍历序列");printf("3，显示后序遍历序列为");printf("4，显示前

8、序叶子节点及其个数");scanf("%d",&i);switch(i){case1:printf("先序遍历序列为:");PreOrder(T);printf("");gotostar;break;case2:printf("中序遍历序列为:");InOrder(T);print