数据结构C语言版树的双亲表存储表示.docx
《数据结构C语言版树的双亲表存储表示.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版树的双亲表存储表示.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构C语言版树的双亲表存储表示
/*
数据结构C语言版树的双亲表存储表示
P135
编译环境：
Dev-C++4.9.9.2
日期：
2011年2月13日
*/
#include
typedefcharTElemType;
//树的双亲表存储表示
#defineMAX_TREE_SIZE100
typedefstruct
{
TElemTypedata;//数据域
intparent;//双亲位置域
}PTNode;//结点结构
typedefstruct
{
PTNodenodes[MAX_TREE_SIZE];//存储结点的数组
intn;//结点数
}PTree;
typedefstruct
{
intnum;
TElemTypename;
}QElemType;//定义队列元素类型
typedefstructQNode
{
QElemTypedata;//数据域
structQNode*next;//指针域
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront,//队头指针，指针域指向队头元素
rear;//队尾指针，指向队尾元素
}LinkQueue;
TElemTypeNil='';//以空格符为空
intInitTree（PTree*T）
{//操作结果:
构造空树T
（*T）.n=0;
return1;
}
voidDestroyTree（）
{
//由于PTree是定长类型,无法销毁
}
//构造一个空队列Q
intInitQueue（LinkQueue*Q）
{
（*Q）.front=（*Q）.rear=（QueuePtr）malloc（sizeof（QNode））;//动态分配一个空间
if（!
（*Q）.front）
exit（0）;
（*Q）.front->next=NULL;//队头指针指向空，无数据域，这样构成了一个空队列
return1;
}
//若Q为空队列,则返回1,否则返回0
intQueueEmpty（LinkQueueQ）
{
if（Q.front==Q.rear）
return1;
else
return0;
}
//插入元素e为Q的新的队尾元素
intEnQueue（LinkQueue*Q,QElemTypee）
{
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）//存储分配失败
exit（0）;
//生成一个以为e为数据域的队列元素
p->data=e;
p->next=NULL;
//将该新队列元素接在队尾的后面
（*Q）.rear->next=p;
（*Q）.rear=p;
return1;
}
//若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0
intDeQueue（LinkQueue*Q,QElemType*e）
{
QueuePtrp;
if（（*Q）.front==（*Q）.rear）
return0;
p=（*Q）.front->next;//队头元素
*e=p->data;
（*Q）.front->next=p->next;
if（（*Q）.rear==p）
（*Q）.rear=（*Q）.front;
free（p）;
return1;
}
//构造树T
intCreateTree（PTree*T）
{
LinkQueueq;
QElemTypep,qq;
inti=1,j,l;
charc[MAX_TREE_SIZE];//临时存放孩子结点数组
InitQueue（&q）;//初始化队列
printf（"请输入根结点（字符型,空格为空）:
"）;
scanf（"%c%*c",&（*T）.nodes[0].data）;//根结点序号为0,%*c吃掉回车符
if（（*T）.nodes[0].data!
=Nil）//非空树
{
（*T）.nodes[0].parent=-1;//根结点无双亲
qq.name=（*T）.nodes[0].data;
qq.num=0;
EnQueue（&q,qq）;//入队此结点
while（iQueueEmpty（q））//数组未满且队不空
{
DeQueue（&q,&qq）;//出队一个结点
printf（"请按长幼顺序输入结点%c的所有孩子:
",qq.name）;
gets（c）;
l=strlen（c）;
for（j=0;j{
（*T）.nodes[i].data=c[j];
（*T）.nodes[i].parent=qq.num;
p.name=c[j];
p.num=i;
EnQueue（&q,p）;//入队此结点
i++;
}
}
if（i>MAX_TREE_SIZE）
{
printf（"结点数超过数组容量\n"）;
exit（0）;
}
（*T）.n=i;
}
else
（*T）.n=0;
return1;
}
#defineClearTreeInitTree//二者操作相同
//若T为空树,则返回1,否则返回0
intTreeEmpty（PTreeT）
{
if（T.n）
return0;
else
return1;
}
//返回T的深度
intTreeDepth（PTreeT）
{
intk,m,def,
max=0;//存储深度
for（k=0;k{
def=1;//初始化本际点的深度
m=T.nodes[k].parent;
while（m!
=-1）
{
m=T.nodes[m].parent;
def++;
}
if（maxmax=def;
}
returnmax;//最大深度
}
//返回T的根
TElemTypeRoot（PTreeT）
{
inti;
for（i=0;iif（T.nodes[i].parent<0）
returnT.nodes[i].data;
returnNil;
}
//返回第i个结点的值
TElemTypeValue（PTreeT,inti）
{
if（ireturnT.nodes[i].data;
else
returnNil;
}
//改cur_e为value
intAssign（PTree*T,TElemTypecur_e,TElemTypevalue）
{
intj;
for（j=0;j<（*T）.n;j++）
{
if（（*T）.nodes[j].data==cur_e）
{
（*T）.nodes[j].data=value;
return1;
}
}
return0;
}
//若cur_e是T的非根结点,则返回它的双亲,否则函数值为＂空＂
TElemTypeParent（PTreeT,TElemTypecur_e）
{
intj;
for（j=1;jif（T.nodes[j].data==cur_e）
returnT.nodes[T.nodes[j].parent].data;
returnNil;
}
//若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回＂空＂
TElemTypeLeftChild（PTreeT,TElemTypecur_e）
{
inti,j;
for（i=0;iif（T.nodes[i].data==cur_e）//找到cur_e,其序号为i
break;
for（j=i+1;j//根据树的构造函数,最左孩子（长子）的序号＜其它孩子的序号
if（T.nodes[j].parent==i）
returnT.nodes[j].data;
returnNil;
}
//若cur_e有右（下一个）兄弟,则返回它的右兄弟,否则返回＂空＂
TElemTypeRightSibling（PTreeT,TElemTypecur_e）
{
inti;
for（i=0;iif（T.nodes[i].data==cur_e）//找到cur_e,其序号为i
break;
if（T.nodes[i+1].parent==T.nodes[i].parent）
//根据树的构造函数,若cur_e有右兄弟的话则右兄弟紧接其后
returnT.nodes[i+1].data;
returnNil;
}
//输出树T
intPrint（PTreeT）
{
inti;
printf（"结点个数=%d\n",T.n）;
printf（"结点双亲\n"）;
for（i=0;i{
printf（"%c",Value（T,i））;//结点
if（T.nodes[i].parent>=0）//有双亲
printf（"%c",Value（T,T.nodes[i].parent））;//双亲
printf（"\n"）;
}
return1;
}
//插入c为T中p结点的第i棵子树
intInsertChild（PTree*T,TElemTypep,inti,PTreec）
{
intj,k,l,f=1,n=0;//设交换标志f的初值为1,p的孩子数n的初值为0
PTNodet;
if（!
TreeEmpty（*T））//T不空
{
for（j=0;j<（*T）.n;j++）//在T中找p的序号
if（（*T）.nodes[j].data==p）//p的序号为j
break;
l=j+1;//如果c是p的第1棵子树,则插在j+1处
if（i>1）//c不是p的第1棵子树
{
for（k=j+1;k<（*T）.n;k++）//从j+1开始找p的前i-1个孩子
if（（*T）.nodes[k].parent==j）//当前结点是p的孩子
{
n++;//孩子数加1
if（n==i-1）//找到p的第i-1个孩子,其序号为k1
break;
}
l=k+1;//c插在k+1处
}//p的序号为j,c插在l处
if（l<（*T）.n）//插入点l不在最后
//依次将序号l以后的结点向后移c.n个位置
for（k=（*T）.n-1;k>=l;k--）
{
（*T）.nodes[k+c.n]=（*T）.nodes[k];//向后移c.n个位置
if（（*T）.nodes[k].parent>=l）
（*T）.nodes[k+c.n].parent+=c.n;
}
for（k=0;k{
（*T）.nodes[l+k].data=c.nodes[k].data;//依次将树c的所有结点插于此处
（*T）.nodes[l+k].parent=c.nodes[k].parent+l;
}
（*T）.nodes[l].parent=j;//树c的根结点的双亲为p
（*T）.n+=c.n;//树T的结点数加c.n个
while（f）
{//从插入点之后,将结点仍按层序排列
f=0;//交换标志置0
for（j=l;j<（*T）.n-1;j++）
if（（*T）.nodes[j].parent>（*T）.nodes[j+1].parent）
{
//如果结点j的双亲排在结点j+1的双亲之后（树没有按层序排
//列）,交换两结点
t=（*T）.nodes[j];
（*T）.nodes[j]=（*T）.nodes[j+1];
（*T）.nodes[j+1]=t;
f=1;//交换标志置1
for（k=j;k<（*T）.n;k++）//改变双亲序号
if（（*T）.nodes[k].parent==j）
（*T）.nodes[k].parent++;//双亲序号改为j+1
elseif（（*T）.nodes[k].parent==j+1）
（*T）.nodes[k].parent--;//双亲序号改为j
}
}
return1;
}
else//树T不存在
return0;
}
intdeleted[MAX_TREE_SIZE+1];//删除标志数组（全局量）
//删除T中结点p的第i棵子树
voidDeleteChild（PTree*T,TElemTypep,inti）
{
intj,k,n=0;
LinkQueueq;
QElemTypepq,qq;
for（j=0;j<=（*T）.n;j++）
deleted[j]=0;//置初值为0（不删除标记）
pq.name='a';//此成员不用
InitQueue（&q）;//初始化队列
for（j=0;j<（*T）.n;j++）
if（（*T）.nodes[j].data==p）
break;//j为结点p的序号
for（k=j+1;k<（*T）.n;k++）
{
if（（*T）.nodes[k].parent==j）
n++;
if（n==i）
break;//k为p的第i棵子树结点的序号
}
if（k<（*T）.n）//p的第i棵子树结点存在
{
n=0;
pq.num=k;
deleted[k]=1;//置删除标记
n++;
EnQueue（&q,pq）;
while（!
QueueEmpty（q））
{
DeQueue（&q,&qq）;
for（j=qq.num+1;j<（*T）.n;j++）
if（（*T）.nodes[j].parent==qq.num）
{
pq.num=j;
deleted[j]=1;//置删除标记
n++;
EnQueue（&q,pq）;
}
}
for（j=0;j<（*T）.n;j++）
if（deleted[j]==1）
{
for（k=j+1;k<=（*T）.n;k++）
{
deleted[k-1]=deleted[k];
（*T）.nodes[k-1]=（*T）.nodes[k];
if（（*T）.nodes[k].parent>j）
（*T）.nodes[k-1].parent--;
}
j--;
}
（*T）.n-=n;//n为待删除结点数
}
}
//层序遍历树T,对每个结点调用函数Visit一次且仅一次
voidTraverseTree（PTreeT,void（*Visit）（TElemType））
{
inti;
for（i=0;iVisit（T.nodes[i].data）;
printf（"\n"）;
}
voidvi（TElemTypec）
{
printf（"%c",c）;
}
intmain（）
{
inti;
PTreeT,p;
TElemTypee,e1;
InitTree（&T）;
printf（"构造空树后,树空否?
%d（1:
是0:
否）树根为%c树的深度为%d\n",
TreeEmpty（T）,Root（T）,TreeDepth（T））;
CreateTree（&T）;
printf（"构造树T后,树空否?
%d（1:
是0:
否）树根为%c树的深度为%d\n",
TreeEmpty（T）,Root（T）,TreeDepth（T））;
printf（"层序遍历树T:
\n"）;
TraverseTree（T,vi）;
printf（"请输入待修改的结点的值新值:
"）;
scanf（"%c%*c%c%*c",&e,&e1）;
Assign（&T,e,e1）;
printf（"层序遍历修改后的树T:
\n"）;
TraverseTree（T,vi）;
printf（"%c的双亲是%c,长子是%c,下一个兄弟是%c\n",e1,
Parent（T,e1）,LeftChild（T,e1）,RightSibling（T,e1））;
printf（"建立树p:
\n"）;
InitTree（&p）;
CreateTree（&p）;
printf（"层序遍历树p:
\n"）;
TraverseTree（p,vi）;
printf（"将树p插到树T中，请输入T中p的双亲结点子树序号:
"）;
scanf（"%c%d%*c",&e,&i）;
InsertChild（&T,e,i,p）;
Print（T）;
printf（"删除树T中结点e的第i棵子树，请输入ei:
"）;
scanf（"%c%d",&e,&i）;
DeleteChild（&T,e,i）;
Print（T）;
system（"pause"）;
return0;
}
/*
输出效果：
构造空树后,树空否?
1（1:
是0:
否）树根为树的深度为0
请输入根结点（字符型,空格为空）:
a
请按长幼顺序输入结点a的所有孩子:
bc
请按长幼顺序输入结点b的所有孩子:
d
请按长幼顺序输入结点c的所有孩子:
e
请按长幼顺序输入结点d的所有孩子:
请按长幼顺序输入结点e的所有孩子:
构造树T后,树空否?
0（1:
是0:
否）树根为a树的深度为3
层序遍历树T:
abcde
请输入待修改的结点的值新值:
ef
层序遍历修改后的树T:
abcdf
f的双亲是c,长子是,下一个兄弟是
建立树p:
请输入根结点（字符型,空格为空）:
A
请按长幼顺序输入结点A的所有孩子:
B
请按长幼顺序输入结点B的所有孩子:
层序遍历树p:
AB
将树p插到树T中，请输入T中p的双亲结点子树序号:
b2
结点个数=7
结点双亲
a
ba
ca
db
Ab
fc
BA
删除树T中结点e的第i棵子树，请输入ei:
a1
结点个数=3
结点双亲
a
ca
fc
请按任意键继续...
*/
升级会员 