数据结构二叉树的遍历北华大学吕磊.docx
《数据结构二叉树的遍历北华大学吕磊.docx》由会员分享，可在线阅读，更多相关《数据结构二叉树的遍历北华大学吕磊.docx（6页珍藏版）》请在冰点文库上搜索。
数据结构二叉树的遍历北华大学吕磊
数据结构-二叉树的遍历（北华大学吕磊）
#include
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW-1
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineMAXQSIZE10
typedefstructBiTNode
{
chardata;
structBiTNode*lChild,*rChild;
}BiTNode,*BiTree;
typedefstructSqStack
{
BiTNode*base;
BiTNode*top;
intstacksize;
}SqStack;//栈类型
voidInitStack（SqStack*S）//创建栈
{
S->base=（BiTNode*）malloc（STACK_INIT_SIZE*sizeof（BiTNode））;
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
intStackEmpty（SqStack*S）//判断栈是否非空
{
if（S->top==S->base）returnOK;
elsereturnERROR;
}
voidPush（SqStack*S,BiTNodee）//进栈
{
if（S->top-S->base>=S->stacksize）
{
S->base=（BiTNode*）realloc（S->base,
（S->stacksize+STACKINCREMENT）*sizeof（BiTNode））;
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*（S->top）=e;
S->top++;
}
BiTNodePop（SqStack*S）//出栈
{
S->top--;
return*S->top;
}
typedefBiTreeQElemType;//设栈元素为二叉树的指针类型
typedefstruct
{
QElemType*base;
intfront;//头指针,若队列不空,指向队列头元素
intrear;//尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;
intInitQueue（SqQueue*Q）//创建队列
{
（*Q）.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
if（!
（*Q）.base）exit（OVERFLOW）;
（*Q）.front=（*Q）.rear=0;
returnOK;
}
intQueueEmpty（SqQueueQ）//判断队列是否为空
{
if（Q.front==Q.rear）returnOK;
elsereturnERROR;
}
intEnQueue（SqQueue*Q,QElemTypee）//插入元素e为Q的新的队尾元素
{
if（（（*Q）.rear+1）%MAXQSIZE==（*Q）.front）returnERROR;
（*Q）.base[（*Q）.rear]=e;
（*Q）.rear=（（*Q）.rear+1）%MAXQSIZE;
returnOK;
}
intDeQueue（SqQueue*Q,QElemType*e）//删除Q的队头元素,用e返回其值
{
if（（*Q）.front==（*Q）.rear）returnERROR;
*e=（*Q）.base[（*Q）.front];
（*Q）.front=（（*Q）.front+1）%MAXQSIZE;
returnOK;
}
intCreateBiTree（BiTree&T）//按先序次序输入二叉中树结点的值，#表示空树构造
{
charch;
scanf（"%c",&ch）;
if（ch=='#'）T=NULL;
else
{
if（!
（T=（BiTree）malloc（sizeof（BiTNode））））exit（OVERFLOW）;
T->data=ch;
CreateBiTree（T->lChild）;
CreateBiTree（T->rChild）;
}
returnOK;
}
voidPreOrderTraverse（BiTreeT）//先序遍历二叉树的递归算法
{
if（T）
{
printf（"%c",T->data）;
PreOrderTraverse（T->lChild）;
PreOrderTraverse（T->rChild）;
}
}
voidInOrderTraverse（BiTreeT）//中序遍历二叉树的递归算法
{
if（T）
{
InOrderTraverse（T->lChild）;
printf（"%c",T->data）;
InOrderTraverse（T->rChild）;
}
}
voidPostOrderTraverse（BiTreeT）//后序遍历二叉树的递归算法
{
if（T）
{
PostOrderTraverse（T->lChild）;
PostOrderTraverse（T->rChild）;
printf（"%c",T->data）;
}
}
voidinorder（BiTreeT）//中序非递归遍历二叉树
{SqStackS;
InitStack（&S）;
BiTreep=T;
while（p||!
StackEmpty（&S））
{
if（p）
{
Push（&S,*p）;
p=p->lChild;
}
else
{
p=（BiTNode*）malloc（sizeof（BiTNode））;
*p=Pop（&S）;
printf（"%c",p->data）;
p=p->rChild;
}
}
}
intmain（）//主函数分别实现建立并输出先、中、后序遍历二叉树
{
BiTreeT;
printf（"按先序输入二叉树中结点的值，#表示空结点:
\n"）;
CreateBiTree（T）;
printf（"先序递归遍历二叉树:
"）;
PreOrderTraverse（T）;
printf（"\n中序递归遍历二叉树:
"）;
InOrderTraverse（T）;
printf（"\n后序递归遍历二叉树:
"）;
PostOrderTraverse（T）;
printf（"\n中序非递归遍历二叉树：
\n"）;
inorder（T）;
printf（"\n"）;
system（"pause"）;
return0;
}
升级会员 