实验三二叉树.doc

数据结构实验报告
实验名称: 实验三——二叉树
学生姓名:
班级:
班内序号:
学号:
日期: 2012年12月1日

实验目的:
通过选择下面两个题目之一进行实现,掌握如下内容:
掌握二叉树基本操作的实现方法
了解赫夫曼树的思想和相关概念
学习使用二叉树解决实际问题的能力
根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。
二叉树的基本功能:
1、二叉树的建立
2、前序遍历二叉树
3、中序遍历二叉树
4、后序遍历二叉树
5、按层序遍历二叉树
6、求二叉树的深度
7、求指定结点到根的路径
8、二叉树的销毁
9、其他:自定义操作
编写测试main()函数测试线性表的正确性。
2. 程序分析
存储结构
采用二叉树的存储结构,其中每个二叉树的结点定义了一个结构体,该结构体包含三个元素,分别是一个T 类型的数据域data,一个指向T 类型的指针左孩子, 一个指向T 类型的指针右孩子,示意图如图所示。
lch
data
rch
rch
data
lch
rch
data
lch
在对二叉树的层序遍历的实现过程中,采用了队列的存储结构。队列的存储结构示意图如图所示:
关键算法分析
1、建立二叉树。
template <class T> void BiTree <T>::Create (BiNode<T> * &R,T data[] ,int i)//顺序结构存储二叉链表
{
//i表示位置,从1开始
if(data[i-1]!=0)
{
R=new BiNode<T>;//创建根节点

R->data=data[i-1];

Create(R->lch,data,2*i);//创建左子树

Create(R->rch,data,2*i+1);//创建右子树
}

else

R=NULL;
}
2、前序遍历二叉树(递归调用)。
template <class T> void BiTree <T>::PreOrder(BiNode<T> *R)//前序遍历的实现
{
if(R!=NULL)

{
cout<<R->data;//访问结点
PreOrder(R->lch);//遍历左子树
PreOrder(R->rch);//遍历右子树

}
}
3、中序遍历二叉树(递归调用)。
template <class T> void BiTree <T>::InOrder(BiNode<T> *R)//中序遍历的实现
{
if(R!=NULL)

{
PreOrder(R->lch);//遍历左子树
cout<<R->data;//访问结点
PreOrder(R->rch);//遍历右子树

}
}
4、后序遍历二叉树(递归调用)。
template <class T> void BiTree <T>::PostOrder(BiNode<T> *R)//后序遍历的实现
{
if(R!=NULL)

{
PreOrder(R->lch);//遍历左子树
PreOrder(R->