树型数据结构实验--二叉树.docVIP

淮海工学院计算机科学系 实验报告书 课 程名： 《 数据结构》 题 目： 树型数据结构试验 班 级： 学 号： 姓 名： 树结构算法实现与应用报告要求 1目的与要求: 1）熟练掌握二叉树的二叉链表表示及前序创建算法与实现； 2）熟练掌握二叉树的前序、中序和后序递归遍历算法与实现； 3）掌握中序遍历线索二叉树的基本算法与实现 4）掌握中序遍历线索化二叉树的算法与实现； 5）按照实验题目要求独立完成实验内容（提交程序清单及相关实验数据与运行结果）； 6）认真书写实验报告,并按时提交。 2 实验内容或题目 实验内容: 1）按照先序序列建立下图所示二叉树的二插链表树，结点元素类型取字符型，树的字符序列从键盘逐个动态输入。 2）在第1）步建立好的二叉链表树上实施前序、中序和后序递归遍历，并输出相应遍历序列。 3) 在第1) 步建立好的二叉链表树上实施前序遍历的叶子结点输出。 4) 在第1) 步建立好的二叉链表树上实施前序遍历的非叶子结点输出。 5）中序线索化第1）步所建立的二叉链表树(选做)。 6）中序遍历第5）步所建立的线索二叉树，并输出遍历结果(选做) 3 实验步骤与源程序 #include stdio.h #include malloc.h 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==NULLroot-RChild==NULL) printf(%c ,root-data); Pre(root -LChild); Pre(root -RChild); } } void Prl(BiTree root) { if(root!=NULL) { if(root-LChild!=NULL||root-RChild!=NULL) printf(%c,root-data); Prl(root-LChild); Prl(root-RChild); } } void main() { BiTree T; printf(创建先序遍历序列二插树); CreateBiTree(T); printf(先序遍历序列为:); PreOrder(T); printf(\n中序遍历序列为:); InOrder(T); printf(\n后序遍历序列为:); PostOrder(T); printf(\n前序遍历的叶子结点是:); Pre(T); printf(\n前序遍历的非叶子结点是:); Prl(T); printf(\n);