中南民族大学信管二叉树_数据结构实验报告.doc

中南民族大学管理学院学生实验报告 中南民族大学管理学院 学生实验报告 实验项目：二叉树的建立与遍历 课程名称：　 　数据结构　 　 年　 级：　 　2011　　　 专　 业：信息管理与信息系统 指导教师：　 　　 实验地点：管理学院综合实验室 完成日期： 2012年12月15日 小组成员： 微博@song-style是坏学长 2012 学年至2013 学年度第 1 学期 @song-style是坏学长 实验目的 掌握二叉树的建立与遍历 学会定义抽象数据类型 学会分析问题，设计适当的解决方案 实验内容 【问题描述】 建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】从键盘接受输入（先序），以二叉树表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 【测试数据】 ABC##DE#G##F###(其中#表示空格字符) 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 【选作内容】 采用非递归算法实现二叉树的遍历 实验步骤 （一）需求分析 （二）概要设计 （三）详细设计 （四）调试分析 1.我们用getchar（ch）读入一个字符时读不出来，后来我们用scanf(%c,ch)也不对，用//scanf(%c,%ch)和scanf(ch)是对的，但根据我们以前学的C语言语句结构，这后面的两个都是不对的。 （五）用户手册 （六）测试结果 （说明：将程序实际运行的结果截图后粘贴在这里。请删除这里的说明文字） （七）心得体会 （八）团队介绍 （九）附录：源程序清单 #include stdio.h #include malloc.h typedef struct node { char data; struct node *lchild; struct node *rchild; } Node,*pNode; void PreOrder(pNode m);//先序遍历 void InOrder(pNode m);//中序遍历 void PostOrder(pNode m);//后序遍历 pNode creat_1();//输入一个先序顺序的二叉树字符串 pNode creat();//按照先序遍历创建一个二叉树 char b[25]; int j; int main() { pNode m=NULL ; int i = 1,a; while(i) { printf(\n********请选择************\n); printf( 1 按先序遍历创建二叉树\n); printf( 2 按先序遍历遍历二叉树\n); printf( 3 按中序遍历遍历二叉树\n); printf( 4 按后序遍历遍历二叉树\n); printf( 输入以上数字之外的则退出); printf(\n**************************\n); printf(请输入:); scanf(%d,a); switch (a) { case 1: m=creat_1(); break; case 2: PreOrder(m); break; case 3: InOrder(m); break; case 4: PostOrder(m); break; default : i=0; } } } pNode creat_1() { printf(请输入字符串:(例如ABC##DE#G##F###,#代表空)\n); scanf(%s,b); return creat(); } pNode creat() { pNode m; char ch; ch=b[j]; j++; scanf(ch);//读入一个字符 if(ch==#) return NULL;//构造空树 //构造新结点 m=(pNode)malloc(sizeof(Node)); m-data=ch;//生成根结点 m-lchild=creat(); //构造左子树 m-rchild=creat(); //构造右子树 return m; } void PreOrder(pNode m) { if(!m) return; else{ printf(%c ,m-data); PreOrder(m-lchild); PreOrder(m-rchild);} } void InOrder(pNode m) { if(!m) return; else{