二叉树的遍历试验报告

1、二叉树的遍历实验报告一. 需求分析在二叉树的应用中，常常要求在树中査找具有某种特征的结点，或者对树中全部结点逐 一进行某种处理，这就是二叉树的遍历问题。对二叉树的数据结构进行泄义，建立一棵二叉树，然后进行各种实验操作。二叉树是一个非线性结构,遍历时要先明确遍历的规则，先访问根结点还时先访问子树, 然后先访问左子树还是先访问有右子树，这些要事先立好，因为采用不同的遍历规则会产生 不同的结果。本次实验要实现先序、中序、后序三种遍历。基于二叉树的递归左义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树 的以及用递归的方式进行二叉树的遍历。二、系统总框图三、各模块设计分析(1) 建立二叉树结构

2、建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则 来建立的。本实验用的是先序遍历的规则进行建树。二叉树用链表存储来实现，因此要先上义一个二叉树链表存储结构。因此要先疋义一个结构体。此结构体的每个结点都是由数据域data.左指针域Lchild.右指针域Rchild组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。要注意的是，第一步的时候一泄要先泄义一个结朿标志符号，例如空格键、#等。当 它遇到该标志时，就指向为空。建立左右子树时，仍然是凋用create ()函数，依此递归进行下去，直

3、到遇到结束标 志时停止操作。(2) 输入二叉树元素输入二叉树时，是按上而所确泄的遍历规则输入的。最后，用一个返回值来表示所 需要的结果。(3) 先序遍历二叉树当二叉树为非空时，执行以下三个操作：访问根结点、先序適历左子树、先序遍历 右子树。(4) 中序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序 遍历右子树。(5)后序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先 序遍历右子树。(6)主程序需列岀各个函数，然后进行函数调用。四、各函数定义及说明因为此二叉树是用链式存储结构存储的，所以泄义一个结构体用以存储。typedef

4、struct BiTNode char data;struct BiTNode *Lchild;struct BiTNode *Rchild;BiTNode, *BiTree;(1) 主函数main ()主程序要包括：定义的二叉树T、建树函数create ()、先序遍历函数Preorder ()、中序遍历函数Inorder ()、后序遍历函数Postorder ()。(2) 建树函数Create ()泄义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间 给T, T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调 用Create (),依次循环下去，直

5、到ch遇到空时，结束。最后要返回建立的二叉树T。(3) 先序遍历函数Preorder ()根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子, 依次进行下去。(4) 中序遍历函数Inorder ()根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处 的数据，再右指针指向右孩子，依次进行下去。(5) 后序遍历函数Postorder ()根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩 子，最后输出结点处的数据，依次进行下去。五. 使用说明在Turbo C的环境下，先按CtrHF9运行程序，此时就是建立二叉树的过程，例如输 入序列-+a

6、 *b -c d /e f输入过程中不要加回车，因为回车也有对应的ASCII码， 是要算字符的，输入完之后再按回车，用户界而上就能够看到结果了。期外你必须会手动建立一棵二叉树，保证你输入的序列能构成一棵二叉树，否则你怎么输入, 按最后按多少回车程序也不会结朿！六、源程序include "stdio. hinclude ''string h#include ''alloc h#define NULL 0typedef struct BiTNodechar data;struct BiTNode *Lchild;struct BiTNode *Rchild

7、;BiTNode,伙B订ree;BiTree Create 0char ch;BiTree T;scanf (z，%c，z, &ch);if(ch='')T二NULL;else T=(BiTNode *)malloc(sizeof(BiTNode);T->data=ch;T->Lchild=Create 0 ;T->Rchild=Create 0 ;return T;void Preorder(BiTree T)if(T)printf (/z%cz T->data);Preorder(T->Lchi1d);Preorder(T->Rc

8、hi1d); void Inorder(BiTree T)if(T)Inorder(T->Lchild);printf (/z%cz T->data);Inorder(T->RchiId);void Postorder(BiTree T)if(T)Postorder(T->LchiId);Postorder(T->RchiId);printf (z，%cz T->data);mainOBiTree T;clrscr0;printf (?，The elements is ：");T=Create0;printf("n");prin

9、tf (''The Preorder* s result is ：");Preorder(T);printf (/z nn");printf C'The Inorder's result is :;Inorder(T);printf ("nn");printf("The Postorder* s result is : ”);Postorder(T);getchO ;七. 测试数据八. 测试结果先庁遍历序列：",+, a, *, b, c, d, /, e, f ； 屮序遍历序列：a,+, b, *, c, d, e, /, f : 后序遍历序列:a, b, c, d, *, +, e, f,;cl C:TcTc.exeThe elements 13 : -«a xb -c d Ze