二叉树的建立与遍历实验报告(c语言编写-附源代码)(共9页).doc

《二叉树的建立与遍历实验报告(c语言编写-附源代码)(共9页).doc》由会员分享，可在线阅读，更多相关《二叉树的建立与遍历实验报告(c语言编写-附源代码)(共9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上二叉树的建立与遍历实验报告 级 班 年 月 日 姓名 学号_ 1实验题目建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。2需求分析本程序用VC编写，实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。 输入的形式和输入值的范围： 输入二叉树的先序，当其结点为空时，需要输入#。（输入的先序仅含字母和#） 输出的形式：输出二叉树的先序、中序、后序。 程序所能达到的功能：实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、 后序），并且打印输出遍历结果。 测试数据：输入数据：输入ABC#DE#G#F#输出结果：二叉树的

2、先序遍历为：ABCDEGF二叉树的中序遍历为：CBEGDFA二叉树的后序遍历为：CGEFDBA3概要设计1) 为了实现上述程序功能，需要定义二叉链表的抽象数据类型：typedef struct BinaryTreeNode TElemType data;/二叉树结点中的数据域 struct BinaryTreeNode *lchild , *rchild; /二叉树结点的左孩子和右孩子指针BinaryTreeNode ,*BiTree;基本操作：A. void CreateBinaryTree (BiTree &T) 初始条件：无操作结果：建立了二叉树。B. void PreOrder(BiT

3、ree T) 初始条件：存在一棵二叉树操作结果：先序遍历二叉树，并且输出先序遍历的结果。C. void MidOrder(BiTree T)初始条件：存在一棵二叉树操作结果：中序遍历二叉树，并且输出中序遍历的结果。D. void PostOrder(BiTree T)初始条件：存在一棵二叉树操作结果：后序遍历二叉树，并且输出后序遍历的结果。程序包含5个函数：主函数main()先序建立二叉树 void CreateBinaryTree (BiTree &T)先序遍历二叉树，并且输出先序遍历的结果 void PreOrder(BiTree T); 中序遍历二叉树，并且输出中序遍历的结果 void

4、MidOrder(BiTree T);序遍历二叉树，并且输出后序遍历的结果 void PostOrder(BiTree T);主函数main()CreateBinaryTreePreOrderMidOrderPostOrder各函数间关系如下：4详细设计1) 二叉链表的定义typedef struct BinaryTreeNode定义一个树结点的数据域;定义一个该结点的左孩子指针和右孩子指针;2) void CreateBinaryTree (BiTree &T)/先序建立二叉树 输入一个字符量;if(输入字符= #) T指针置值为NULL;else 动态申请一个指向二叉树结构体的指针 把输入

5、字符赋值给新指针的数据域data; 调用CreateBinaryTree(新指针的lchild成员); 调用CreateBinaryTree(新指针的rchild成员); 3) void PreOrder(BiTree T) /先序遍历二叉树 if(T指针不为NULL)输出T的data域;先序遍历左子树; 先序遍历右子树;4) void MidOrder(BiTree T) /中序遍历二叉树 if(T指针不为NULL)中序遍历左子树;输出T的data域;中序遍历右子树;5) void PostOrder(BiTree T) /中序遍历二叉树 if(T指针不为NULL) 后序遍历左子树;后序遍历

6、右子树;输出T的data域;5调试分析在编写程序过程中，我将scanf（”%c”,&ch）中的%c写成%d，程序运行了一段时间没有结果，经过检查，发现了这个错误。编写程序不能有一点马虎，否则后续纠错工作很辛苦，编写程序的进度变慢。6使用说明程序名为：二叉树遍历.exe，运行环境为DOS。程序执行后显示输入字符，先序建立二叉树：此时请输入一棵二叉树的先序，并且当结点为空时，输入#输入完成后，会输出该二叉树的先序遍历、中序遍历和后序遍历7测试结果1) 输入数据：输入ABC#DE#G#F#输出结果：二叉树的先序遍历为：ABCDEGF二叉树的中序遍历为：CBEGDFA二叉树的后序遍历为：CGEFDBA

7、2) 输入数据：输入AB#C#输出结果：二叉树的先序遍历为：ABC二叉树的中序遍历为：BAC二叉树的后序遍历为：BCA3) 二叉树如下：先序输入这棵二叉树，程序运行结果为：程序源代码：#include#includetypedef char TElemType;typedef struct BinaryTreeNode/二叉链表的存储结构TElemType data;struct BinaryTreeNode *lchild , *rchild;BinaryTreeNode ,*BiTree;void CreateBinaryTree (BiTree &T)/先序建立二叉树 char ch;s

8、canf(%c,&ch);if(ch = #) T=NULL;else if(!(T = (BinaryTreeNode *)malloc (sizeof(BinaryTreeNode) exit (-1);/判断malloc函数是否获得符合要求的内存块，是则继续程序，否则使用exit函数强制退出程序/如果malloc函数无法获得符合要求的内存块，malloc函数会返回NULL指针T-data=ch;CreateBinaryTree(T-lchild);CreateBinaryTree(T-rchild);void PreOrder(BiTree T)/先序遍历二叉树if(T)printf(%

9、c ,T-data);PreOrder(T-lchild); PreOrder(T-rchild);void MidOrder(BiTree T)/中序遍历二叉树if(T)MidOrder(T-lchild);printf(%c ,T-data);MidOrder(T-rchild);void PostOrder(BiTree T)/后序遍历二叉树if(T)PostOrder(T-lchild);PostOrder(T-rchild);printf(%c ,T-data);void main()BiTree Tree;printf(输入字符，先序建立二叉树：n);CreateBinaryTree(Tree);printf(二叉树的先序遍历为：n);PreOrder(Tree);printf(n二叉树的中序遍历为：n);MidOrder(Tree);printf(n二叉树的后序遍历为：n);PostOrder(Tree);getchar();getchar();专心-专注-专业