实验目的 （1）学会用先序创建一棵二叉树。 （2）学会采用递归算法对二叉树进行先序、中序、后序遍历。 （3）学会打印输出二叉树的遍历结果。 实验内容 【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 【基本要求】 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 【测试数据】 ABCффDEфG ффFффф(其中ф表示空格字符) 则输出结果为 先序：ABCDEG F 中序：CBEG DFA 后序：CG BFDBA 【选作内容】 采用非递归算法实现二叉树遍历。 实验步骤 （一）需求分析 1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元素设定为大写字母 ABCDEFG ，输出的先序，中序，后序遍历分别为ABCDEG F,CBEG DFA,CG BFDBA。二叉树可以表示为： 中南民族大学管理学院学生实验报告 接受的输入数据在进行递归的先序，中序，后序遍历后，分别将结果打印出来。 2、在程序运行的过程中可以看到，以计算机提示用户执行的方式进行下去，即在计算机终端上提示“输入二叉树的先序序列”后，由用户在键盘上输入ABC##DE#G ##F###，之后相应的选择遍历及遍历结果显示出来。 3、程序执行的命令包括：首先是二叉树的先序序列被创建输入，其次是对输入进去的先序序列有次序的进行先序，中序，后序遍历。最后是打印出二叉树的遍历结果。 4、测试数据 （1）在键盘上输入的先序序列 ABC##DE#G ##F### （2）先序遍历结果ABCDEG F A B D G F E C 中南民族大学管理学院学生实验报告 （3）中序遍历结果CBEGDFA （4）后序遍历结果CGBFDBA （二）概要设计 1、为实现上述程序功能，应以二叉树定义的相关操作和二叉树递归遍历的相关操作为依据。有关以二叉链表作为存储结构，建立二叉树的操作为： typedef BTNode *BTree; //定义二叉树的指针 BTree CreatBTree(void) { BTree 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); } } ...
