文档详情

数据结构实验题目元多项式.doc

发布:2017-03-25约6.85千字共20页下载文档
文本预览下载声明
数据结构实验报告 实验名称: 实验一题目3一元多项式 学生姓名: 卢跃凯 班 级: 信通12班 班内序号: 13号 学 号: 2012210344 日 期: 2013/11/13 1.实验要求 1 实验目的 通过选择下面两个题目之一进行实现,掌握如下内容: ? 掌握二叉树基本操作的实现方法 ? 学习使用二叉树解决实际问题的能力 题目1 ? 根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。 ? 二叉树的基本功能: ? 1、二叉树的建立 ? 2、前序遍历二叉树 ? 3、中序遍历二叉树 ? 4、后序遍历二叉树 ? 5、按层序遍历二叉树 ? 6、求二叉树的深度 ? 7、求指定结点到根的路径 ? 8、二叉树的销毁 ? 9、其他:自定义操作 ? 编写测试main()函数测试线性表的正确性 2. 程序分析 2.1 存储结构 采用二叉树的存储结构,其中每个二叉树的结点定义了一个结构体BiNodeT*lch;,该结构体包含三个元素,分别是一个T类型的数据域data,一个指向T类型的指针左孩子BiNodeT*lch;,一个指向T类型的指针右孩子,示意图如图所示。 在对二叉树的层序遍历算法的实现过程中,采用了队列的存储结构。队列的存储结构示意如图所示: 在二叉树的创建中,对于二叉树中每个结点的data 域的赋值,我们事先把这些data 储存在一个数组 中,通过对数组元素的调用事先对二叉树中每个结点的data 域的赋值。 2.2 关键算法分析 一:二叉树的建立: A. 自然语言描述: 1 首先判断调用的数组是否为空,如果该数组不为空,则把调用的数组的第一个元素的赋给根节点的data 域。 2 采用递归的思想,分别将根节点的左右孩子作为根节点,递归调用该函数。完成对左右子树的赋值。 3如果为空,直接将一个已经初始化好的根节点置为空。 B. 代码详细分析: void BiTreeT::Create (BiNodeT*R,T data[],int i) { //i表示位置,从1开始 if(data[i-1]!=0) { R = new BiNodeT; //创建根结点 R-data = data[i-1]; Create(R-lch,data,2*i); //创建左子树 Create(R-rch,data,2*i+1); //创建右子树 } else R = NULL; } 二:前序遍历二叉树: A. 自然语言描述: 1. 首先判断根结点是否为空,如果不为空,输出根结点data域中所存储的值。 2. 递归调用函数PreOrder,遍历左子树。 3. 递归调用函数PreOrder,遍历右子树。 B. 代码详细分析: void BiTreeT::PreOrder(BiNodeT*R) { if(R!=NULL) { coutR-data; //访问结点 PreOrder(R-lch); //遍历左子树 PreOrder(R-rch); //遍历右子树 } } 三:中序遍历二叉树: B. 自然语言描述: 1. 首先判断根结点是否为空,如果不为空,递归调用函数InOrder,遍历左子树。 2. 输出根结点data域中所存储的值。 3. 递归调用函数InOrder,遍历右子树。 B. 代码详细分析: void BiTreeT::InOrder(BiNodeT*R) { if(R!=NULL) { InOrder(R-lch); //遍历左子树 coutR-data; //访问结点 InOrder(R-rch); //遍历右子树 } } 三:后序遍历二叉树: C. 自然语言描述: 1.首先判断根结点是否为空,如果不为空,递归调用函数PostOrder,遍历左子树。 2.递归调用函数PostOrder,遍历右子树。 3.输出根结点data域中所存储的值。 B. 代码详细分析: void BiTreeT::PostOrder(BiNodeT *R) { if(R!=NULL) { PostOrder(R-lch); PostOrder(R-rch); coutR-data ; } } 三:层序遍历二叉树: D. 自然语言描述: 1. 根节点非空,入队。 2. 如果队列不空 { 队头元素出队 访问该元素 若该结点的左孩子非空,则左孩子入队; 若该结点的右孩子非空,则右孩子入队; } B. 代码详细分析 void BiTreeT::LevelOrder(BiNodeT *R) { BiNodeT *queue[100]; int f=0,r=0; if(R!=NULL) queue[++r]=R;
显示全部
相似文档