数据结构实验报告

1、，打印输出遍历结果。，并采用递归算，将遍历结果打印输出。先序： ABCDEGF ，以二叉链表作为存ABCDEFG ，输出的先序，中序，后序遍。二叉树可以表示为：- -WORD 格式，打印输出遍历结果。，并采用递归算，将遍历结果打印输出。先序： ABCDEGF ，以二叉链表作为存ABCDEFG ，输出的先序，中序，后序遍。二叉树可以表示为：- 实验目的（1）学会用先序创建一棵二叉树。（2）学会采用递归算法对二叉树进行先序、中序、后序遍历。（3）学会打印输出二叉树的遍历结果。实验内容【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序）【基本要求】从键盘接受输入（先序） ，以二叉链表作为存

2、储结构，建立二叉树（以先序来建立）法对其进行遍历（先序、中序、后序）【测试数据】ABC DEGF(其中表示空格字符 ) 则输出结果为中序： CBEGDFA 后序： CGBFDBA 【选作内容】采用非递归算法实现二叉树遍历。实验步骤（一）需求分析1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序）储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母历分别为 ABCDEGF,CBEGDFA,CGBFDBA-完整版学习资料分享D F ABC#DE#G#F# - -WORD 格式-可编辑-专业资料- D F ABC#DE#G#F# -

3、 A B C E G 接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列” 后，由用户在键盘上输入 ABC#DE#G#F#，之后相应的选择遍历及遍历结果显示出来。3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。4、测试数据（1）在键盘上输入的先序序列（2）先序遍历结果 ABCDEGF （3）中序遍历结果 CBEGDFA （4）后序遍历结果 CGBFDBA （二）概要设

4、计1、为实现上述程序功能，应以二叉树定义的相关操作和二叉树递归遍历的相关操-完整版学习资料分享/定义二叉树的指针/读入#，返回空指针/构造左子树/构造右子树/先序遍历/访问结点/先序遍历左子树/先序遍历右子树/中序遍历/中序遍历左子树/访问结点- -WORD 格式-可编辑-专业资料- /定义二叉树的指针/读入#，返回空指针/构造左子树/构造右子树/先序遍历/访问结点/先序遍历左子树/先序遍历右子树/中序遍历/中序遍历左子树/访问结点- 作为依据。有关以二叉链表作为存储结构，建立二叉树的操作为：typedef BTNode *BTree; BTree CreatBTree(void) BTree

5、 T; char ch; if(ch=getchar()=#) return(NULL); else T=(BTNode *)malloc(sizeof(BTNode); / 分配空间，生成结点T-data=ch; T-lchild=CreatBTree(); T-rchild=CreatBTree(); return(T); 2、而有关先序、中序、后序遍历的递归操作为：void Preorder(BTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); void Inorder(BTree T) if(

6、T) Inorder(T-lchild); printf(%c,T-data); -完整版学习资料分享/中序遍历右字树/后序遍历/后序遍历左子树/后序遍历右子树/访问结点- -WORD 格式-可编辑-专业资料- /中序遍历右字树/后序遍历/后序遍历左子树/后序遍历右子树/访问结点- Inorder(T-rchild); void Postorder(BTree T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); 3、本程序包含的模块（1）结点单元模块（2）构建先序二叉树模块（3）二叉树遍历模块（4）主程序模

7、块各模块之间的调用关系如下：主程序模块结点单元模块构建先序二叉树模块二叉树遍历模块（三）详细设计-完整版学习资料分享/二叉树的元素类型/自定义二叉树的结类型/定义二叉树的指针。/定义输入的数据类型/支持在键盘上输入先序二叉树/读入#，返回空指针#”号，否则先序二叉树将不完整。/分配空间，生成结点/构造左子树/构造右子树return(T) ，否则输入将一直持续下去不能跳出来。在#对于二叉树的遍历有着十分重要的作用，因此- -WORD 格式-可编辑-专业资/二叉树的元素类型/自定义二叉树的结类型/定义二叉树的指针。/定义输入的数据类型/支持在键盘上输入先序二叉树/读入#，返回空指针#”号，否则先序

