数据结构B实验报告-单链表的实现.doc

实 验 报 告
〔 2014/ 2015 学年 第二学期〕
课程名称
数 据 结 构B
实验名称
单链表的实现
实验时间
2015
年
5
月
15
日
指导单位
电脑学院电脑科学与技术系
eCreate(Bt->rchild);
}
return Bt;
}
void Preorder(BTNode *Bt) //先序输出二叉树
{
if(Bt)
{
printf("%c ",Bt->element);
Preorder(Bt->lchild);
Preorder(Bt->rchild);
}
}
void Inorder(BTNode *Bt) //中序输出二叉树
{
if(Bt)
{
Inorder(Bt->lchild);
4
printf("%c ",Bt->element);
Inorder(Bt->rchild);
}
}
void Postorder(BTNode *Bt) //后序输出二叉树
{
if(Bt)
{
Postorder(Bt->lchild);
Postorder(Bt->rchild);
printf("%c ",Bt->element);
}
}
int Size(BTNode *Bt) //求二叉树中的结点数
{
int s,s1,s2;
if(!Bt) //二叉树为空，结点数为0
s=0;
else
5
{
s1=Size(Bt->lchild);
s2=Size(Bt->rchild);
s=s1+s2+1; //二叉树的结点数等于左右子树结点数的和在加1〔根结点〕
}
return s;
}
int Leaf(BTNode *Bt) //求二叉树中叶子个数
{
int ll,rl,tl;
if(!Bt) //二叉树为空，叶子个数为0
tl=0;
else if(!Bt->lchild&&!Bt->rchild) //叶子满足的条件〔左右孩子均为空〕
tl=1;
else
{
ll=Leaf(Bt->lchild);
rl=Leaf(Bt->rchild);
6
tl=ll+rl;
}
return tl;
}
int Depth(BTNode *Bt) //求二叉树的深度〔高度〕
{
int ld,rd,td;
if(!Bt)
td=0;
else
{
ld=Depth(Bt->lchild);
rd=Depth(Bt->rchild);
if(ld>=rd) //左右子树高度大的加1，即为二叉树的高度
td=ld+1;
else
td=rd+1;
}
return td;
7
}
void main()
{
BTNode *Bt;
int s,tl,td;
Bt=NULL;
printf("\nInput create order:\n");
Bt=PreCreate(Bt);
printf("\nThe preorder is:\n");
Preorder(Bt);
printf("\nThe inorder is:\n");
Inorder(Bt);
printf("\nThe postorder is:\n");
Postorder(Bt);
8
s=Size(Bt);
printf("\nThe size of the tree is:\n");
printf("%d\n",s);
tl=Leaf(Bt);
printf("\nThe leaves of the tree is:\n");
printf("%d\n",tl);
td=Depth(Bt);
printf("\nThe depth of the tree is:\n");
printf("%d\n",td);
}
9
实 验 报 告
10
五、实验小结〔包括问题和解决方法、心得体会、意见与建议等〕
这是一门纯属于设计的科目，它需用把理论变为上机调试。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我