中南民族大学管理学院学生实验报告.doc

实验目的(1)学会用先序创建一棵二叉树。(2)学会采用递归算法对二叉树进行先序、中序、后序遍历。(3)学会打印输出二叉树的遍历结果。实验内容【问题描述】建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。【基本要求】从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),并采用递归算法对其进行遍历(先序、中序、后序),将遍历结果打印输出。【测试数据】ABCффDEфGффFффф(其中ф表示空格字符)则输出结果为先序:ABCDEGF中序:CBEGDFA后序:CGBFDBA【选作内容】采用非递归算法实现二叉树遍历。实验步骤(一)需求分析1、在这个过程中,接受遍历的二叉树是从键盘接受输入(先序),以二叉链表作为存储结构,建立的二叉树。因此,首先要创建一棵二叉树,而这棵二叉树是先序二叉树。本演示程序中,集合的元素设定为大写字母ABCDEFG,输出的先序,中序,后序遍历分别为ABCDEGF,CBEGDFA,CGBFDBA。二叉树可以表示为:ABDGFEC接受的输入数据在进行递归的先序,中序,后序遍历后,分别将结果打印出来。2、在程序运行的过程中可以看到,以计算机提示用户执行的方式进行下去,即在计算机终端上提示“输入二叉树的先序序列”后,由用户在键盘上输入ABC##DE#G##F###,之后相应的选择遍历及遍历结果显示出来。3、程序执行的命令包括:首先是二叉树的先序序列被创建输入,其次是对输入进去的先序序列有次序的进行先序,中序,后序遍历。最后是打印出二叉树的遍历结果。4、测试数据(1)在键盘上输入的先序序列ABC##DE#G##F###(2)先序遍历结果ABCDEGF(3)中序遍历结果CBEGDFA(4)后序遍历结果CGBFDBA(二)概要设计1、为实现上述程序功能,应以二叉树定义的相关操作和二叉树递归遍历的相关操作为依据。有关以二叉链表作为存储结构,建立二叉树的操作为:typedefBTNode*BTree;//定义二叉树的指针BTreeCreatBTree(void){ BTreeT; charch; if((ch=getchar())=='#') return(NULL);//读入#,返回空指针else{ T=(BTNode*)malloc(sizeof(BTNode));//分配空间,生成结点 T->data=ch; T->lchild=CreatBTree();//构造左子树 T->rchild=CreatBTree();//构造右子树 return(T);}}2、而有关先序、中序、后序遍历的递归操作为:voidPreorder(BTreeT)//先序遍历{ if(T){ printf("%c",T->data);//访问结点 Preorder(T->lchild);//先序遍历左子树 Preorder(T->rchild);//先序遍历右子树 }}voidInorder(BTreeT)//中序遍历{ if(T) { Inorder(T->lchild);//中序遍历左子树 printf("%c",T->data);//访问结点 Inorder(T->rchild);//中序遍历右字树 }}voidPostorder(BTreeT)//后序遍历{ if(T) { Postorder(T->lchild);//后序遍历左子树 Postorder(T->rchild);//后序遍历右子树 printf("%c",T->data);//访问结点 }}3、本程序包含的模块(1)结点单元模块(2)构建先序二叉树模块(3)二叉树遍历模块(4)主程序模块各模块之间的调用关系如下:主程序模块结点单元模块构建先序二叉树模块二叉树遍历模块(三)详细设计1、元素类型,结点类型和指针类型typedefstructnode{ chardata;//二叉树的元素类型 structnode*lchild; structnode*rchild;}BTNode;//自定义二叉树的结类型typedefBTNode*BTree;//定义二叉树的指针2、定义类型之后,要以二叉链表作为存储结构,建立二叉树(以先序来建立)。BTreeCreatBTree(void){ BTreeT; charch;//定义输入的数据类型 if((ch=getchar())=='#')//支持在键盘上输入先序二叉树 return(NULL);//读入#,返回空指针对于二叉树的先序输入,在输入中要注意的是对于空指针的把握,由于是先序输入,在输入时要在确定的位置输入“#”号,否则先序二叉树将不完整。else{ T=(BTNode*)malloc(sizeof(BTNode));//分配空间,生成结点 T->data=ch; T->lchild=Crea