8、二叉树将不完整。/分配空间，生成结点/构造左子树/构造右子树return(T) ，否则输入将一直持续下去不能跳出来。在#对于二叉树的遍历有着十分重要的作用，因此- 1、元素类型，结点类型和指针类型typedef struct node char data; struct node *lchild; struct node *rchild; BTNode; typedef BTNode *BTree; 2、定义类型之后，要以二叉链表作为存储结构，建立二叉树（以先序来建立）BTree CreatBTree(void) BTree T; char ch; if(ch=getchar()=#) ret

9、urn(NULL); 对于二叉树的先序输入，在输入中要注意的是对于空指针的把握， 由于是先序输入，在输入时要在确定的位置输入“else T=(BTNode *)malloc(sizeof(BTNode); T-data=ch; T-lchild=CreatBTree(); T-rchild=CreatBTree(); return(T); 当输入的叶子结点完整之后，要程序的设计过程中，在适当的位置插入要明白二叉树的先序创建过程如何运行。-完整版学习资料分享/先序遍历/访问结点/先序遍历左子树/先序遍历右子树/中序遍历/后序遍历- -WORD 格式-可编辑-专业资料- /先序遍历/访问结点/先序

10、遍历左子树/先序遍历右子树/中序遍历/后序遍历- 3、对于二叉树进行先序、中序、后序的遍历。void Preorder(BTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); 这个是先序遍历，先序遍历与中序遍历，后序遍历相似，都是以不同顺序访问子树及结点。先序遍历先访问根节点，先序遍历左子树，再先序遍历右子树。而中序遍历是中序遍历左子树，访问根节点，中序遍历右子树。后序遍历是后序遍历左子树，后序遍历右子树，后序遍历根节点。三个遍历虽说顺序不一致，但是在程序的编写上有很多可以相通的地方。以下分别是中序、后

11、序的程序：void Inorder(BTree T) if(T) Inorder(T-lchild); /中序遍历左子树printf(%c,T-data); /访问结点Inorder(T-rchild); /中序遍历右字树 void Postorder(BTree T) -完整版学习资料分享/后序遍历左子树/后序遍历右子树/访问结点/数的根结点/可供选择的整型变量 i /返回根结点/循环语句输入菜单序号- -WORD 格式-可编辑-专业资/后序遍历左子树/后序遍历右子树/访问结点/数的根结点/可供选择的整型变量 i /返回根结点/循环语句输入菜单序号- if(T) Postorder(T-lc

12、hild); Postorder(T-rchild); printf(%c,T-data); 4、主程序模块的链接。在这个模块中，不仅要实现二叉树先序序列从键盘的输入，还要实现选择三个遍历的输出。主函数的作用旨在使每个程序模块能够链接在一起，调用各个函数以实现最终的目的。void main() BTree root; int i; printf(n); printf( 请输入二叉树的先序序列，用 #代表虚结点 :); root=CreatBTree(); do printf(*SELECT*n); printf(t1: 先序遍历 n); printf(t2: 中序遍历 n); printf(t

13、3: 后序遍历 n); printf(t0:Exitn); printf(t*n); scanf(%d,&i);/switch(i) case 1:printf( 先序遍历结果为 :); -完整版学习资料分享1、2、3 数字实现Preorder - Inorder Postorde-WORD 格式-可编辑-专业资1、2、3 数字实现Preorder - Inorder PostordePreorder(root); break; case 2:printf( 中序遍历结果为 :); Inorder(root); break; case 3:printf( 后序遍历结果为 :); Postord

14、er(root); break; 在这三个选择中，充分调用了先序、中序、后序遍历函数，选择对三个遍历的输出打印。default:exit(1); printf(n); while(i!=0); 5、函数的调用关系图反映了演示程序的层次结构：main CreatBTree （四）调试分析1、实验涉及的部分包括用二叉链表创建先序二叉树，对二叉树进行三种遍历，最后是对三种遍历结果进行打印。在做这个实验的过程中，我们首先最先碰到的问题是用二叉链表存储先序二叉树，由于对二叉树存储的不深入了解，我们在输入数据时，只能对其无限输入，并不能及时的终止，导致的结果是程序停止不了，运行不下去。不能返回的问题困扰了

15、我们很久，在这个过程中，我们还尝试了一些用栈来对其进行存储，通过一遍遍的摸索，最终找到了正确的方法。在这个过程中，我们也对二叉树的存储-完整版学习资料分享在主程序的链接中， 创建二叉树，返回根节点。while 和 swith 语句，没有返回根结点，造成算法的DOS在主程序的链接中， 创建二叉树，返回根节点。while 和 swith 语句，没有返回根结点，造成算法的DOS 操作系统，本程序执行文件为“执行二叉树建立与遍- 有了更为深刻的了解，相信这在我们以后的学习中也有很大的帮助。2、在实验过程中，我们还有尝试了非递归的算法对于二叉树的遍历，递归算法和非递归算法各有千秋，产用递归算法更为简单明

16、了。3、根节点的运用没有得到合理的开发，接着是一个 do 循环对于选择三种遍历结果的打印输出和退出操作，在开始的程序设计阶段没有发挥作用，前期使用的是运行不能有序进行下去。4、刚开始是忽略了一些细节问题，对于元素类型，结点类型的定义没有认真检查，程序前期运行过程中有很多的失误，导致了效率低下。今后一定要重视确定参数的变量和赋值属性的区别和标志。5、程序的设计基本是由一个个子模块联系到一起，由于前期没有将这个程序的大致模型框架构架好，子模块之间的联系在主程序中就出现了一些问题，因此在以后的实验过程中，要首先构造大框架更有利于子模块的链接。（五）用户手册1、本程序的运行环境为历.exe”。2、进入

17、程序运行后会有说明指示首先创建二叉树按照完全二叉树的先序序列输入，以回车键结束，程序主界面就会形成：-完整版学习资料分享- -WORD 格式-可编辑-专业资料- - 3、按照要求输入各个功能的命令，程序接受命令后立即执行并且显示相应的结果。（六）测试结果（1）首先二叉链表存储（以先序创建）键盘输入（2）选择数字“ 1”，先序遍历 : -完整版学习资料分享- -WORD 格式-可编辑-专业资料- - (3)选择数字“ 2”，中序遍历：（4）选择数字“ 3”后序遍历：-完整版学习资料分享/二叉树的元素类型/自定义二叉树的结点类型/定义二叉树的指针- -WORD 格式-可编辑-专业资料- /二叉树的

18、元素类型/自定义二叉树的结点类型/定义二叉树的指针- （九）附录：源程序清单#include #include #include /* typedef struct node char data; struct node *lchild; struct node *rchild; BTNode; /* typedef BTNode *BTree; BTree CreatBTree(void) BTree T; char ch; -完整版学习资料分享/支持在键盘上输入先序二叉树/读入#，返回空指针/构造左子树/构造右子树/先序遍历/访问结点/先序遍历左子树/先序遍历右子树/中序遍历/中序遍历左子

19、树/访问结点/中序遍历右字树/后序遍历- -WORD 格式-可编辑-专业资料- /支持在键盘上输入先序二叉树/读入#，返回空指针/构造左子树/构造右子树/先序遍历/访问结点/先序遍历左子树/先序遍历右子树/中序遍历/中序遍历左子树/访问结点/中序遍历右字树/后序遍历- if(ch=getchar()=#) return(NULL); else T=(BTNode *)malloc(sizeof(BTNode); / 分配空间，生成结点T-data=ch; T-lchild=CreatBTree(); T-rchild=CreatBTree(); return(T); /* void Preor

20、der(BTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); /* void Inorder(BTree T) if(T) Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); /* void Postorder(BTree T) -完整版学习资料分享/后序遍历左子树/后序遍历右子树/访问结点/二叉树的根结点/返回根结点/do 做循环打印遍历结果输入菜单序号- -WORD 格式-可编辑-专业资/后序遍历左子树/后序遍历右子树/访问结点/二叉树

21、的根结点/返回根结点/do 做循环打印遍历结果输入菜单序号- if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); /* void main() BTree root; int i; printf(n); printf( 请输入二叉树的先序序列，用 #代表虚结点 :); root=CreatBTree(); do printf(*SELECT*n); printf(t1: 先序遍历 n); printf(t2: 中序遍历 n); printf(t3: 后序遍历 n); printf(t0:Exitn); printf(t*n); scanf(%d,&i);/switch(i) case 1:printf( 先序遍历结果为 :); Preorder(root); break; case 2:printf( 中序遍历结果为 :); Inorder(root); break; case 3:printf( 后序遍历结果为 :); -完整版学习资料分享- -WORD 格式-可编辑-专业资料- - Postorder(root); break; default:exit(1); printf(n); while(i!=0); 实验结果分析通