C语言数据结构 创建和遍历二叉树 源码.docx
《C语言数据结构 创建和遍历二叉树 源码.docx》由会员分享，可在线阅读，更多相关《C语言数据结构 创建和遍历二叉树 源码.docx（9页珍藏版）》请在冰点文库上搜索。
C语言数据结构创建和遍历二叉树源码
Create&TraverseBiTree
程序已就绪，可直接编译运行
#include
#include
#defineOK1
#defineTRUE1
#defineERROR0
#defineFALSE0
#defineOVERFLOW-1
#defineSTACK_INIT_SIZE200;
#defineSTACKINCERMENT20;
typedefintstatus;
typedefcharTElemType;
//-----二叉树的二叉链表存储表示-----
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;//*BiTree表示指向该结构体的指针
//-----单链队列-----队列的链式存储结构
typedefBiTreeQElemType;
typedefstructQNode
{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
//------队列基本操作------
statusInitQueue（LinkQueue&Q）
{//构造一个空队列Q
Q.front=（QueuePtr）malloc（sizeof（QNode））;
Q.rear=Q.front;
if（!
Q.front）exit（OVERFLOW）;
Q.front->next=NULL;
returnOK;
}//InitQueue
statusEnQueue（LinkQueue&Q,QElemTypee）
{//插入元素e为Q的新队尾元素
QueuePtrp;
p=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）exit（OVERFLOW）;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
returnOK;
}//EnQueue
statusDeQueue（LinkQueue&Q,QElemType&e）
{//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK
//否则返回ERROR
QueuePtrp;
if（Q.front==Q.rear）returnERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）Q.rear=Q.front;
free（p）;
returnOK;
}//DeQueue
statusQueueEmpty（LinkQueue&Q）
{
intlen;
len=Q.rear-Q.front;
if（len==0）returnOK;
returnERROR;
}//QueueEmpty
statusDestroyQueue（LinkQueue&Q）
{//销毁队列Q
while（Q.front）
{
Q.rear=Q.front->next;
free（Q.front）;
Q.front=Q.rear;
}
returnOK;
}//DestroyQueue
//-----二叉树的基本操作函数-----
statusCreateBiTree（BiTree&T）
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树
//构造二叉链表表示的二叉树T
{
charch;
scanf（"%c",&ch）;
if（ch==''）T=NULL;
else
{
if（!
（T=（BiTNode*）malloc（sizeof（BiTNode））））exit（OVERFLOW）;
T->data=ch;//生成根节点
CreateBiTree（T->lchild）;//构造左子树
CreateBiTree（T->rchild）;//构造右子树
}
returnOK;
}//CreateBiTree
statusvisit（TElemTypee）
{
printf（"%c",e）;
returnOK;
}//visit
statusPreOrderTraverse（BiTreeT,status（*visit）（TElemTypee））
//先序遍历二叉树T的递归算法
{
if（T）
{
if（visit（T->data））
if（PreOrderTraverse（T->lchild,visit））
if（PreOrderTraverse（T->rchild,visit））
returnOK;
//returnERROR;
}
else
{
printf（"_"）;
returnOK;
}
}//PreOrderTraverse
statusMidOrderTraverse（BiTreeT,status（*visit）（TElemTypee））
//中序遍历二叉树T的递归算法
{
if（T）
{
if（MidOrderTraverse（T->lchild,visit））
if（visit（T->data））
if（MidOrderTraverse（T->rchild,visit））
returnOK;
//returnERROR;
}
else
{
printf（"_"）;
returnOK;
}
}//MidOrderTraverse
statusLastOrderTraverse（BiTreeT,status（*visit）（TElemTypee））
//后序遍历二叉树T的递归算法
{
if（T）
{
if（LastOrderTraverse（T->lchild,visit））
if（LastOrderTraverse（T->rchild,visit））
if（visit（T->data））
returnOK;
//returnERROR;
}
else
{
printf（"_"）;
returnOK;
}
}//LastOrderTraverse
statusLeafCount（BiTreeT,int&sum）
{
inta;
if（T）
{
if（T->lchild）LeafCount（T->lchild,sum）;
elsea=1;
if（T->rchild）LeafCount（T->rchild,sum）;
elseif（a==1）sum++;
returnOK;
//returnERROR;
}
}
statusLevelOrderTraverse（BiTreeT,status（*visit）（TElemTypee））
{
LinkQueueQ;
BiTreep;
if（T）
{
InitQueue（Q）;
EnQueue（Q,T）;
while（!
QueueEmpty（Q））
{
DeQueue（Q,p）;
printf（"%c",p->data）;
if（p->lchild）EnQueue（Q,p->lchild）;
if（p->rchild）EnQueue（Q,p->rchild）;
}
DestroyQueue（Q）;
}
returnOK;
}
//-----主体程序部分-----
intmain（）
{
intsum=0;
BiTreeT;
CreateBiTree（T）;
printf（"先序：
\n"）;
PreOrderTraverse（T,visit）;
printf（"\n"）;
printf（"中序：
\n"）;
MidOrderTraverse（T,visit）;
printf（"\n"）;
printf（"后序：
\n"）;
LastOrderTraverse（T,visit）;
printf（"\n"）;
printf（"层序：
\n"）;
LevelOrderTraverse（T,visit）;
printf（"\n"）;
LeafCount（T,sum）;
printf（"叶子数:
%d",sum）;
return0;
}
升级会员 