树型数据结构试验.docVIP

淮海工学院计算机科学系 实验报告书 课 程名： 《 数据结构》 题 目： 树型数据结构试验 班 级： 学 号： 姓 名： 树结构算法实现与应用报告要求 1目的与要求: 1）熟练掌握二叉树的二叉链表表示及前序创建算法与实现； 2）熟练掌握二叉树的前序、中序和后序递归遍历算法与实现； 3）掌握中序遍历线索二叉树的基本算法与实现 4）掌握中序遍历线索化二叉树的算法与实现； 5）按照实验题目要求独立完成实验内容（提交程序清单及相关实验数据与运行结果）； 6）认真书写实验报告,并按时提交（本次实验第9周周三以前提交，不得延误）。 2 实验内容或题目 实验内容: 1）按照先序序列建立下图所示二叉树的二插链表树，结点元素类型取字符型，树的字符序列从键盘逐个动态输入。 2）在第1）步建立好的二叉链表树上实施前序、中序和后序递归遍历，并输出相应遍历序列。 3) 在第1) 步建立好的二叉链表树上实施前序遍历的叶子结点输出及其个数统计。 4）在第1) 步建立好的二叉链表树上实施二叉树性质三的验证； 5）在第1）步建立好的二叉链表树上实施中序非递归遍历，并输出相应遍历序列(选做) 6）中序线索化第1）步所建立的二叉链表树(选做)。 7）中序遍历第6）步所建立的线索二叉树，并输出遍历结果(选做) （注释：实验要求完成的任务（各个实验内容）应以菜单机制显示和运行来逐项完成，即整个实验题目写一个主程序完成所有实验内容，并以菜单机制实施交互运行，而不要一个实验内容写一个主程序） 3 实验步骤与源程序 源程序： #include stdio.h #include malloc.h #include conio.h typedef char DataType; typedef struct Node { DataType 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); /*先序遍历左子树*/ PreOrder(root-RChild); /*先序遍历右子树*/ } } void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if(root!=NULL) { InOrder(root-LChild); /*中序遍历左子树*/ Visit(root-data); /*访问根结点*/ InOrder(root-RChild); /*中序遍历右子树*/ } } void PostOrder(BiTree root) /*后序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if(root!=NULL) { PostOrder(root-LChild); /*后序遍历左子树*/ PostOrder(root-RChild); /*后序遍历右子树*/ Visit(root-data); /*访问根结点*/ } } void PreLeaf(BiTree root) /*前序遍历的叶子结点输出*/ { if(root!=NULL) { if(root-LChild==NULLroot-RChild==NULL) printf(%c ,root-data ); PreLeaf(root-LChild); PreLeaf(root-RChild