数据结构实验题目元多项式.doc
文本预览下载声明
数据结构实验报告
实验名称: 实验一题目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;
显示全部