数据结构
实
验
报
告
1. 实验目的和内容：
掌握二叉树基本操作的实现方法
2. 程序分析
2.1存储结构
链式存储
2．程序流程
2.3关键算法分析
算法一：Create(BiNode<T>* &R,T data[],int i,int n)
【1】 算法功能：创建二叉树
【2】 算法基本思想：利用顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法来递归建立二叉链表的二叉树
【3】 算法空间时间复杂度分析：O(n)
【4】 代码逻辑：
如果位置小于数组的长度则
{ 创建根结点
二叉树的基本性质将数组的值赋给刚才创建的结点的数据域
创建左子树，如果当前结点位置为i,则左孩子位置为2i
创建右子树，如果当前结点位置为i,则右孩子位置为2i+1
}
否则R为空
算法二：CopyTree(BiNode<T>*sR,BiNode<T>* &dR)
）
【1】 算法功能：复制构造函数
【2】 算法基本思想：按照先创建根结点，再递归创建左右子树的方法来实现。
【3】 算法空间时间复杂度分析：O（n)
【4】 代码逻辑:
如果源二叉树根结点不为空
则{
创建根结点
调用函数自身，创建左子树
调用函数自身，创建右子树
}
将该函数放在复制构造函数中调用，就可以实现复制构造函数
算法三：PreOrder(BiNode<T>*R)
【1】 算法功能：二叉树的前序遍历
【2】 算法基本思想：这个代码用的是优化算法，提前让当前结点出栈。
【3】 算法空间时间复杂度分析：O（n）
【4】 代码逻辑（伪代码）
如果当前结点为非空，则
{
访问当前结点
当前结点入栈
将当前结点的左孩子作为当前结点}
如果为空
{
则栈顶结点出栈
则将该结点的右孩子作为当前结点
}
反复执行这两个过程，直到结点为空并且栈空
算法四：InOrder(BiNode<T>*R)
【1】 算法功能：二叉树的中序遍历
【2】 算法基本思想：递归
【3】 算法空间时间复杂度分析：未知
【4】 代码逻辑：
如果R为非空：
则调用函数自身遍历左孩子
访问该结点
再调用自身访问该结点的右孩子
算法五：LevelOrder(BiNode<T>*R)
【1】 算法功能：二叉树的层序遍历
【2】 算法基本思想：
【3】 算法空间时间复杂度分析：O（n）
【4】 代码逻辑（伪代码）：
若根结点非空，入队
如果队列不空
{
对头元素出队
访问该元素
若该结点的左孩子为非空，则左孩子入队；
若该结点的右孩子为非空，则右孩子入队；
}
算法六：Count(BiNode<T>*R)
【1】 算法功能：计算结点的个数
【2】 算法基本思想：递归
【3】 算法空间时间复杂度分析：未知
【4】 代码逻辑：
如果R不为空的话
{
调用函数自身计算左孩子的结点数
调用函数自身计算右孩子的结点数
}
template<class T>
int BiTree<T>::Count(BiNode<T>*R)
{
if(R==NULL)return 0;
else
{
int m=Count(R->lchild);
int n=Count(R->rchild);
return m+n+1;
}
}
算法七：Release(BiNode<T>*R)
【1】 算法功能：释放动态内存
【2】 算法基本思想：左右子树全部释放完毕后再释放该结点
【3】 算法空间时间复杂度分析：未知
【4】 代码逻辑：
调用函数自身，释放左子树
调用函数自身，释放右子树
释放根结点
释放二叉树
template<class T>
void BiTree<T>::Release(BiNode<T>*R)
{
if(R!=NULL)
{
Release(R->lchild);
Release(R->rchild);
delete R;
}
}
template<class T>
BiTree<T>::~BiTree()
{
Release(root);
}
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
BiTree<int> BTree(a,10);
BiTree<int>Tree(BTree);
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论