我用vs2019实现C语言二叉树非递归中序遍历时，遍历时（InOrderTraverse(BiTree T))函数中打印没实现。
问题代码：
Status InOrderTraverse(BiTree T) //非递归中序遍历
{
BiTree P;
SqStack S;
InitStack(&S);
P = T;
while (P || !StackEmpty(S))
{
while (P)
{
Push(&S,P);
P = P->lchild;
}
if (!StackEmpty(S))
{
Pop(&S, &P);
printf("%c", P->data);
P = P->rchild;
}
}
return OK;
}
完整源码：
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;
typedef struct {
ElemType* base;
ElemType* top;
int StackSize;
}SqStack; //顺序栈
Status InitStack(SqStack* S) //初始化
{
S->base = (ElemType*)malloc(sizeof(ElemType) * MaxSize);
if (!S->base)
exit(0);
S->top = S->base;
S->StackSize = MaxSize;
return OK;
}
Status StackEmpty(SqStack S) //判断是否为空栈
{
if (S.base == S.top)
return OK;
else
ERROR;
}
Status Push(SqStack* S, ElemType e) //入栈
{
if (!S->base)
return ERROR;
*(S->top) = e;
S->top++;
return OK;
}
Status Pop(SqStack* S, ElemType* e) //出栈
{
if (S->base == S->top)
return ERROR;
*e = *(S->top - 1);
S->top--;
return OK;
}
typedef struct BiNode {
ElemType data;
struct BiNode* lchild, * rchild;
}BiNode, * BiTree;
Status Create_BiTree(BiTree *T) //初始化二叉树
{
char ch;
scanf("%c", &ch);
if (ch == '#')
{
*T = NULL;
}
else
{
*T = (BiTree)malloc(sizeof(BiNode));
(*T)->data = ch;
Create_BiTree(&(*T)->lchild);
Create_BiTree(&(*T)->rchild);
}
return OK;
}
Status InOrderTraverse(BiTree T) //非递归中序遍历
{
BiTree P;
SqStack S;
InitStack(&S);
P = T;
while (P || !StackEmpty(S))
{
while (P)
{
Push(&S,P);
P = P->lchild;
}
if (!StackEmpty(S))
{
Pop(&S, &P);
printf("%c", P->data);
P = P->rchild;
}
}
return OK;
}
int main()
{
BiTree T;
printf("请输入字符（#表示空指针）：");
Create_BiTree(&T);
printf("非递归遍历：");
InOrderTraverse(T);
return 0;
}
