数据结构二叉树的实验报告Word文件下载.docx
《数据结构二叉树的实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构二叉树的实验报告Word文件下载.docx（15页珍藏版）》请在冰点文库上搜索。
【3】算法空间时间复杂度分析：
O（n）
【4】代码逻辑：
如果位置小于数组的长度则
{创建根结点
将数组的值赋给刚才创建的结点的数据域
创建左子树，如果当前结点位置为i,则左孩子位置为2i
创建右子树，如果当前结点位置为i,则右孩子位置为2i+1
}
否则R为空
算法二：
CopyTree（BiNode<
*sR,BiNode<
dR）
）
复制构造函数
按照先创建根结点，再递归创建左右子树的方法来实现。
【4】代码逻辑:
如果源二叉树根结点不为空
则{
创建根结点
调用函数自身，创建左子树
调用函数自身，创建右子树
将该函数放在复制构造函数中调用，就可以实现复制构造函数
算法三：
PreOrder（BiNode<
*R）
二叉树的前序遍历
这个代码用的是优化算法，提前让当前结点出栈。
【4】代码逻辑（伪代码）
如果当前结点为非空，则
{
访问当前结点
当前结点入栈
将当前结点的左孩子作为当前结点}
如果为空
则栈顶结点出栈
则将该结点的右孩子作为当前结点
反复执行这两个过程，直到结点为空并且栈空
算法四：
InOrder（BiNode<
二叉树的中序遍历
递归
未知
如果R为非空：
则调用函数自身遍历左孩子
访问该结点
再调用自身访问该结点的右孩子
算法五：
LevelOrder（BiNode<
二叉树的层序遍历
【4】代码逻辑（伪代码）：
若根结点非空，入队
如果队列不空
对头元素出队
访问该元素
若该结点的左孩子为非空，则左孩子入队；
若该结点的右孩子为非空，则右孩子入队；
算法六：
Count（BiNode<
计算结点的个数
如果R不为空的话
调用函数自身计算左孩子的结点数
调用函数自身计算右孩子的结点数
template<
classT>
intBiTree<
:
if（R==NULL）return0;
else
{
intm=Count（R->
lchild）;
intn=Count（R->
rchild）;
returnm+n+1;
算法七：
Release（BiNode<
释放动态内存
左右子树全部释放完毕后再释放该结点
调用函数自身，释放左子树
调用函数自身，释放右子树
释放根结点
释放二叉树
voidBiTree<
if（R!
=NULL）
Release（R->
deleteR;
BiTree<
~BiTree（）
Release（root）;
intmain（）
inta[10]={1,2,3,4,5,6,7,8,9,10};
BiTree<
int>
BTree（a,10）;
Tree（BTree）;
BTree.PreOrder（BTree.root）;
cout<
<
endl;
Tree.PreOrder（Tree.root）;
BTree.InOrder（BTree.root）;
Tree.InOrder（Tree.root）;
BTree.PostOrder（BTree.root）;
Tree.PostOrder（Tree.root）;
BTree.LevelOrder（BTree.root）;
Tree.LevelOrder（Tree.root）;
intm=BTree.Count（BTree.root）;
cout<
m<
return0;
3.测试数据：
inta[10]={1,2,3,4,5};
12453
42513
45231
12345
5
4.总结：
4.1:
这次实验大多用了递归的算法，比较好理解。
4.2:
新得体会：
在创建二叉树的过程中，在没有思路的时候可以巧妙的利用递归算法。
但是我的代码仍然应该改进，应该进一步简化，减少算法的时间复杂度和空间复杂度。
#include<
iostream>
usingnamespacestd;
template<
classBiNode
{
public:
Tdata;
BiNode<
*lchild;
*rchild;
};
classBiTree
public:
BiNode<
*root;
BiTree（Tdata[],intn）;
BiTree（BiTree<
&
r）;
voidPreOrder（BiNode<
*R）;
voidInOrder（BiNode<
voidPostOrder（BiNode<
voidLevelOrder（BiNode<
intCount（BiNode<
~BiTree（）;
private:
voidCreate（BiNode<
R,Tdata[],inti,intn）;
voidCopyTree（BiNode<
dR）;
voidRelease（BiNode<
Create（BiNode<
if（i<
=n&
data[i-1]）
R=newBiNode<
;
R->
data=data[i-1];
Create（R->
lchild,data,2*i,n）;
rchild,data,2*i+1,n）;
elseR=NULL;
BiTree（Tdata[],intn）
Create（root,data,1,n）;
if（sR==NULL）
dR=NULL;
dR=newBiNode<
dR->
data=sR->
data;
CopyTree（sR->
lchild,dR->
rchild,dR->
BiTree（BiTree<
p）
CopyTree（p.root,this->
root）;
//this?
?
*S[100];
inttop=-1;
while（（top!
=-1）||（R!
=NULL））
if（R!
{
cout<
R->
data<
"
"
S[++top]=R;
R=R->
lchild;
}
R=S[top--];
rchild;
InOrder（R->
cout<
PostOrder（BiNode<
PostOrder（R->
*queue[100];
intf=0,r=0;
queue[++r]=R;
while（f!
=r）
*p=queue[++f];
p->
if（p->
lchild!
queue[++r]=p->
rchild!
inta[5]={1,2,3,4,5};
BTree（a,5）;
升级会员 