数据结构实验报告3.docx

《数据结构实验报告3.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告3.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法试验报告专业信息与计算科学班级姓名学号试验项目试验三二叉树试验目的1、把握用递归方法实现二叉树的遍历。2、深入对二叉树的理解，逐步培育解决实际问题的编程力量。试验内容题目：编写二叉树的遍历操作函数。先序遍历，递归方法 re preOrder (TREE *tree)中序遍历，递归方法 re_midOrder (TREE *tree)后序遍历，递归方法 re_postOrder (TREE *tree)调用上述函数实现先序、中序和后序遍历二叉树操作。算法设计分析(-)数据结构的定义：二叉树的二叉链表结点存储类型定义typedef struct Node (DataType data

2、;struct Node *LChild;struct Node *RChild;BitNode,*BitTree;(二)总体设计：1 .主程序模块：建立二叉树：void CreatBiTree (BitTree *bt)用扩展先序遍历序列创建二 叉树，假如是当前树根置为空，否则申请一个新节点。2 .编程实现二叉树的前序、中序和后序遍历操作，输出遍历序列：1)先序遍历模块；2)中序遍历模块；3)后序遍历模块；(三)各函数的具体设计：L.建立二叉树存储类型=构造二叉树二二=void CreatBiTree(BitTree *bt)用扩展先序遍历序列创建二叉树，假如是当前树根置 为空，否则申请一个

3、新节点(char ch;ch=getchar ();if(ch=.)*bt=NULL;else(*bt= (BitTree) malloc (sizeof (BitNode); 申请一段关于该节点类型的存储空间(*bt)-data=ch;/生成根结点CreatBiTree(&(*bt)-LChild);构造左子树CreatBiTree (&(*bt)-RChiId); 构造右子树2.编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列1)先序遍历二叉树的递归算法如下： void PreOrder(BitTree root) if (root!=NULL) Visit(root -data

4、);PreOrder (root -LChild); 递归调用核心PreOrder (root -RChild); 2)中序遍历二叉树的递归算法如下： void InOrder(BitTree root) if (root!=NULL) InOrder(root -LChild);Visit (root -data);InOrder(root -RChild); 3)后序遍历二叉树的递归算法如下： void PostOrder(BitTree root) if (root!=NULL)PostOrder(root -LChild);PostOrder(root -RChild);Visit (

5、root -data);)试验测试结果及结果分析(-)测试结果C:Windowssystem32DebugSHUJU.exe*请输入二叉树中的元素( 以扩展先序遍历序列输入，其中.代表空子树):abc . . de先序遍历序列为:abcdegf中序强历序列为:cbegdfa后序遍历序列为=cgefdbaPress any key to continue(二)结果分析.进入演示程序后的显示主界面：请输入二叉树中的元素；先序、中序和后序遍历分别输出结果。1 .测试结果以扩展先序遍历序列输入，其中.代表空子树：abc. . de. g. . f-先序遍历序列为：abcdegf中序遍历序列为：cbeg

6、dfa后序遍历序列为：cgefdba试验总结二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。由于树的每一个 左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二 叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出挨次构成了不同的遍 历方法，这个过程需要根据不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用 选择语句来实现。附录试验程序代码(该部分请加注释)#include#includeftinclude ttinclude typedef int DataType;typedef struct Node创建结点类型结构体(Dat

7、aType data;struct Node *LChild;struct Node *RChild;)BitNode, *BitTree;void CreatBiTree(BitTree *bt)用扩展先序遍历序列创建二叉树，假如是当前树根置为空，否则申请一个新节点char ch;ch=getchar();if (ch=二.)*bt=NULL;else(*bt=(BitTree)malloc(sizeof(BitNode);(*bt)-data=ch;CreatBiTree(&(*bt)-LChiId);CreatBiTree(&(*bt)-RChiId);)void Visit (char

8、 ch) 访问根节点(printf(%c”,ch);)void PreOrder(BitTree root) 先序遍历二叉树的递归算法(if (root!=NULL)Visit (root -data);PreOrder (root -LChild);PreOrder (root -RChild); void InOrder(BitTree root) 中序遍历二叉树的递归算法 ( if (root!=NULL) InOrder(root -LChild);Visit (root -data);InOrder(root -RChild);) ) void PostOrder(BitTree r

9、oot)后序遍历求二叉树的递归算法if (root!=NULL) (PostOrder(root -LChild);PostOrder(root -RChild);Visit (root -data);)void main() (BitTree T;int layer;layer=0;printf (请输入二叉树中的元素(以扩展先序遍历序列输入，其中.代表空子树)：n);CreatBiTree(&T);printf (先序遍历序列为:);PreOrder(T);printf (z，n中序遍历序列为：“);InOrder(T);printf (n后序遍历序列为:);PostOrder (T);printf (n); )序号项目得分总分1试验报告排版（3分）2算法思想分析（6分）3源代码（6分）4试验结果及分析（5分）