实验树型数据结构.docVIP

淮海工学院计算机工程学院 实验报告书 课程名： 《 数 据 结 构》 题 目： 实验2 树型数据结构及其应用 班 级： 姓 名： 实验2 树型数据结构 实验目的和要求 1．熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先序递归遍历、中序递归和非递归遍历、后序递归遍历。 2．掌握按先序遍历顺序输入数据，递归建立二叉树的方法。 3. 掌握建立哈夫曼树的方法，实现哈夫曼编码。 实验环境 Turbo C 或VC++ 实验学时 4学时，必做实验 实验题目 [问题描述] 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。 [基本要求] 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。 [测试数据] ABCффDEфGффFффф（其中ф表示空格字符） 输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 2．已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。 [提示]： （1）参习题6.20，实现逐层遍历 （2）队中保存每个结点的打印位置，其左、右子的距离 3．如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图6.34所示。 A B C D E 图6.34 F 4．按凹入表形式打印树形结构，如图6.35所示。 [提示]：参P.129例，用先根遍历。 A B C D E F G 图6.35 实现代码和运行结果 第一题（采用递归方法实现）： #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)//中序遍历二叉树 { 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);//后序遍历右子树