二叉树的建立与遍历（实验报告）.doc

本科学生综合性实验报告学 院： 软件与通信工程学院 课程名称： 数据结构与算法 专业班级： 09通信工程1班 姓 名： 王燕 学 号： 0093731 学生实验报告（2）学生姓名王燕学号0093731同组人实验项目二叉树的建立和遍历必修 选修 演示性实验 验证性实验 操作性实验 综合性实验实验地点H113实验仪器台号指导教师蒋娜实验日期及节次周五8、9、A节一、实验目的1进一步掌握树的结构及非线性特点，递归特点。2进一步巩固对指针的使用，编写二叉树的创建和遍历基本操作的实现程序。二、实验内容建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。实验说明 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。测试数据ABC*DE*G*F*（其中*表示空格字符）则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA拓展要求采用非递归算法实现二叉树遍历。三、实验要求1用C+/C完成算法设计和程序设计并上机调试通过。2. 实验过程中学生调试完成，需向教师演示实验过程和结果。3撰写实验报告，提供实验结果和数据。4分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。5. 采用上机情况、程序质量、实习报告相结合的形式，满分为100分。四、实验仪器1. WindowsXP以上操作系统；2. Visual C+6.0语言环境；3. 每人一台PC机。五、实验内容和步骤1启动Windows XP操作系统打开计算机，启动Windows XP操作系统。2创建工作文件夹创建Visual C+ 6.0的工作文件夹。3启动Visual C+ 6.0建立一个空工程BiTree,在建立一个源文件bitree4.编写代码如下：#include#include#include#define MAX 50typedef struct Nodechar data;struct Node * LChild;struct Node * RChild;BiTNode, * BiTree;/建立二叉链表BiTNode *BiT_Create(char s ,int *pi)BiTNode *root;char ch;ch=s*pi;(*pi)+;if(ch=*) return NULL;root=(BiTNode*)malloc(sizeof(BiTNode);root-data=ch;root-LChild=BiT_Create(s,pi);root-RChild=BiT_Create(s,pi);return(root);/前序递归遍历void PreOrder(BiTree root)if(root!=NULL)printf(%c,root-data);PreOrder(root-LChild);PreOrder(root-RChild);/中序递归遍历void InOrder(BiTree root)if(root!=NULL)InOrder(root-LChild);printf(%c,root-data);InOrder(root-RChild);/后序递归遍历void PostOrder(BiTree root)if(root!=NULL)PostOrder(root-LChild);PostOrder(root-RChild);printf(%c,root-data);/前序非递归遍历二叉树void BiT_PreOrder(BiTNode *root)BiTNode *p,*nodeMAX;int top=0;p=root;dowhile(p!=NULL)if(p-data!=*) printf(%c,p-data);nodetop=p;top+;p=p-LChild;if(top0)top-;p=nodetop;p=p-RChild;while(top0 | p!=NULL);/中序非递归遍历二叉树void BiT_InOrder(BiTNode *root)BiTNode *p,*nodeMAX;int top=0;p=root;dowhile(p!=NULL)nodetop=p;top+;p=p-LChild;if(top0)top-;p=nodetop;printf(%c,p-data);p=p-RChild;while(top0 | p!=NULL);/后序非递归遍历二叉树void BiT_PostOrder(BiTNode *root)BiTNode *p,*nodeMAX;int top,flagMAX; top=0;p=root;dowhile(p!=NULL)nodetop=p;flagtop=0;top+;p=p-LChild;while(top0 & flagtop-1=1)top-;p=nodetop;printf(%c,p-data);if(top0)p=nodetop-1;flagtop-1=1;p=p-RChild;while(top0 );void Display(char str)printf(当前链表信息为：n%sn,str);void main( )char str30;BiTNode *root;int k=1,flag;while(k)int i=0;printf(nnttt二叉树的建立与遍历nn);printf(ttt1.先序建立二叉链表n);printf(ttt2.先序遍历二叉树n);printf(ttt3.中序遍历二叉树n);printf(ttt4.后序遍历二叉树n);printf(ttt5.显示二叉链表信息n);printf(ttt0.退出n); printf(请选择操作项目：);scanf(%d,&k);system(cls);switch(k)case 1:printf(请输入要建立的信息(*代表结点为空)：n); scanf(%s,str);root=BiT_Create(str,&i);system(pause); break;case 2:printf(请输入遍历方式( 0 代表递归遍历，1代表非递归遍历)：);scanf(%d,&flag);switch(flag)case 0: printf(先序递归遍历结果为：n); PreOrder(root); printf(n); system(pause); break;case 1: printf(先序非递归遍历结果为：n); BiT_PreOrder(root); printf(n); system(pause); break;case 3:printf(请输入遍历方式( 0 代表递归遍历，1代表非递归遍历)：);scanf(%d,&flag);switch(flag)case 0: printf(中序递归遍历结果为：n); InOrder(root); printf(n); system(pause); break;case 1: printf(中序非递归遍历结果为：n); BiT_InOrder(root); printf(n); system(pause); break;case 4:printf(请输入遍历方式( 0 代表递归遍历，1代表非递归遍历)：);scanf(%d,&flag);switch(flag)case 0: printf(后序递归遍历结果为：n); PostOrder(root); printf(n); system(pause); break;case 1: printf(后序非递归遍历结果为：n); BiT_PostOrder(root); printf(n); system(pause);break;case 5:Display(str);system(pause);break;case 0:break;default :printf(选择出错，请重新选择操作项目!n);system(pause);system(cls);5.编译、运行，结果如下：开始界面：建立一个二叉链表：显示当前二叉链表的信息：先序递归遍历二叉树：先序非递归遍历二叉树：中序递归遍历二叉树：中序序非递归遍历二叉树：后序递归遍历二叉树：后序非递归遍历二叉树：下面为重新建立二叉链表（也即更新二叉链表）后的操作信息：选择退出后的页面：四、结论1、实验结果 实现了以先序建立二叉链表以及按先序、中序、后序遍历二叉树的操作。其中先序、中序、后序遍历二叉树操作都包括递归和非递归方式。2、分析讨论 我的编程要求是全面、界面友好、具有主动输入选择权，为了界面友好我使用了分支选择函数switch()以及清屏函数system(“cls”)。并且该实验完全是自己编出来的。“先序建立一个二叉链表”选项既是建