实验报告 二叉树的中序遍历
15091030 肖克
一、问题描述
二叉树一种是重要的数据结构。所谓遍历是指沿着某条搜索路线，依次对树中每个结 点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树 上最重要的运算之一，是二叉树上进行其它运算之基础。
二、数据结构
二叉树是每个节点最多有两个子树的树结构。 有了根结点之后， 每个顶点定义了唯一的 父结点，和最多 2 个子结点。其存储结构分为两种，链式存储方式和顺序存储方式。 遍历是对树的一种最基本的运算， 所谓遍历二叉树， 就是按一定的规则和顺序走遍二叉 树的所有结点， 使每一个结点都被访问一次， 而且只被访问一次。 由于二叉树是非线性结构， 因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
*rchild;
Status CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if (ch=='#') T= NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return OVERFLOW; T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } // CreateBiTree void PreOrder(BiTree T) { if(T) { printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } }
三、算法的设计和实现
首先输入先序序列 abc###de###，建立如下图所示的二叉树。
并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda
四、预期结果和实验中的问题
预期结果是正确的Βιβλιοθήκη 照定义给出的中序遍历输出结果。 实验中出现了中序遍历的过程中顺序有误的问题。
五、 C 源代码及运行截图
#include <stdio.h> #include <malloc.h> #define OK 1 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, }BiTNode,*BiTree;
void InOrder(BiTree T) { if(T) { InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T) { if(T) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } } void main() { BiTree T; CreateBiTree(T); printf("\n 先序遍历序列:"); PreOrder(T); printf("\n 中序遍历序列:"); InOrder(T); printf("\n 后序遍历序列:"); PostOrder(T); }