c语言版本二叉树基本操作示例(先序递归非递归)
这篇文章主要介绍了实现二叉树的创建（先序）、递归及非递归的先、中、后序遍历
复制代码代码如下:
请按先序遍历输入二叉树元素（每个结点一个字符，空结点为''=''）:
ABD==E==CF==G==
先序递归遍历：
ABDECFG
中序递归遍历：
DBEAFCG
后序递归遍历：
DEBFGCA
层序递归遍历：
ABCDEFG
先序非递归遍历：
ABDECFG
中序非递归遍历：
DBEAFCG
后序非递归遍历：
DEBFGCA
深度：
请按任意键继续...
复制代码代码如下:
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineOVERFLOW-1
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefintStatus;
typedefcharElemType;
typedefstructBTNode
{
ElemTypedata;
structBTNodeleftChild;
structBTNoderightChild;
}BTNode,BinTree;
typedefBinTreeSElemType;
typedefstruct{//栈结构定义
SElemTypebase;
SElemTypetop;
intstacksize;
}SqStack;
BinTreeCreateBinTree(BinTreeT);
StatusVisit(ElemTypee);
StatusDepth(BinTreeT);
StatusPreOrderRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee));
StatusInOrderRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee));
StatusPostOrderRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee));
StatusLevelOrderRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee));
//定义栈的相关操作
StatusInitStack(SqStackS);
StatusDestroyStack(SqStackS);
StatusClearStack(SqStackS);
StatusStackEmpty(SqStackS);
intStackLength(SqStackS);
StatusGetTop(SqStackS,SElemTypee);
StatusPush(SqStackS,SElemTypee);
StatusPop(SqStackS,SElemTypee);
StatusStackTraverse(constSqStackS);
StatusPreOrderNoneRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee));
StatusInOrderNoneRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee));
StatusPostOrderNoneRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee));
intmain()
{
intdepth;
BinTreeTree=NULL;
Status(visit)(ElemTypee)=Visit;
printf_s("请按先序遍历输入二叉树元素（每个结点一个字符，空结点为''=''）:\n");
Tree=CreateBinTree(Tree);
printf_s("\n先序递归遍历：\n");
PreOrderRecursionTraverse(Tree,visit);
printf_s("\n中序递归遍历：\n");
InOrderRecursionTraverse(Tree,visit);
printf_s("\n后序递归遍历：\n");
PostOrderRecursionTraverse(Tree,visit);
printf_s("\n层序递归遍历：\n");
LevelOrderRecursionTraverse(Tree,visit);
printf_s("\n先序非递归遍历：\n");
PreOrderNoneRecursionTraverse(Tree,visit);
printf_s("\n中序非递归遍历：\n");
InOrderNoneRecursionTraverse(Tree,visit);
printf_s("\n后序非递归遍历：\n");
PostOrderNoneRecursionTraverse(Tree,visit);
printf_s("\n深度：\n");
depth=Depth(Tree);
printf_s("%d\n",depth);
system("pause");
return0;
}
//创建二叉树
BinTreeCreateBinTree(BinTreeT)
{
charch;
scanf_s("%c",&ch);
if(ch==''='')
{
T=NULL;
}
else
{
if(!(T=(BTNode)malloc(sizeof(BTNode))))
{
exit(OVERFLOW);
}
T->data=ch;//生成根结点
T->leftChild=CreateBinTree(T->leftChild);
T->rightChild=CreateBinTree(T->rightChild);
}
returnT;
}
//访问二叉树
StatusVisit(ElemTypee)
{
if(e==''\0'')
{
returnERROR;
}
else
{
printf_s("%c",e);
}
returnOK;
}
//先序遍历递归算法
StatusPreOrderRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee))
{
if(T)
{
if(!Visit(T->data))
{
returnERROR;
}
PreOrderRecursionTraverse(T->leftChild,Visit);
PreOrderRecursionTraverse(T->rightChild,Visit);
}
returnOK;
}
//中序遍历递归算法
StatusInOrderRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee))
{
if(T)
{
InOrderRecursionTraverse(T->leftChild,Visit);
if(!Visit(T->data))
{
returnERROR;
}
InOrderRecursionTraverse(T->rightChild,Visit);
}
returnOK;
}
//后序遍历递归算法
StatusPostOrderRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee))
{
if(T)
{
PostOrderRecursionTraverse(T->leftChild,Visit);
PostOrderRecursionTraverse(T->rightChild,Visit);
if(!Visit(T->data))
{
returnERROR;
}
}
returnOK;
}
//层序遍历递归算法
StatusLevelOrderRecursionTraverse(BinTreeT,Status(Visitwww.visa158.com)(ElemTypee))
{
if(T)
{
BTNodeQ[100];//假设不溢出
intfront=-1,rear=-1;
if(T)
{
Q[++rear]=T;
printf_s("%c",T->data);
while(front!=rear)
{
BTNodep;
if(!(p=(BTNode)malloc(sizeof(BTNode))))
{
exit(OVERFLOW);
}
p=Q[++front];
if(p->leftChild)
{
Q[++rear]=p->leftChild;
printf("%c",p->leftChild->data);
}
if(p->rightChild)
{
Q[++rear]=p->rightChild;
printf("%c",p->rightChild->data);
}
}
}
}
returnOK;
}
StatusDepth(BinTreeT)
{
inta,b;
if(!T)
{
returnERROR;
}
else
{
a=Depth(T->leftChild)+1;
b=Depth(T->rightChild)+1;
returnawww.hunanwang.net>b?a:b;
}
}
//先序遍历非递归算法
StatusPreOrderNoneRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee))
{
SqStackS;
SElemTypep;
InitStack(&S);
Push(&S,T);
while(!StackEmpty(S))
{
Pop(&S,&p);
if(!Visit(p->data))
{
returnERROR;
}
if(p->leftChild)
{
Push(&S,p->rightChild);
}
if(p->rightChild)
{
Push(&S,p->leftChild);
}
}
DestroyStack(&S);
returnOK;
}
//中序遍历非递归算法
StatusInOrderNoneRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee))
{
SqStackS;
SElemTypep;
InitStack(&S);
Push(&S,T);
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p)
{
Push(&S,p->leftChild);
}
Pop(&S,&p);
if(!StackEmpty(S))
{
Pop(&S,&p);
if(!Visit(p->data))
{
returnERROR;
}
Push(&S,p->rightChild);
}
}
DestroyStack(&S);
returnOK;
}
//后序便利非递归算法
StatusPostOrderNoneRecursionTraverse(BinTreeT,Status(Visit)(ElemTypee))
{
SqStackS;
SElemTypep,q;
InitStack(&S);
Push(&S,T);
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p&&(p->leftChild||p->rightChild))
{
Push(&S,p->rightChild);
Push(&S,p->leftChild);
}
if(!StackEmpty(S)){
Pop(&S,&p);
if(p)
{
if(!Visit(p->data))
{
returnERROR;
}
}
else
{
Pop(&S,&p);
if(!Visit(p->data))
{
returnERROR;
}
}
while(GetTop(S,&q)&&q&&p==q->rightChild)
{
Pop(&S,&p);
if(!Visit(p->data))
{
returnERROR;
}
GetTop(S,&q);
}
}
}
DestroyStack(&S);
returnOK;
}
//-----------栈的相关操作--------------//
StatusInitStack(SqStackS){
S->base=(SElemType)malloc(STACK_INIT_SIZEsizeof(SElemType));
if(!S->base)
{
exit(0);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusDestroyStack(SqStackS){
if(!S)
{
exit(0);
}
free(S->base);
returnOK;
}
StatusClearStack(SqStackS){
if(!S)
{
returnFALSE;
}
S->top=S->base;
returnOK;
}
StatusStackEmpty(SqStackS){
if(S.top==S.base)
{
returnTRUE;
}
else
{
returnFALSE;
}
}
intStackLength(SqStackS){
returnS.stacksize;
}
StatusGetTop(SqStackS,SElemTypee){
if(S.top==S.base)
{
returnFALSE;
}
else
{
e=(S.top-1);
returnOK;
}
}
StatusPush(SqStackS,SElemTypee){
if(S->top-S->base>=S->stacksize)
{
S->base=(SElemType)realloc(S->base,(S->stacksize+STACKINCREMENT)sizeof(SElemType));
if(!S->base)
{
exit(0);
}
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
S->top++=e;
returnOK;
}
StatusPop(SqStackS,SElemTypee){
if(S->top==S->base)
{
returnERROR;
}
e=(--S->top);
returnOK;
}
|
|
