?? 二叉樹的各種遍歷操作(非)遞歸.c
字號:
/*二叉樹的各種遍歷操作*/
//#include<alloc.h>
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
/*函數結果狀態代碼*/
#define True 1
#define False 0
#define Ok 1
#define Error 0
#define Infeasible -1
#define Overflow -2
#define Null 0
#define STACK_INIT_SIZE 100
#define Stackincrement 10
typedef int Status ;
typedef char TElemType;/* 抽象元素類型為char類型 */
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;/*左右孩子指針*/
}BiTNode;
typedef struct BiTNode *BiTree;
typedef struct BiTNode SElemType;
struct STACK
{
SElemType *base;
SElemType *top;
int stacksize;
};
typedef struct STACK SqStack;
int InitStack(SqStack *S)
/*構造一個空棧*/
{
S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)
exit(Overflow);/*存儲分配失敗*/
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return Ok;
}/*InitStack()*/
Status StackEmpty(SqStack *S)
/*判斷棧S是否為空*/
{
if(S->top==S->base) return True;
else
return False;
}/*StackEmpty()*/
int StackLength(SqStack *S)
/*求棧S中的數據個數*/
{
int i;
SElemType *p;
i=0;
p=S->top;
while(p!=S->base)
{
p--;
i++;
}/*while*/
return i;
}/*StackLength()*/
int GetTop(SqStack *S,SElemType **e)
/*若棧不空，則用e返回S的棧頂元素，并返回Ok，否則返回Error*/
{
if(S->top==S->base)
return Error;
else
{
*e=S->top-1;
return Ok;
}/*else*/
}/*GetTop()*/
int Push(SqStack *S,SElemType *e)
/*插入元素e為新的棧頂元素*/
{
if(S->top-S->base>=S->stacksize)/*棧滿，追加存儲空間*/
{
S->base=(SElemType*)realloc(S->base,(S->stacksize+Stackincrement)*sizeof(SElemType));
if(!S->base)exit(Overflow);
S->top=S->base+S->stacksize;
S->stacksize+=Stackincrement;
}/*if*/
S->top->data=e->data;
S->top->rchild=e->rchild;
S->top->lchild=e->lchild;
++S->top;
}/*Push()*/
int Pop(SqStack *S,SElemType **e)
/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回Ok；否則返回Error*/
{
if(S->top==S->base)
return Error;
else
{
(*e)->data=(S->top-1)->data;
(*e)->rchild=(S->top-1)->rchild;
(*e)->lchild=(S->top-1)->lchild;
--S->top;
}/*else*/
return Ok;
}/*Pop()*/
int CreateBiTree(BiTNode **T)
/* 按先序次次序輸入二叉樹終結點的值（一個字符），空格字符表示空樹，構造二叉鏈表表示的二叉樹T */
{
TElemType ch;
scanf("%c",&ch);
if(ch=='#')
(*T)=Null;
else
{
(*T)=(BiTNode*)malloc(sizeof(BiTNode));
if(!(*T))
exit(Overflow);
(*T)->data=ch; /* 生成根節點 */
CreateBiTree(&(*T)->lchild); /* 構造左子樹 */
CreateBiTree(&(*T)->rchild); /* 構造右子樹 */
}/*else*/
return Ok;
} /* CreateBiTree() */
int PreOrderTraverse(BiTree T,int (*Visit)(TElemType))
/*采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數 */
/*先序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數Visit */
/*最簡單的Visit函數是： */
/* int PrintElememt(TElemType e) */
/* 輸出元素e的值 */
/* { */
/* printf(e); 實用時，加上格式串 */
/* return Ok; */
/* } */
/*調用實例：PreOrderTraverse(T,PrintElement) */
{
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
return Ok;
return Error;
}
else
return Ok;
}/*PreOrderTraverse()*/
int InOrderTraverse(BiTree T,int (*Visit)(TElemType))
/*中序遍歷二叉樹T的遞歸算法*/
{
if(T)
{
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return Ok;
return Error;
}
else
return Ok;
}/*InOrderTraverse()*/
int PostOrderTraverse(BiTree T,int (*Visit)(TElemType))
/*后序遍歷二叉樹T的遞歸算法*/
{
if(T)
{
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data))
return Ok;
return Error;
}
else
return Ok;
}/*PostOrderTraverse()*/
int InOrderTraverse1(BiTree T,int(*Visit)(TElemType))
/*采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。*/
/*中序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit*/
{
SqStack *S;
SElemType *p;
S=(SqStack*)malloc(sizeof(SqStack));
p=(SElemType*)malloc(sizeof(SElemType));
InitStack(S);
Push(S,T); /*根指針進棧*/
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p->data>='a'&&p->data<='z')
{Push(S,p->lchild);} /*向左走到盡頭*/
Pop(S,&p); /*空指針退棧*/
if(!StackEmpty(S)) /*訪問結點，向右一步*/
{
Pop(S,&p);
if(!Visit(p->data))
return Error;
Push(S,p->rchild);
}/*if*/
}/*while*/
return Ok;
}/*InOrderTraverse1()*/
int PreOrderTraverse1(BiTree T,int(*Visit)(TElemType))
/*采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。*/
/*先序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit*/
{
SqStack *S;
SElemType *p;
S=(SqStack*)malloc(sizeof(SqStack));
p=(SElemType*)malloc(sizeof(SElemType));
InitStack(S);
Push(S,T);/*根指針進棧*/
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p->data>='a'&&p->data<='z') /*先遍歷左子樹*/
{
if(!Visit(p->data))
return Error;
p=p->lchild;
Push(S,p);
}/*while*/
Pop(S,&p); /*空指針退棧*/
if(!StackEmpty(S)) /*通過下一次循環中的內嵌while實現右子樹遍歷*/
{
Pop(S,&p);
p=p->rchild;
Push(S,p);
}/*if*/
}/*while*/
return Ok;
}/*PreOrderTraverse1()*/
int PostOrderTraverse1(BiTree T,int(*Visit)(TElemType))
/*采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。*/
/*后序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit*/
{
SqStack *S;
SElemType *p,*t;
int tag[100];
S=(SqStack*)malloc(sizeof(SqStack));
p=(SElemType*)malloc(sizeof(SElemType));
t=(SElemType*)malloc(sizeof(SElemType));
InitStack(S);
p=T;/*Push(S,T);*/
do
{
while(p->data>='a'&&p->data<='z')
{
Push(S,p);
tag[StackLength(S)]=0;
p=p->lchild;
} /*向左走到盡頭*/
if(!StackEmpty(S)) /*訪問結點，向右一步*/
{
if(GetTop(S,&t)&&tag[StackLength(S)]==1)
{
Pop(S,&t);
if(!Visit(t->data))
return Error;
}/*if*/
else
{
GetTop(S,&p);
if(!StackEmpty(S))
{
p=p->rchild; /*掃描右子樹*/
tag[StackLength(S)]=1;
}
}
}/*while*/
}while(p->data>='a'&&p->data<='z'||!StackEmpty(S));
return Ok;
}/*PostOrderTraverse1()*/
int PrintTree(TElemType e)
/*輸出二叉樹中的每一個結點*/
{
printf("%c ",e);
return Ok;
}
main()
{
BiTree T;
CreateBiTree(&T);
printf("preOrder:");
PreOrderTraverse(T,PrintTree);
printf("\n");
printf("InOrder:");
InOrderTraverse(T,PrintTree);
printf("\n");
printf("postOrder:");
PostOrderTraverse(T,PrintTree);
printf("\n");
printf("not recursion InOrder:");
InOrderTraverse1(T,PrintTree);
printf("\n");
printf("not recursion PreOrder:");
PreOrderTraverse1(T,PrintTree);
printf("\n");
printf("not recursion PostOrder:");
PostOrderTraverse1(T,PrintTree);
printf("\n");
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -