#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define FALSE 0
#define TRUE 1
typedef char StackElementType;
typedef char ElemType;
typedef struct Tree
{
ElemType data;
struct Tree *Lchild;
struct Tree *Rchild;
}BiTNode, *BiTree;
typedef struct node
{
BiTree date;
struct node *next;
}LinkStackNode, *LinkStack;
/*构造一个空栈S*/
void InitStack(LinkStack *top)
{
(*top) = (LinkStack)malloc(sizeof(LinkStackNode));
(*top)->next = NULL;
}
/* 将数据元素x压入栈top中 */
int Push(LinkStack top,BiTree x)
{
LinkStackNode *p;
p = (LinkStackNode*)malloc(sizeof(LinkStackNode));
if (p == NULL)
return(FALSE); /*申请空间失败 */
p->date = x;
p->next = top->next;
top->next = p; /* 修改当前栈顶指针 */
return(TRUE);
}
/* 将栈top的栈顶元素弹出,放到x所指的存储空间中 */
int Pop(LinkStack top, BiTree *x)
{
LinkStackNode *p;
p = top->next;
if (p == NULL) /*栈为空*/
return(FALSE);
top->next = p->next;
*x=p->date;
free(p); /*释放存储空间 */
return(TRUE);
}
int GetTop(LinkStack top, BiTree *x)
{
LinkStackNode *p;
p=top->next;
if(p==NULL) /*栈为空*/
return(FALSE);
*x=p->date;
return(TRUE);
}
/*判空*/
int IsEmpty(LinkStackNode *top)
{
if (top == NULL)
return 1;
return 0;
}
//创建二叉树
void CreateBinTree(BiTree *T)
{
char ch;
ch = getchar();
if (ch == '.')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBinTree(&((*T)->Lchild));
CreateBinTree(&((*T)->Rchild));
}
}
//非递归中序遍历
int InOrder(BiTree T)
{
LinkStackNode *top;
InitStack(&top);
BiTNode *p;
p=T;
while (p != NULL || !IsEmpty(top))
{
if (p != NULL) /* 根指针进栈, 遍历左子树 */
{
Push(top, p);
p = p->Lchild;
}
else
{ /*根指针退栈, 访问根结点, 遍历右子树*/
Pop(top,&p);
printf("%c",p->data);
p = p->Rchild;
}
}
return 1;
}
//非递归后序遍历
void PostOrder(BiTree root)
{
LinkStackNode *s;
BiTNode *p,*q;
q=NULL;
p=root;
InitStack(&s);
while(p != NULL || !IsEmpty(s))
{
if (p != NULL) /* 根指针进栈, 遍历左子树 */
{
Push(s,p);
p = p->Lchild;
}
else
{ /*根指针退栈, 访问根结点, 遍历右子树*/
GetTop(s,&p);
if((p->Rchild==NULL)||(p->Rchild==q))
{
printf("%c",p->data);
q=p;
Pop(s,&p);
p=NULL;
}
else
p=p->Rchild;
}
}
}
int main()
{
BiTree T,root;
printf("先序输出二叉树:(用“.”代表空结点)\n");
CreateBinTree(&T);
printf("中序遍历结果为:\n");
InOrder(T);
printf("后序遍历结果为:\n");
PostOrder(T);
return 0;
}
因为报错了,最后的return 都不是0
GetTop(s,&p);还是应该要检查返回值是否为TRUE啊,不然p是空的
您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~
ps:问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632