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

1、实验目的（1）学会用先序创建一棵二叉树。（2）学会采用递归算法对二叉树进行先序、中序、后序遍历。（3）学会打印输出二叉树的遍历结果。实验内容【问题描述】建立一棵二叉树，并 对其进行遍历（先序、中序、后序），打印输出遍历结果。【基本要求】从键盘接受输入（先序），以二叉 链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进 行遍历（先序、中序、后序），将遍历结果打印输出。【测试数据】ABCDEGF(其中 表示空格字符)则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA【选作内容】采用非递归算法实现二叉树遍历。实验步骤（一）需求分析1、在这个过程中，接受遍历的二

2、叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要 创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母 ABCDEFG，输出的先序，中序，后序遍 历分别为 ABCDEGF,CBEGDFA,CGBFDBA。二叉 树可以表示为：中南民族大学管理学院学生实验报告ABDGFEC接受的输入数据在进行递归的先序，中序，后序遍历后，分 别将结果打印出来。2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列”后，由用户在键盘上输入 ABC#DE#G#F#，之后相应的选择遍历及遍历结果显示出来。

3、3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。中南民族大学管理学院学生实验报告4、测试数据（1）在键盘上输入的先序序列 ABC#DE#G#F#（2）先序遍历结果 ABCDEGF（3）中序遍历结果 CBEGDFA（4）后序遍历结果 CGBFDBA（二）概要设计1、为实现上述程序功能，应以二叉树定义的相关操作和二叉树递归遍历的相关操作为依据。有关以二叉 链表作为存 储结构，建立二叉树的操作为：typedef BTNode *BTree; /定义二叉树 的指针BTree CreatBTree(voi

4、d)BTree T;char ch;if(ch=getchar()=#)return(NULL); /读入#，返回空指针elseT=(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-lch

5、ild); /先序遍历左子树Preorder(T-rchild); /先序遍历右子树void Inorder(BTree T) /中序遍历if(T)Inorder(T-lchild); /中序遍历左子 树printf(“%c“,T-data); /访问结点Inorder(T-rchild); /中序遍历右字 树void Postorder(BTree T) /后序遍历if(T)中南民族大学管理学院学生实验报告Postorder(T-lchild); /后序遍历左子树Postorder(T-rchild); /后序遍历右子树printf(“%c“,T-data); /访问结点3、本程序包含的模块

6、（1）结点单元模块（2）构建先序二叉树模块（3）二叉树遍历模块（4）主程序模块各模块之间的调用关系如下：（三）详细设计1、元素类型，结点类型和指针类型主程序模块二叉树遍历模块结点单元模块构建先序二叉树模块中南民族大学管理学院学生实验报告typedef struct nodechar data; /二叉树的元素类型struct node *lchild;struct node *rchild;BTNode; /自定义二叉树的 结类型typedef BTNode *BTree; /定义二叉树的指 针2、定义类型之后，要以二叉链表作为存储结构，建立二叉树（以先序来建立）。BTree CreatBTr

7、ee(void)BTree T;char ch; /定义输入的数据类型if(ch=getchar()=#) /支持在键盘上输入先序二叉树return(NULL); /读入#，返回空指针对于二叉树的先序输入，在输入中要注意的是对于空指针的把握，由于是先序输入，在 输入时要在确定的位置输 入 “#”号，否则先序二叉树将不完整。elseT=(BTNode *)malloc(sizeof(BTNode); /分配空间，生成结点T-data=ch;T-lchild=CreatBTree(); /构造左子 树中南民族大学管理学院学生实验报告T-rchild=CreatBTree(); /构造右子树retu

8、rn(T);当输入的叶子结点完整之后，要 return(T)，否则输入将一直持续下去不能跳出来。在程序的设计过程中，在适当的位置插入#对于二叉树的遍历有着十分重要的作用，因此要明白二叉树的先序创建过程如何运行。3、对于二叉树进行先序、中序、后序的遍 历。void Preorder(BTree T) /先序遍历if(T)printf(“%c“,T-data); /访问结点Preorder(T-lchild); /先序遍历左子树Preorder(T-rchild); /先序遍历右子树这个是先序遍历，先序遍历与中序遍历，后序遍 历相似，都是以不同顺序访问子树及结点。先序遍历先访问根节点，先序遍历左子

9、树，再先序遍历右子树。而中序遍历是中序遍历左子树， 访问根节点，中序遍历右子树。后序遍历是后序遍历左子树，后序遍历右子中南民族大学管理学院学生实验报告树，后序遍历根节点。三个遍历虽说顺序不一致，但是在程序的编写上有很多可以相通的地方。以下分别是中序、后序的程序：void Inorder(BTree T) /中序遍历if(T)Inorder(T-lchild);/中序遍历左子树printf(“%c“,T-data); /访问结点Inorder(T-rchild);/中序遍历右字树void Postorder(BTree T) /后序遍历if(T)Postorder(T-lchild); /后序遍

10、历左子树Postorder(T-rchild); /后序遍历右子树printf(“%c“,T-data); /访问结点4、主程序模块的链接。在这个模块中，不仅要实现 二叉树先序序中南民族大学管理学院学生实验报告列从键盘的输入，还要实现选择三个遍历的输出。主函数的作用旨在使每个程序模块能够链接在一起，调用各个函数以实现最终的目的。void main()BTree root; /数的根结点int i; /可供选择的整型变量 i printf(“n“);printf(“请输 入二叉树 的先序序列，用 #代表虚结点:“);root=CreatBTree(); /返回根结点do /循环语句printf(

11、“*SELECT*n“);printf(“t1:先序遍 历n“);printf(“t2:中序遍 历n“);printf(“t3:后序遍 历n“);printf(“t0:Exitn“);printf(“t*n“);scanf(“%d“,/输入菜单序号switch(i)case 1:printf(“先序遍历结果为:“);中南民族大学管理学院学生实验报告Preorder(root);break;case 2:printf(“中序遍历结果为:“);Inorder(root);break;case 3:printf(“后序遍历结果为:“);Postorder(root);break;在这三个选择中，充分调用了先序、中序、后序遍 历 函数，选择1、2、3 数字实现对三个遍历的输出打印。default:exit(1);printf(“n“);while(i!=0);5、函数的调用关系图反映了演示程序的层次结构：mainCreatBTree InorderPreorder Postorder（四）调试分析1、实验涉及的部分包括用二叉链表创建先序二叉树，对二叉树进