数据结构C语言版二叉树的三叉链表存储表示.docx
《数据结构C语言版二叉树的三叉链表存储表示.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版二叉树的三叉链表存储表示.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构C语言版二叉树的三叉链表存储表示
数据结构C语言版二叉树的三叉链表存储表示.txt大悲无泪，大悟无言，大笑无声。
我们手里的金钱是保持自由的一种工具。
女人在约会前，一定先去美容院；男人约会前，一定先去银行。
/*
数据结构C语言版二叉树的三叉链表存储表示
编译环境：
Dev-C++4.9.9.2
日期：
2011年2月13日
*/
#include
#include
typedefcharTElemType;
//二叉树的三叉链表存储表示
typedefstructBiTPNode
{
TElemTypedata;
structBiTPNode*parent,*lchild,*rchild;//双亲、左右孩子指针
}BiTPNode,*BiPTree;
typedefBiPTreeQElemType;//设队列元素为二叉树的指针类型
typedefstructQNode
{
QElemTypedata;//数据域
structQNode*next;//指针域
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront,//队头指针，指针域指向队头元素
rear;//队尾指针，指向队尾元素
}LinkQueue;
TElemTypeNil='';//字符型以空格符为空
//构造空二叉树T
intInitBiTree（BiPTree*T）
{
*T=NULL;
return1;
}
//销毁二叉树T
voidDestroyBiTree（BiPTree*T）
{
if（*T）//非空树
{
if（（*T）->lchild）//有左孩子
DestroyBiTree（&（*T）->lchild）;//销毁左孩子子树
if（（*T）->rchild）//有右孩子
DestroyBiTree（&（*T）->rchild）;//销毁右孩子子树
free（*T）;//释放根结点
*T=NULL;//空指针赋0
}
}
#defineClearBiTreeDestroyBiTree
//按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中定义），
//构造仅缺双亲指针的三叉链表表示的二叉树T。
变量Nil表示空（子）树
voidCreate（BiPTree*T）//CreateBiTree（）调用
{
TElemTypech;
scanf（"%c",&ch）;
if（ch==Nil）//空
*T=NULL;
else
{
*T=（BiPTree）malloc（sizeof（BiTPNode））;
if（!
*T）
exit（0）;
（*T）->data=ch;//生成根结点
Create（&（*T）->lchild）;//构造左子树
Create（&（*T）->rchild）;//构造右子树
}
}
//构造一个空队列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
intCreateBiTree（BiPTree*T）
{
LinkQueueq;
QElemTypea;
Create（T）;//构造二叉树（缺双亲指针）
if（*T）//非空树
{
（*T）->parent=NULL;//根结点的双亲为＂空＂
InitQueue（&q）;//初始化队列
EnQueue（&q,*T）;//根指针入队
while（!
QueueEmpty（q））//队不空
{
DeQueue（&q,&a）;//出队,队列元素赋给a
if（a->lchild）//有左孩子
{
a->lchild->parent=a;//给左孩子的双亲指针赋值
EnQueue（&q,a->lchild）;//左孩子入队
}
if（a->rchild）//有右孩子
{
a->rchild->parent=a;//给右孩子的双亲指针赋值
EnQueue（&q,a->rchild）;//右孩子入队
}
}
}
return1;
}
//若T为空二叉树,则返回1,否则0
intBiTreeEmpty（BiPTreeT）
{
if（T）
return0;
else
return1;
}
//返回T的深度
intBiTreeDepth（BiPTreeT）
{
inti,j;
if（!
T）
return0;
if（T->lchild）
i=BiTreeDepth（T->lchild）;
else
i=0;
if（T->rchild）
j=BiTreeDepth（T->rchild）;
else
j=0;
returni>j?
i+1:
j+1;
}
//返回T的根
TElemTypeRoot（BiPTreeT）
{
if（T）
returnT->data;
else
returnNil;
}
//返回p所指结点的值
TElemTypeValue（BiPTreep）
{
returnp->data;
}
//给p所指结点赋值为value
voidAssign（BiPTreep,TElemTypevalue）
{
p->data=value;
}
//返回二叉树T中指向元素值为e的结点的指针
BiPTreePoint（BiPTreeT,TElemTypee）
{
LinkQueueq;
QElemTypea;
if（T）//非空树
{
InitQueue（&q）;//初始化队列
EnQueue（&q,T）;//根结点入队
while（!
QueueEmpty（q））//队不空
{
DeQueue（&q,&a）;//出队,队列元素赋给a
if（a->data==e）
returna;
if（a->lchild）//有左孩子
EnQueue（&q,a->lchild）;//入队左孩子
if（a->rchild）//有右孩子
EnQueue（&q,a->rchild）;//入队右孩子
}
}
returnNULL;
}
//若e是T的非根结点,则返回它的双亲,否则返回＂空＂
TElemTypeParent（BiPTreeT,TElemTypee）
{
BiPTreea;
if（T）//非空树
{
a=Point（T,e）;//a是结点e的指针
if（a&&a!
=T）//T中存在结点e且e是非根结点
returna->parent->data;//返回e的双亲的值
}
returnNil;//其余情况返回空
}
//返回e的左孩子。
若e无左孩子,则返回＂空＂
TElemTypeLeftChild（BiPTreeT,TElemTypee）
{
BiPTreea;
if（T）//非空树
{
a=Point（T,e）;//a是结点e的指针
if（a&&a->lchild）//T中存在结点e且e存在左孩子
returna->lchild->data;//返回e的左孩子的值
}
returnNil;//其余情况返回空
}
//返回e的右孩子。
若e无右孩子,则返回＂空＂
TElemTypeRightChild（BiPTreeT,TElemTypee）
{
BiPTreea;
if（T）//非空树
{
a=Point（T,e）;//a是结点e的指针
if（a&&a->rchild）//T中存在结点e且e存在右孩子
returna->rchild->data;//返回e的右孩子的值
}
returnNil;//其余情况返回空
}
//返回e的左兄弟。
若e是T的左孩子或无左兄弟,则返回＂空＂
TElemTypeLeftSibling（BiPTreeT,TElemTypee）
{
BiPTreea;
if（T）//非空树
{
a=Point（T,e）;//a是结点e的指针
//T中存在结点e且e存在左兄弟
if（a&&a!
=T&&a->parent->lchild&&a->parent->lchild!
=a）
returna->parent->lchild->data;//返回e的左兄弟的值
}
returnNil;//其余情况返回空
}
//返回e的右兄弟。
若e是T的右孩子或无右兄弟,则返回＂空＂
TElemTypeRightSibling（BiPTreeT,TElemTypee）
{
BiPTreea;
if（T）//非空树
{
a=Point（T,e）;//a是结点e的指针
//T中存在结点e且e存在右兄弟
if（a&&a!
=T&&a->parent->rchild&&a->parent->rchild!
=a）
returna->parent->rchild->data;//返回e的右兄弟的值
}
returnNil;//其余情况返回空
}
//根据LR为0或1,插入c为T中p所指结点的左或右子树。
p所指结点
//的原有左或右子树则成为c的右子树。
intInsertChild（BiPTreep,intLR,BiPTreec）
{
if（p）//p不空
{
if（LR==0）
{
c->rchild=p->lchild;
if（c->rchild）//c有右孩子（p原有左孩子）
c->rchild->parent=c;
p->lchild=c;
c->parent=p;
}
else//LR==1
{
c->rchild=p->rchild;
if（c->rchild）//c有右孩子（p原有右孩子）
c->rchild->parent=c;
p->rchild=c;
c->parent=p;
}
return1;
}
return0;//p空
}
//根据LR为0或1,删除T中p所指结点的左或右子树
intDeleteChild（BiPTreep,intLR）
{
if（p）//p不空
{
if（LR==0）//删除左子树
ClearBiTree（&p->lchild）;
else//删除右子树
ClearBiTree（&p->rchild）;
return1;
}
return0;//p空
}
//先序递归遍历二叉树T
voidPreOrderTraverse（BiPTreeT,int（*Visit）（BiPTree））
{
if（T）
{
Visit（T）;//先访问根结点
PreOrderTraverse（T->lchild,Visit）;//再先序遍历左子树
PreOrderTraverse（T->rchild,Visit）;//最后先序遍历右子树
}
}
//中序递归遍历二叉树T
voidInOrderTraverse（BiPTreeT,int（*Visit）（BiPTree））
{
if（T）
{
InOrderTraverse（T->lchild,Visit）;//中序遍历左子树
Visit（T）;//再访问根结点
InOrderTraverse（T->rchild,Visit）;//最后中序遍历右子树
}
}
//后序递归遍历二叉树T
voidPostOrderTraverse（BiPTreeT,int（*Visit）（BiPTree））
{
if（T）
{
PostOrderTraverse（T->lchild,Visit）;//后序遍历左子树
PostOrderTraverse（T->rchild,Visit）;//后序遍历右子树
Visit（T）;//最后访问根结点
}
}
//层序遍历二叉树T（利用队列）
voidLevelOrderTraverse（BiPTreeT,int（*Visit）（BiPTree））
{
LinkQueueq;
QElemTypea;
if（T）
{
InitQueue（&q）;
EnQueue（&q,T）;
while（!
QueueEmpty（q））
{
DeQueue（&q,&a）;
Visit（a）;
if（a->lchild!
=NULL）
EnQueue（&q,a->lchild）;
if（a->rchild!
=NULL）
EnQueue（&q,a->rchild）;
}
}
}
intvisitT（BiPTreeT）
{
if（T）//T非空
printf（"%c是",T->data）;
if（T->parent）//T有双亲
{
printf（"%c",T->parent->data）;
if（T->parent->lchild==T）
printf（"的左孩子\n"）;
else
printf（"的右孩子\n"）;
}
else
printf（"根结点\n"）;
return1;
}
intmain（）
{
inti;
BiPTreeT,c,q;
TElemTypee1,e2;
InitBiTree（&T）;
printf（"构造空二叉树后,树空否？
%d（1:
是0:
否）树的深度=%d\n",
BiTreeEmpty（T）,BiTreeDepth（T））;
e1=Root（T）;
if（e1!
=Nil）
printf（"二叉树的根为:
%c\n",e1）;
else
printf（"树空，无根\n"）;
printf（"请按先序输入二叉树（如:
ab三个空格表示a为根结点,b为"
"左子树的二叉树）\n"）;
CreateBiTree（&T）;
printf（"建立二叉树后,树空否？
%d（1:
是0:
否）树的深度=%d\n",
BiTreeEmpty（T）,BiTreeDepth（T））;
e1=Root（T）;
if（e1!
=Nil）
printf（"二叉树的根为:
%c\n",e1）;
else
printf（"树空，无根\n"）;
printf（"中序递归遍历二叉树:
\n"）;
InOrderTraverse（T,visitT）;
printf（"后序递归遍历二叉树:
\n"）;
PostOrderTraverse（T,visitT）;
printf（"层序遍历二叉树:
\n"）;
LevelOrderTraverse（T,visitT）;
printf（"请输入一个结点的值:
"）;
scanf（"%*c"）;
scanf（"%c%*c",&e1）;
c=Point（T,e1）;//c为e1的指针
printf（"结点的值为%c\n",Value（c））;
printf（"欲改变此结点的值，请输入新值:
"）;
scanf（"%c%*c",&e2）;
Assign（c,e2）;
printf（"层序遍历二叉树:
\n"）;
LevelOrderTraverse（T,visitT）;
e1=Parent（T,e2）;
if（e1!
=Nil）
printf（"%c的双亲是%c\n",e2,e1）;
else
printf（"%c没有双亲\n",e2）;
e1=LeftChild（T,e2）;
if（e1!
=Nil）
printf（"%c的左孩子是%c\n",e2,e1）;
else
printf（"%c没有左孩子\n",e2）;
e1=RightChild（T,e2）;
if（e1!
=Nil）
printf（"%c的右孩子是%c\n",e2,e1）;
else
printf（"%c没有右孩子\n",e2）;
e1=LeftSibling（T,e2）;
if（e1!
=Nil）
printf（"%c的左兄弟是%c\n",e2,e1）;
else
printf（"%c没有左兄弟\n",e2）;
e1=RightSibling（T,e2）;
if（e1!
=Nil）
printf（"%c的右兄弟是%c\n",e2,e1）;
else
printf（"%c没有右兄弟\n",e2）;
InitBiTree（&c）;
printf（"构造一个右子树为空的二叉树c:
\n"）;
printf（"请先序输入二叉树（如:
ab三个空格表示a为根结点,b为左子树的二叉树）\n"）;
CreateBiTree（&c）;
printf（"先序递归遍历二叉树c:
\n"）;
PreOrderTraverse（c,visitT）;
printf（"树c插到树T中,请输入树T中树c的双亲结点c为左（0）或右
（1）子树:
"）;
scanf（"%*c%c%d",&e1,&i）;
q=Point（T,e1）;
InsertChild（q,i,c）;
printf（"先序递归遍历二叉树:
\n"）;
PreOrderTraverse（T,visitT）;
printf（"删除子树,请输入待删除子树的双亲结点左（0）或右
（1）子树:
"）;
scanf（"%*c%c%d",&e1,&i）;
q=Point（T,e1）;
DeleteChild（q,i）;
printf（"先序递归遍历二叉树:
\n"）;
PreOrderTraverse（T,visitT）;
DestroyBiTree（&T）;
system（"pause"）;
return0;
}
/*
输出效果：
构造空二叉树后,树空否？
1（1:
是0:
否）树的深度=0
树空，无根
请按先序输入二叉树（如:
ab三个空格表示a为根结点,b为左子树的二叉树）
ab
建立二叉树后,树空否？
0（1:
是0:
否）树的深度=2
二叉树的根为:
a
中序递归遍历二叉树:
b是a的左孩子
a是根结点
后序递归遍历二叉树:
b是a的左孩子
a是根结点
层序遍历二叉树:
a是根结点
b是a的左孩子
请输入一个结点的值:
a
结点的值为a
欲改变此结点的值，请输入新值:
c
层序遍历二叉树:
c是根结点
b是c的左孩子
c没有双亲
c的左孩子是b
c没有右孩子
c没有左兄弟
c没有右兄弟
构造一个右子树为空的二叉树c:
请先序输入二叉树（如:
ab三个空格表示a为根结点,b为左子树的二叉树）
AB
先序递归遍历二叉树c:
A是根结点
B是A的左孩子
树c插到树T中,请输入树T中树c的双亲结点c为左（0）或右
（1）子树:
c1
先序递归遍历二叉树:
c是根结点
b是c的左孩子
A是c的右孩子
B是A的左孩子
删除子树,请输入待删除子树的双亲结点左（0）或右
（1）子树:
A0
先序递归遍历二叉树:
c是根结点
b是c的左孩子
A是c的右孩子
请按任意键继续...
*/
升级会员 