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

淮海工学院计算机科学系实验报告书课 程名： 数据结构 题 目： 树型数据结构试验 班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 8 -树结构算法实现与应用报告要求1目的与要求:1）熟练掌握二叉树的二叉链表表示及前序创建算法与实现；2）熟练掌握二叉树的前序、中序和后序递归遍历算法与实现；3）掌握中序遍历线索二叉树的基本算法与实现 4）掌握中序遍历线索化二叉树的算法与实现；5）按照实验题目要求独立完成实验内容（提交程序清单及相关实验数据与运行结果）；6）认真书写实验报告,并按时提交（本次实验第9周周三以前提交，不得延误）。2 实验内容或题目 实验内容:1）按照先序序列建立下图所示二叉树的二插链表树，结点元素类型取字符型，树的字符序列从键盘逐个动态输入。2）在第1）步建立好的二叉链表树上实施前序、中序和后序递归遍历，并输出相应遍历序列。3) 在第1) 步建立好的二叉链表树上实施前序遍历的叶子结点输出及其个数统计。4）在第1) 步建立好的二叉链表树上实施二叉树性质三的验证；5）在第1）步建立好的二叉链表树上实施中序非递归遍历，并输出相应遍历序列(选做)6）中序线索化第1）步所建立的二叉链表树(选做)。7）中序遍历第6）步所建立的线索二叉树，并输出遍历结果(选做)（注释：实验要求完成的任务（各个实验内容）应以菜单机制显示和运行来逐项完成，即整个实验题目写一个主程序完成所有实验内容，并以菜单机制实施交互运行，而不要一个实验内容写一个主程序）ABCDEFG3 实验步骤与源程序 #include #include #include typedef struct Node char data; struct Node *LChild; struct Node *RChild; BiTNode, *BiTree;void CreateBiTree(BiTree *bt) char ch; ch = getchar(); if(ch=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode);(*bt)-data=ch; CreateBiTree(&(*bt)-LChild); CreateBiTree(&(*bt)-RChild); void Visit(char ch)printf(%c ,ch);void PreOrder(BiTree root)if (root!=NULL)Visit(root -data); PreOrder(root -LChild); PreOrder(root -RChild);void InOrder(BiTree root) if (root!=NULL)InOrder(root -LChild);Visit(root -data);InOrder(root -RChild);void PostOrder(BiTree root)if(root!=NULL)PostOrder(root -LChild);PostOrder(root -RChild);Visit(root -data); void Pre(BiTree root)if (root!=NULL)if(root-LChild=NULL&root-RChild=NULL)printf(%c ,root-data);Pre(root -LChild);Pre(root -RChild);int LeafCount(BiTree &T) int num1,num2,num3; if(!T) return 0; if(T-LChild=NULL & T-RChild=NULL) return 1; num1=LeafCount(T-LChild); num2=LeafCount(T-RChild); num3=num1+num2; return (num3);void main() int i;BiTree T;printf(创建先序遍历序列二插树);CreateBiTree(&T);star:printf(n请选择您要进行的操作:n);printf(1,显示先序遍历序列n);printf(2，显示中序遍历序列n);printf(3，显示后序遍历序列为n);printf(4，显示前序叶子节点及其个数n);scanf(%d,&i);switch (i)case 1:printf(先序遍历序列为:); PreOrder(T);printf(n);goto star;break;case 2:printf(中序遍历序列为:); InOrder(T);printf(n);goto star;break;case 3:printf(后序遍历序列为:); PostOrder(T);printf(n);goto star;break;case 4:printf(前序遍历的叶子结点是:);Pre(T);printf(n);printf(前序遍历的叶子结点个数是:); printf(%d,LeafCount(T);printf(n);printf(n);goto star;break; 4 测试数据与实验结果（可以抓图粘贴） 5 结果分析与实验体会主要遇到的问题就是用switch语句时不知道怎么反回主菜单，后来查找看书了解到可以用goto语句跳出返回到主菜单。创建二叉树参考程序#include #include #include typedef char DataType;typedef struct NodeDataType data;struct Node *LChild;struct Node *RChild;BiTNode, *BiTree;void CreateBiTree(BiTree *bt)char ch;ch = getchar(); if(ch=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); /生成一个新结点 (*bt)-data=ch; CreateBiTree(&(*bt)-LChild); /生成左子树 CreateBiTree(&(*bt)-RChild); /生成右子树void Visit(char ch)printf(%c ,ch);void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if (root!=NULL)Visit(root -data); /*访问根结点*/PreOrder(root -LChild