MAX_PLAY
BEI-TIAN-XUAN
采纳率100%
2021-03-06 17:16

二叉树非递归中序遍历?

我用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;
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答