二叉树中序遍历的非递归算法

以你之姓@ 2022-08-21 13:56 111阅读 0赞

用栈实现二叉树中序遍历的非递归算法![微笑][smile.gif]

\#include<stdio.h>  
\#include<malloc.h>  
\#define OK 1  
\#define ERROR 0  
\#define STACK\_INIT\_SIZE 100

/\*预定义栈的长度为100

【身无分文的你你找你老妈要了100块，实际上你可能只花了50块】

【我们预先找电脑要了100个储存单元，实际上栈可能没有那么长】\*/  
\#define STACKINCREMENT 10

typedef int Status;  
typedef char ElemType;

typedef struct BiTNode  
\{  
ElemType data;  
struct BiTNode \*lchild,\*rchild;  
\}BiTNode,\*BiTree; //定义二叉树

typedef BiTree SElemType; //定义SElemType是二叉树类型

struct SqStack  
\{  
SElemType \*base;  
SElemType \*top;  
int stacksize;  
\}; //定义栈

Status InitStack(SqStack &S) //构建栈  
\{  
S.base=(SElemType\*)malloc(STACK\_INIT\_SIZE\*sizeof(SElemType));  
if(!S.base) //没有分配到内存返回ERROR  
return ERROR;  
S.top=S.base;  
S.stacksize=STACK\_INIT\_SIZE;  
return OK;  
\}

Status 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)  
return ERROR;  
S.top=S.base+S.stacksize;  
S.stacksize+=STACKINCREMENT;  
\}  
\*S.top++=e; //先自加后赋值  
return OK;  
\}

Status Pop(SqStack &S,SElemType &e) //删除栈顶元素，用e返回其值  
\{  
if(S.top==S.base)  
return ERROR;  
e=\*--S.top; //先取内容后自减再赋值  
return OK;  
\}

Status GetTop(SqStack S,SElemType &e) //取栈顶元素  
\{  
if(S.top==S.base)  
return ERROR;  
e=\*(S.top-1);  
return OK;  
\}

BiTree CreateBiTree(BiTree &T)

//将要构建的二叉树按照先序序列输入，当某节点左孩子（或者右孩子，或两者）为空时输入\#代替  
\{  
char ch;  
scanf("%c",&ch);  
if(ch=='\#')  
T=NULL;  
else  
\{  
if(!(T=(BiTNode\*)malloc(sizeof(BiTNode))))  
return ERROR;  
T->data=ch;  
CreateBiTree(T->lchild);  
CreateBiTree(T->rchild);  
\}  
return T;  
\}

Status Visit(ElemType e)  
\{  
if(e!='\#')  
\{  
printf("%c",e);  
return OK;  
\}  
else  
return ERROR;  
\}

Status InOrderTraverse(BiTree T) //利用栈中序遍历二叉树  
\{  
BiTNode \*p=T;  
SqStack S;  
InitStack(S);  
Push(S,T);  
while(S.top!=S.base) //当栈不为空  
\{  
while(GetTop(S,p)&&p)  
\{  
Push(S,p->lchild);  
\}  
Pop(S,p);  
if(S.top!=S.base)  
\{  
Pop(S,p);  
if(!Visit(p->data))  
return ERROR;  
Push(S,p->rchild);  
\}

\}  
return OK;  
\}

int main()  
\{  
BiTree T;  
printf("先构造二叉树:\\n");  
CreateBiTree(T);  
printf("该二叉树中序遍历如下：\\n");  
InOrderTraverse(T);  
\}

[smile.gif]: /images/20220724/2363d9f0232a4cbfa87dbd1fe2c3ca6d.png