二叉树中序遍历的非递归算法-蒲公英云

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

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

用栈实现二叉树中序遍历的非递归算法

#include
#include
#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);
}