数据结构实验三树与二叉树的操作实验指导Word格式.docx
《数据结构实验三树与二叉树的操作实验指导Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构实验三树与二叉树的操作实验指导Word格式.docx（30页珍藏版）》请在冰点文库上搜索。
）T=NULL;
else{
if（!
（T=（BiTNode*）malloc（sizeof（BiTNode））））exit（OVERFLOW）;
T->
data=ch;
//生成根结点
CreateBiTree（T->
lchild）;
//生成左子树
rchild）;
//生成右子树
}
returnOK;
}//CreateBiTree
参考程序：
//头文件BiTNode.h的内容如下：
#include<
stdio.h>
stdlib.h>
malloc.h>
#defineMAX20
#defineOK1
#defineERROR0
#defineNULL0
#defineOVERFLOW0
typedefcharTElemType;
typedefintStatus;
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
BiTreeCreateBiTree（BiTreeT）
{
charch;
scanf（"
%c"
&
if（ch=='
#'
/*#代表空指针*/
else
{
T=（BiTNode*）malloc（sizeof（BiTNode））;
if（!
T）exit（OVERFLOW）;
/*申请结点*/
data=ch;
/*生成根结点*/
lchild=CreateBiTree（T->
/*构造左子树*/
rchild=CreateBiTree（T->
/*构造右子树*/
}
//以下是主程序shiyan6_1_1.c
#include"
BiTNode.h"
main（）
BiTreeT=NULL;
printf（"
\n请读入构造二叉树的字符序列：
"
）;
CreateBiTree（T）;
/*建立一棵二叉树T*/
}
[实验2]二叉树的遍历
对一棵二叉链表表示的二叉树进行先序遍历、中序遍历、后序遍历和层序遍历并分别输出遍历的结点顺序。
分析：
二叉树的先序遍历是：
若二叉树为空，则空操作；
否则，访问根结点，先序遍历左子树，先序遍历右子树。
二叉树的中序遍历是：
否则，中序遍历左子树，访问根结点，中序遍历右子树。
二叉树的后序遍历是：
否则，后序遍历左子树，后序遍历右子树；
访问个结点。
二叉树的层序遍历是：
在访问二叉树的结点时按照自上而下，从左至右的顺序。
根作为第一层，根的孩子作为第二层，以此类推。
先序遍历二叉树递归算法
StatusPreOrderTraverse（BiTreeT,Status（*Visit）（TElemTypee））{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数，
//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦visit（）失败，则操作失败。
if（T）{
if（Visit（T->
data））
if（PreOrderTraverse（T->
lchild,Visit））
if（PreOrderTraverse（T->
rchild，Visit））
returnOK;
returnERROR;
}else
}//PreOrderTraverse
中序遍历的递归算法
StatusInOrderTraverse（BiTreeT,Status（*Visit）（TElemTypee））{
if（InOrderTraverse（T->
rchild，Visit））
if（Visit（T->
if（InOrderTraverse（T->
rchild，Visit））returnOK;
}//InOrderTraverse
后序遍历递归算法
StatusPostOrderTraverse（BiTreeT,Status（*Visit）（TElemTypee））{
if（PostOrderTraverse（T->
lchild,Visst））
if（PostOrderTraverse（T->
data））returnOK;
层次遍历二叉树的非递归算法
StatusLevelOrder（BiTreeT）{
//按层次遍历二叉树T，Q为队列
InitQueue（Q）;
If（T!
=NULL）{//若树非空
EnQueue（Q,T）;
//根结点入队列
While（!
QueueEmpty（Q））{
DeQueue（Q,b）;
//队首元素出队列
Visit（b->
data）;
//访问结点
If（b->
lchild!
=NULL）EnQueue（Q,b->
//左子树非空，则入队列
rchold!
=Null）EnQueue（Q,b->
//右子树非空，则入队列
}//while
}//if
}LevelOrder
//以下代码保存在文件shiyan6_1_2.c
StatusPrintElement（TElemTypee）
%2c"
e）;
StatusPreOrderTraverse（BiTreeT,Status（*Visit）（TElemType））
inti,j,k;
if（T==NULL）
else
{
i=Visit（T->
if（i）
j=PreOrderTraverse（T->
lchild,Visit）;
/*先序遍历左子树*/
if（j）
k=PreOrderTraverse（T->
rchild,Visit）;
/*先序遍历右子树*/
if（k）returnOK;
elsereturnERROR;
StatusInOrderTraverse（BiTreeT,Status（*Visit）（TElemType））
{/*中序遍历*/
if（T）
lchild,Visit））
if（Visit（T->
rchild,Visit））returnOK;
returnERROR;
}
elsereturnOK;
StatusPostOrderTraverse（BiTreeT,Status（*Visit）（TElemType））
{/*后序遍历*/
if（T）
rchild,Visit））
voidLevleOrder（BiTreeT）
{/*层次遍历二叉树T，从第一层开始，每层从左到右*/
BiTreeQueue[MAX],b;
/*用一维数组表示队列，front和rear分别表示队首和队尾指针*/
intfront,rear;
front=rear=0;
if（T）/*若树非空*/
Queue[rear++]=T;
/*根结点入队列*/
while（front!
=rear）
{/*当队列非空*/
b=Queue[front++];
/*队首元素出队列，并访问这个结点*/
b->
if（b->
=NULL）Queue[rear++]=b->
lchild;
/*左子树非空，则入队列*/
rchild!
rchild;
/*右子树非空，则入队列*/
}/*LevelOrder*/
voidmain（）
BiTreeT=NULL,B;
\n请读入构造二叉树的字符序列:
B=CreateBiTree（T）;
\n该二叉树的先序遍历是:
PreOrderTraverse（B,PrintElement）;
/*先序遍历二叉树*/
\n该二叉树的中序遍历"
InOrderTraverse（B,PrintElement）;
/*中序遍历二叉树*/
\n该二叉树的后序遍历"
PostOrderTraverse（B,PrintElement）;
/*后序遍历二叉树*/
\n该二叉树的层次遍历是:
LevleOrder（B）;
/*层次遍历二叉树*/
getchar（）;
[实验3]叶子结点统计
实验内容与要求：
统计一棵二叉树的叶子结点的个数
叶子结点是二叉树中既没有左孩子又没有有孩子的结点。
采用递归方式。
求一棵二叉树的叶子结点数的递归模型如下。
f（bt）=0;
若为空树时
f（bt）=1;
若只有根结点时,该根结点是叶结点
f（bt）=f（btree->
lchild）+f（btree->
其它
intleafcount（BiTreebt）
{/*统计二叉树bt中叶子结点数*/
intn;
if（bt==NULL）n=0;
elseif（bt->
lchild==NULL&
&
bt->
rchild==NULL）n=1;
elsen=leafcount（bt->
lchild）+leafcount（bt->
/*二叉树叶子结点数等于左、右子树的叶子结点数之和*/
returnn;
voidmain（）{
BiTreeT=NULL;
intm;
\n请输入要构造二叉树的结点序列:
T=CreateBiTree（T）;
m=leafcount（T）;
叶子结点数是:
%d"
m）;
[实验４]二叉树的深度统计
统计一棵二叉树的深度。
分析
若一棵二叉树是空树，则它的深度为０，否则它的深度取值为它的左、右子树中深度最大的深度加１。
intdepth（BiTreeT）{
/*求二叉树的深度*/
intdep1,dep2;
if（T==NULL）return0;
else{
dep1=depth（T->
dep2=depth（T->
returndep1>
dep2?
dep1+1:
dep2+1;
｝
}//depth
//以下代码存放在文件shiyan6_1_4.c文件中
intdepth（BiTreeT）
{/*求二叉树的深度*/
if（T==NULL）
else
{
dep1=depth（T->
dep2=depth（T->
returndep1>
}/*depth*/
BiTreeT=NULL;
\n请输入所构造二叉树的结点序列：
printf（"
\n二叉树的深度是:
depth（T））;
getchar（）;
[实验5]子树交换
试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。
子树交换就是将原来的二叉树中每个结点的左、右子树分别交换生成一棵新的二叉树，该二叉树与原来二叉树成对称形状。
先将二叉树根结点的左、右子树交换，然后在将左（右）子树的左、右子树交换直到子树为空树。
voidExchange（BiTreeT）
BiTNodep;
if （T）
p=T->
T->
lchild=T->
rchild=p;
Exchange（T->
//以下代码存放在文件shiyan6_1_5.c
BiTNode*p;
if（T）
p=T->
T->
lchild=T->
rchild=p;
Exchange（T->
\n请输入要构造二叉树的节点序列:
T=CreateBiTree（T）;
Exchange（T）;
[实验6]线索二叉树
实验内容与要求
构造一棵二叉链表表示的二叉树，并将其中序遍历线索化。
在一棵有N个结点的二叉树中，有N+1个指针域为空。
把这些空的指针项加以利用，将空的左指针指向其前驱，空的右指针指向后继，这样的指针九百能了线索。
线索化就是通过将空的左指针指向其前驱，空的右指针指向其后继，使非线性的二叉树线性化的过程。
线索二叉树采用线索链表表示，链表结构为图6-2（b）所示，在二叉链表结构（图6-2（a）所示）的基础上增加了两个标志域LTag和RTag。
这两个标志域当其值为1时，指向其前驱和后继。
值为0时保持其指针指向不变。
LTag
RTag
图6-2链表结构和线索链表结构
具体情况：
0lchild域指示结点的左孩子
LTag=
1lchild域指示结点的前驱
0rchild域指示结点的右孩子
RTag=
1rchild域指示结点的后继
中序遍历线索化二叉树就是在对线索树中序遍历的过程中为左标志域为1的结点寻找前驱，为由标志域为1的结点寻找后继。
结点的后继是中序遍历其右子树时访问的第一个结点，结点的前驱是中序遍历其左子树时最后访问的一个结点。
先构造一棵用线索链表表示的二叉树T，辅设一个全局变量pre用于记录离当前结点p最后“访问”的结点。
对该二叉树T进行中序遍历，生成线索化后二叉树的头结点Thrt，如果p的左标志域为空，则将其变为线索，并让其左指针指向pre，pre就是中序遍历二叉树Thrt时p结点的前驱；
如果pre的右标志域为空，则p就是pre的后继，将pre的右标志域变为线索。
//以下代码保存在文件shiyan6_1_6.c中
#include<
typedefcharDataType;
/*定义DataType类型*/
typedefenum{Link,Thread}PointerTag;
typedefstructnode{
DataTypedata;
structnode*lchild,*rchild;
/*左右孩子子树*/
PointerTagLTag,RTag;
}BiThrNode;
/*结点类型*/
typedefBiThrNode*BiThrTree;
/*二叉树类型*/
/*构造二叉树*/
void
CreatBinTree（BiThrTree*T）
{
/*构造二叉链表,注意:
输入序列是先序序列*/
if（（ch=getchar（））=='
'
）
*T=NULL;
/*读入非空格*/
T=（BiThrNode*）malloc（sizeof（BiThrNode））;
/*生成结点*/
（*T）->
（*T）->
LTag=Link;
RTag=Link;
CreatBinTree（&
/*构造左子树
*/
/*构造右子树*/
BiThrTreepre;
/*全局变量*/
voidInThreading（BiThrTreep）
if（p）
InThreading（p->
/*左子树线索化*/
p->
lchild）{p->
LTag=Thread;
lchild=pre;
}/*前驱线索*/
pre->
rchild）{pre->
RTag=Thread;
}/*后继线索*/
pre=p;
/*保持pre指向p*/
InThreading（p->
/*右子树线索化*/
intInOrderThreading（BiThrTree*Thrt,BiThrTreeT）
{/*中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点*/
if（!
（*Thrt=（BiThrTree）malloc（sizeof（BiThrNode））））
exit（0）;
（*Thrt）->
（*Thrt）->
/*建头结点*/
rchild=*Thrt;
/*右指针回指*/
if（!
lchild=*Thrt;
lchild=T;
pre=*Thrt;
InThreading（T）;
/*中序遍历进行中序线索化*/
pre->
/*最后一个结点线索化*/
rchild=pre;
return1;
//输出结点
intprint（BiThrTreee）
%d
%c
%d\n"
e->
LTag,e->
data,e->
RTag）;
//中序遍历线索化二叉树
intInOrderTraverse（BiThrTreeT,int（*visit）（BiThrTreee））
{/*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树
BiThrTreep;
p=T->
/*p指向根结点*/
while（p!
=T）/*空树或遍厉结束时，p==T*/
while（p->
LTag==Link）p=p->
visit（p））return0;
/*打印*/
RTag==Thread&
=T）
p=p->
rch
升级会员 