最新版数据结构实验报告Word格式文档下载.docx
《最新版数据结构实验报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《最新版数据结构实验报告Word格式文档下载.docx（37页珍藏版）》请在冰点文库上搜索。
6.输出二叉树b的叶子节点个数；
7.释放二叉树b；
主程序如下：
#include<
stdio.h>
typedefcharElemType;
typedefstructnode
{
ElemTypedata;
//数据元素
structnode*lchild;
//指向左孩子
structnode*rchild;
//指向右孩子
}BTNode;
externvoidCreateBTNode（BTNode*&
b,char*str）;
externBTNode*FindNode（BTNode*b,ElemTypex）;
externBTNode*LchildNode（BTNode*p）;
externBTNode*RchildNode（BTNode*p）;
externintBTNodeDepth（BTNode*b）;
externvoidDispBTNode（BTNode*b）;
externintBTWidth（BTNode*b）;
externintNodes（BTNode*b）;
externintLeafNodes（BTNode*b）;
externvoidDestroyBTNode（BTNode*&
b）;
voidmain（）
BTNode*b,*p,*lp,*rp;
;
CreateBTNode（b,"
A（B（D,E（H（J,K（L,M（,N）））））,C（F,G（,I）））"
）;
printf（"
二叉树的基本运算如下:
\n"
（1）输出二叉树:
"
DispBTNode（b）;
（2）H节点:
p=FindNode（b,'
H'
if（p!
=NULL）
lp=LchildNode（p）;
if（lp!
=NULL）
左孩子为%c"
lp->
data）;
else
无左孩子"
rp=RchildNode（p）;
if（rp!
右孩子为%c"
rp->
无右孩子"
}
（3）二叉树b的深度:
%d\n"
BTNodeDepth（b））;
（4）二叉树b的宽度:
BTWidth（b））;
（5）二叉树b的节点个数:
Nodes（b））;
（6）二叉树b的叶子节点个数:
LeafNodes（b））;
（7）释放二叉树b\n"
DestroyBTNode（b）;
运行结果如下：
7.2.设计一个程序exp7-2.cpp，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。
并对图7.1所示的二叉树b给出求解结果。
malloc.h>
#defineMaxSize100
//数据元素
//指向左孩子
//指向右孩子
voidPreOrder（BTNode*b）//先序遍历的递归算法
if（b!
%c"
b->
//访问根节点
PreOrder（b->
lchild）；
//递归访问左子树
rchild）;
//递归访问右子树
voidPreOrder1（BTNode*b）
BTNode*St[MaxSize],*p;
inttop=-1;
if（b!
top++;
//根节点入栈
St[top]=b;
while（top>
-1）//栈不为空时循环
p=St[top];
//退栈并访问该节点
top--;
p->
if（p->
rchild!
=NULL）//右孩子入栈
St[top]=p->
rchild;
lchild!
=NULL）//左孩子入栈
lchild;
voidInOrder（BTNode*b）//中序遍历的递归算法
InOrder（b->
lchild）;
//递归访问右子树
voidInOrder1（BTNode*b）
p=b;
-1||p!
while（p!
St[top]=p;
p=p->
if（top>
-1）
voidPostOrder（BTNode*b）//后序遍历的递归算法
PostOrder（b->
voidPostOrder1（BTNode*b）
BTNode*St[MaxSize];
BTNode*p;
intflag,top=-1;
//栈指针置初值
do
while（b!
=NULL）//将t的所有左节点入栈
b=b->
p=NULL;
//p指向当前节点的前一个已访问的节点
flag=1;
while（top!
=-1&
&
flag）
b=St[top];
//取出当前的栈顶元素
if（b->
rchild==p）//右子树不存在或已被访问,访问之
//访问*b节点
//p指向则被访问的节点
//t指向右子树
flag=0;
}while（top!
=-1）;
}
voidTravLevel（BTNode*b）
BTNode*Qu[MaxSize];
//定义循环队列
intfront,rear;
//定义队首和队尾指针
front=rear=0;
//置队列为空队列
rear++;
//节点指针进入队列
Qu[rear]=b;
while（rear!
=front）//队列不为空
front=（front+1）%MaxSize;
b=Qu[front];
//队头出队列
=NULL）//输出左孩子,并入队列
lchild->
rear=（rear+1）%MaxSize;
Qu[rear]=b->
=NULL）//输出右孩子,并入队列
rchild->
BTNode*b;
二叉树b:
层次遍历序列:
TravLevel（b）;
先序遍历序列:
递归算法:
PreOrder（b）;
非递归算法:
PreOrder1（b）;
中序遍历序列:
InOrder（b）;
InOrder1（b）;
后序遍历序列:
PostOrder（b）;
PostOrder1（b）;
7.3．对如图7.1所示的二叉树，设计一个程序exp7-3.cpp完成如下功能：
1.输出所有的叶子节点
2.输出所有从叶子节点到根节点的路径
3.输出2中的第一条最长的路径
}BTNode;
//在algo7-1.cpp文件中
voidAllPath（BTNode*b）
structsnode
BTNode*node;
//存放当前节点指针
intparent;
//存放双亲节点在队列中的位置
Qu[MaxSize];
//定义顺序队列
intfront,rear,p;
//定义队头和队尾指针
front=rear=-1;
Qu[rear].node=b;
//根节点指针进入队列
Qu[rear].parent=-1;
//根节点没有双亲节点
while（front<
rear）//队列不为空
front++;
b=Qu[front].node//队头出队列
lchild==NULL&
b->
rchild==NULL）//*b为叶子节点
%c到根节点逆路径:
p=front;
while（Qu[p].parent!
=-1）
Qu[p].node->
p=Qu[p].parent;
%c\n"
=NULL）//左孩子入队列
Qu[rear].node=b->
Qu[rear].parent=front;
=NULL）//右孩子入队列
voidAllPath1（BTNode*b,ElemTypepath[],intpathlen）
inti;
%c"
data,b->
for（i=pathlen-1;
i>
=0;
i--）
path[i]）;
path[pathlen]=b->
data;
//将当前节点放入路径中
pathlen++;
//路径长度增
AllPath1（b->
lchild,path,pathlen）;
//递归扫描左子树
rchild,path,pathlen）;
//递归扫描右子树
pathlen--;
//恢复环境
voidLongPath（BTNode*b,ElemTypepath[],intpathlen,ElemTypelongpath[],int&
longpathlen）
if（b==NULL）
if（pathlen>
longpathlen）//若当前路径更长,将路径保存在longpath中
longpath[i]=path[i];
longpathlen=pathlen;
else
LongPath（b->
lchild,path,pathlen,longpath,longpathlen）;
//递归扫描左子树
rchild,path,pathlen,longpath,longpathlen）;
//递归扫描右子树
voidDispLeaf（BTNode*b）
{if（b->
rchild==NULL）
DispLeaf（b->
ElemTypepath[MaxSize],longpath[MaxSize];
inti,longpathlen=0;
b的叶子节点:
DispLeaf（b）;
AllPath:
AllPath（b）;
AllPath1:
AllPath1（b,path,0）;
LongPath（b,path,0,longpath,longpathlen）;
第一条最长逆路径长度:
longpathlen）;
第一条最长逆路径:
for（i=longpathlen-1;
longpath[i]）;
}运行结果如下：
7.4.设计一个程序exp7-4.cpp，实现由先序遍历序列和中序遍历序列以及由中序遍历序列和后序遍历序列构造一棵二叉树的功能，要求以括号表示和凹入表示法输出该二叉树。
并用先序遍历序列“ABDEHJKLMNCFGI”和中序遍历序列“DBJHLKMNEAFCGI”以及由中序遍历序列“DBJHLKMNEAFCGI”和后序遍历序列“DJLNMKHEBFIGCA”进行验证。
#defineMaxWidth40
typedefstructnode
BTNode*CreateBT1（char*pre,char*in,intn）
BTNode*s;
char*p;
intk;
if（n<
=0）returnNULL;
s=（BTNode*）malloc（sizeof（BTNode））;
//创建二叉树节点*s
s->
data=*pre;
for（p=in;
p<
in+n;
p++）//在中序序列中找等于*ppos的位置k
if（*p==*pre）
break;
k=p-in;
lchild=CreateBT1（pre+1,in,k）;
rchild=CreateBT1（pre+k+1,p+1,n-k-1）;
returns;
BTNode*CreateBT2（char*post,char*in,intn,intm）
char*p,*q,*maxp;
intmaxpost,maxin,k;
maxpost=-1;
p++）//求in中全部字符中在post中最右边的那个字符
for（q=post;
q<
post+m;
q++）//在in中用maxp指向这个字符,用maxin标识它在in中的下标
if（*p==*q）
k=q-post;
if（k>
maxpost）
maxpost=k;
maxp=p;
maxin=p-in;
//创建二叉树节点*s
data=post[maxpost];
lchild=CreateBT2（post,in,maxin,m）;
rchild=CreateBT2（post,maxp+1,n-maxin-1,m）;
voidDispBTNode1（BTNode*b）//以凹入表表示法输出一棵二叉树
intlevel[MaxSize][2],top=-1,n,i,width=4;
chartype;
//根节点入栈
level[top][0]=width;
level[top][1]=2;
//2表示是根
//退栈并凹入显示该节点值
n=level[top][0];
switch（level[top][1]）
case0:
type='
L'
//左节点之后输出（L）
case1:
R'
//右节点之后输出（R）
case2:
B'
//根节点之后前输出（B）
for（i=1;
i<
=n;
i++）//其中n为显示场宽,字符以右对齐显示
"
%c（%c）"
data,type）;
for（i=n+1;
=MaxWidth;
i+=2）
--"
{//将右子树根节点入栈
level[top][0]=n+width;
//显示场宽增width
level[top][1]=1;
//1表示是右子树
{//将左子树根节点入栈
//显示场宽增width
level[top][1]=0;
//0表示是左子树
ElemTypepre[]="
ABDEHJKLMNCFGI"
ElemTypein[]="
DBJHLKMNEAFCGI"
ElemTypepost[]="
DJLNMKHEBFIGCA"
b=CreateBT1（pre,in,14）;
先序序列:
%s\n"
pre）;
中序序列:
in）;
构造一棵二叉树b:
括号表示法:
升级会员 