Question

数据结构 二叉树的非递归遍历（用栈实现）

Answer 1

这是最近写过的
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define NULL 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1

typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree,*SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

Status InitStack (SqStack &S)
{//构造空栈并初始化
S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

Status StackEmpty(SqStack S)
{//判断是否为空栈，是返回TRUE，不是返回FALSE
if(S.base==S.top)
return TRUE;
else
return FALSE;
}

Status Push(SqStack &S,BiTree e)
{//将元素e压入栈顶
if(S.top-S.base>=S.stacksize)
{//栈满，追加存储空间
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof (SElemType));
if(!S.base)exit(OVERFLOW);//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize +=STACKINCREMENT;
}
*S.top++=e;
return OK;
}

Status Pop(SqStack &S,SElemType &e)
{//删除栈顶元素，用e返回其值，并返回OK，否则返回ERROR
if(S.top==S.base) return ERROR;//空栈情况
e=*--S.top;
return OK;
}

Status InitBiTree(BiTree &T)
{//构造空二叉树T
T=NULL;
return OK;
}

BiTree CreateBiTree(BiTree &T)
{//按先序次序输入二叉树中结点的值，空格字符表示空树
//构造二叉链表表示的二叉树T
char ch;
scanf("%c",&ch);
if (ch=='.') T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return T;
}
Status PrintElement(TElemType e)
{//输出元素e的值
printf("%c",e);
return OK;
}

Status InOrderTraverse2(BiTree T, Status (*Visit)(TElemType)) {
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
SqStack S;
BiTree p;
InitStack(S); p = T;
while (p || !StackEmpty(S)) { //P或stack不为空
if (p) {
Push(S, p);
p = p->lchild;
} // 非空指针进栈，继续左进
else { // 上层指针退栈，访问其所指结点，再向右进
Pop(S, p); //弹栈，将p指向被弹结点
if (!Visit(p->data)) //所访问结点不存在
return ERROR;
p = p->rchild;
}
}
return OK;
} // InOrderTraverse

void main()
{
BiTree T;
InitBiTree(T);
printf("创建二叉树T，空树用.代替：\n");
CreateBiTree(T);
printf("\n非递归算法中序遍历二叉树：");
InOrderTraverse2(T,PrintElement);
printf("\n");
}

追问

我这怎么不能运行啊

追答

要正确输入，用点表示没有左/右子树