北邮数据结构第三次实验二叉树修改.docx
《北邮数据结构第三次实验二叉树修改.docx》由会员分享，可在线阅读，更多相关《北邮数据结构第三次实验二叉树修改.docx（14页珍藏版）》请在冰点文库上搜索。
北邮数据结构第三次实验二叉树修改
数据结构实验报告
实验名称：
实验三——题目1二叉树
姓名：
班级：
班内序号：
学号：
**********
1．实验要求
根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。
二叉树的基本功能：
1、二叉树的建立
2、前序遍历二叉树
3、中序遍历二叉树
4、后序遍历二叉树
5、按层序遍历二叉树
6、求二叉树的深度
7、求指定结点到根的路径
8、二叉树的销毁
9、其他：
自定义操作
编写测试main（）函数测试线性表的正确性
2.程序分析
2.1存储结构
使用二叉链表实现二叉树的存储，其示意图如下图所示：
2.2关键算法分析
前序遍历：
访问根节点
遍历左子树
遍历右子树
具体算法：
template
voidBiTree:
:
PreOrder（BiNode*R）//前序遍历
{
if（R!
=NULL）
{
cout<data;//访问结点
PreOrder（R->lch）;//遍历左子树
PreOrder（R->rch）;//遍历右子树
}
}
中序遍历：
template
voidBiTree:
:
Inorder（BiNode*R）
{
if（R!
=NULL）
{
Inorder（R->lchild）;//遍历左子树
cout<data;//访问结点
Inorder（R->rchild）;//遍历右子树
}
}
后序遍历
template
voidBiTree:
:
Postorder（BiNode*R）
{
if（R!
=NULL）
{
Postorder（R->lchild）;//遍历左子树
Postorder（R->rchild）;//遍历右子树
cout<data;//访问结点
}
}
层序遍历：
template
voidBiTree:
:
LevelOrder（BiNode*R）//层序遍历
{
BiNode*queue[100];//创建队
intf=0,r=0;//r为队尾指针，f为对头指针
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;
}
}
求深度:
template
intBiTree:
:
Depth（BiNode*R,intd）//求二叉树的深度
{
if（R==NULL）//如果二叉树为空，返回0
returnd;
if（（R->lch==NULL）&&（R->rch==NULL））//如果二叉树没有孩子，返回二叉树深度
returnd+1;
else//如果二叉树有孩子，做递归循环，并返回二叉树的最长路径，即二叉树深度
{
intm=GetDepth（R->lch,d+1）;
intn=GetDepth（R->rch,d+1）;
returnn>m?
n:
m;
}
}
求路径：
template
boolBiTree:
:
Getpath（BiNode*R,intd）
{
if（R==NULL）returnfalse;
if（R->data==d||Getpath（R->lchild,d）||Getpath（R->rchild,d））
{
cout<data<<"";
returntrue;
}
}
时间复杂度:
前序遍历：
O（n）
层序遍历：
O（n）
求二叉树深度：
O（n）
3.程序运行结果
3.1测试主函数流程
4.总结
该次试验中，二叉树的建立，前序遍历，中序遍历，后序遍历，求二叉树的深度以及二叉树的销毁都涉及到递归函数的巧妙应用。
二叉树的层序遍历则利用“队”的概念来实现——根节点入队，出队，并让其孩子按顺序入队。
个人觉得最难的部分莫过于求指定结点到根节点的路径。
对于寻找指定结点到根节点的路径，首先觉得应该是一个一个节点地寻找，直到找到要求的结点，寻找过程即用到二叉树的遍历，比如该实验中用到的前序遍历；再者，关于路径，想到“迷宫问题”，即使用“栈”存储寻找到指定结点的正确路径，并一一出栈，就可得到指定结点到根节点的路径。
对于编程，有些巧妙而经典的方法需要记忆，独自想出每种问题的算法比较困难，也浪费时间，而借鉴一些经典算法，有利于加快工作，也启迪我们一些算法的创新。
所以，我们需要记忆一些经典算法。
源程序：
#include
usingnamespacestd;
templatestructBiNode
{
Tdata;
BiNode*lchild;
BiNode*rchild;
};
templateclassBiTree
{
private:
voidCreate（BiNode*&R,Tdata[],inti,intn）;//创建二叉树
voidRelease（BiNode*R）;//释放二叉树
public:
BiNode*root;//根节点
BiTree（Tdata[],intn）;//构造函数
voidPreorder（BiNode*R）;//前序遍历
voidInorder（BiNode*R）;//中序遍历
voidPostorder（BiNode*R）;//后序遍历
voidLeveorder（BiNode*R）;//层序遍历
~BiTree（）;//析构函数
intCount（BiNode*R）;//结点数
boolGetpath（BiNode*R,intd）;//路径
intGetDepth（BiNode*R,intd）;//深度
};
template
voidBiTree:
:
Create（BiNode*&R,Tdata[],inti,intn）//表示位置，从开始，表示数组的长度
{
if（i<=n）
{
R=newBiNode;//创建根节点
R->data=data[i-1];
Create（R->lchild,data,2*i,n）;//创建左子树
Create（R->rchild,data,2*i+1,n）;//创建右子树
}
elseR=NULL;
}
templateBiTree:
:
BiTree（Tdata[],intn）
{
Create（root,data,1,n）;
}
//前序遍历
template
voidBiTree:
:
Preorder（BiNode*R）
{
if（R!
=NULL）
{
cout<data;//访问节点
Preorder（R->lchild）;//遍历左子树
Preorder（R->rchild）;//遍历右子树
}
}
//中序遍历
template
voidBiTree:
:
Inorder（BiNode*R）
{
if（R!
=NULL）
{
Inorder（R->lchild）;//遍历左子树
cout<data;//访问结点
Inorder（R->rchild）;//遍历右子树
}
}
//后序遍历
template
voidBiTree:
:
Postorder（BiNode*R）
{
if（R!
=NULL）
{
Postorder（R->lchild）;//遍历左子树
Postorder（R->rchild）;//遍历右子树
cout<data;//访问结点
}
}
//层序遍历
template
voidBiTree:
:
Leveorder（BiNode*R）
{
BiNode*queue[100];
intf=0;intr=0;//初始化空队列
if（R!
=NULL）queue[++r]=R;//根节点入队
while（f!
=r）
{
BiNode*p=queue[++f];//对头元素出队
cout<data;//出队打印
if（p->lchild!
=NULL）queue[++r]=p->lchild;//左孩子入队
if（p->rchild!
=NULL）queue[++r]=p->rchild;//右孩子入队
}
}
//析1函数
template
voidBiTree:
:
Release（BiNode*R）
{
if（R!
=NULL）
{
Release（R->lchild）;释放左子树
Release（R->rchild）;//释放右子树
deleteR;//释放根节点
}
}
//释放二叉树
template
BiTree:
:
~BiTree（）
{
Release（root）;
}
//求结点总数
templateintBiTree:
:
Count（BiNode*R）
{
if（R==NULL）return0;
else
{
intm=Count（R->lchild）;
intn=Count（R->rchild）;
returnm+n+1;
}
}
//求深度
template
intBiTree:
:
GetDepth（BiNode*R,intd）
{
if（R==NULL）returnd;
if（（R->lchild==NULL）&&（R->rchild==NULL））
returnd+1;
else
{
intm=GetDepth（R->lchild,d+1）;
intn=GetDepth（R->rchild,d+1）;
returnn>m?
n:
m;
}
}
//查询结点路径?
template
boolBiTree:
:
Getpath（BiNode*R,intd）
{
if（R==NULL）returnfalse;
if（R->data==d||Getpath（R->lchild,d）||Getpath（R->rchild,d））
{
cout<data<<"";
returntrue;
}
}
voidmain（）
{
chardata[50]="abcdefgh";
BiTreetree（data,8）;
cout<<"前序遍历为：
";
tree.Preorder（tree.root）;
cout<cout<<"中序遍历为：
";
tree.Inorder（tree.root）;
cout<cout<<"后序遍历为：
";
tree.Postorder（tree.root）;
cout<cout<<"层序遍历为：
";
tree.Leveorder（tree.root）;
cout<cout<<"结点数为：
";
cout<cout<intdepth=0;
cout<<"深度为：
";
cout<cout<cout<<"指定结点f,"<<"则到f的路径为：
";
tree.Getpath（tree.root,'f'）
}
升级会员 