数据结构实验三二叉树实验报告
数据结构实验报告
实验名称： 实验三——二叉树
学生姓名： XX
班 级：
班内序号：
学 号：
日 期：
1．实验要求
1.1实验目的
通过选择下面两个题目之一进行实现，掌握如下内容：
掌握二叉树基本操作的实现方法
了解赫夫曼树的思想和相关概念
学习使用二叉树解决实际问题的能力
1.2实验内容
根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。
二叉树的基本功能：
1、二叉树的建立
2、前序遍历二叉树
3、中序遍历二叉树
4、后序遍历二叉树
5、按层序遍历二叉树
6、求二叉树的深度
7、求指定结点到根的路径
8、二叉树的销毁
9、其他：自定义操作
编写测试main()函数测试线性表的正确性
2. 程序分析
2.1 存储结构
2.2 关键算法分析
创建一个二叉树
伪代码实现：
1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空；
2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或者右孩子，并把地址付给父结点，把data写入。
代码实现
void BiTree::create(BiNode* &R,int data[],int i,int n)//创建二叉树
{
if(i<=n)
{
R=new BiNode;
R->data=data[i-1];
create(R->lch,data,2*i,n);
create(R->rch,data,2*i+1,n);
}
else R=NULL;
}
(2)前序遍历
伪代码实现：
1.设置递归边界条件：if root==null则停止递归
打印起始节点的值，并先后在左子数右子数上递归调用打印函数
代码实现
void BiTree::preorder(BiNode* R)//前序遍历
{
if(R!=NULL)
{cout<data;
preorder(R->lch);
preorder(R->rch);
}
}
时间复杂度：O(n)
(3)中序遍历
伪代码实现：
设置递归边界条件：if root==null则停止递归
递归遍历左子树
打印根节点数据域内容
递归遍历右子树
代码实现
void BiTree::inorder(BiNode* R)//中序遍历
{
if(R!=NULL)
{inorder(R->lch);
cout<data;
inorder(R->rch);
}
}
时间复杂度：O(n)
(4)后序遍历
伪代码实现：
设置递归边界条件：if root==null则停止递归
递归遍历左子树
递归遍历右子树
访问根结点数据域
代码实现
void BiTree::postorder(BiNode* R)//后序遍历
{
if(R!=NULL)
{postorder(R->lch);
postorder(R->rch);
cout<data;
}
}
时间复杂度：O(n)
(5)层序遍历
伪代码实现
1.队列Q及所需指针的定义和初始化
2.如果二叉树非空，将根指针入队
3.循环直到队列Q为空
3.1 q=队列Q的队头元素出队
3.2 访问节点q的数据域 cout<data<
3.3 若节点q存在左孩子，则将左孩子指针入队
若节点q存在右孩子，则将右孩子指针入队
代码实现
void BiTree::levelordre(BiNode* R)//层序遍历
{
BiNode*queue[maxsize];
int f=0,r=0;
if(R!=NULL)
queue[++r]=R;
while(f!=r)
{BiNode*p=queue[++f];
cout<data;
if(p->lch!=NULL)
queue[++r]=p->lch;
if(p->rch!=NULL)
queue[++r]=p->rch;
}
}
时间复杂度：O(n)
(6)计算二叉树深度
伪代码实现：
1. 定义和初始化计数深度的参数
2．如果根节点为空，return0
3．如果根节点为非空，递归调用自身的到叶子节点到根的路径长度，输出其中较大的作为树的深度
代码实现
int BiTree::depth(BiNode* root)//求二叉树深度
{
int ld,rd;
if (root!=NULL)
{ld = 1+depth(root->lch);
rd = 1+depth(root->rch);
return ld>rd?ld:rd;
}
else return 0;
}
时间复杂度：O(n)
(7)输出指定结点到根结点的路径
伪代码实现：
1.建立一个存储路径结点结构，定义和初始化结
