C语言结构并非递归遍历二叉树

C语言构造并非递归遍历二叉树

源代码：

#include<stdio.h>
#include<malloc.h>

#define SIZE 100
#define STACKINCREMENT 10
#define FALSE 1
#define ERROR 0
#define OK 1
#define NO 0

//二叉树
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

typedef int Status;
BiTree T;


//栈的结构体
typedef  struct
{
    BiTree a;
} SElemType;
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
} Stack;

Status 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 OK;
} // CreateBiTree

int vi(char c)
{
    printf("%c ",c);
    return OK;
}

//先序遍历的递归
void PreOrder(BiTree T)
{
    if(T)
    {
        vi(T->data);      //访问结点
        PreOrder(T->lchild);       //遍历左子树
        PreOrder(T->rchild);       //遍历右子树
    }
}

//栈操作
Status InitStack(Stack *S)
{
    S->base=(SElemType *)malloc(SIZE*sizeof(SElemType));
    if(!S->base) exit(0);
    S->top=S->base;
    S->stacksize=SIZE;
    return OK;
}
Status Push(Stack *S,SElemType e)
{
    if(S->top-S->base>=S->stacksize)
    {
        S->base=(SElemType *)malloc((S->stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!S->base) exit(0);
        S->top=S->base+S->stacksize;
        S->stacksize+=STACKINCREMENT;
    }
    *S->top++=e;
    return OK;
}
Status Stackempty(Stack S)//栈是否为空
{
    if(S.top==S.base)
        return OK;
    else
        return NO;

}
Status Pop(Stack *S,SElemType *e)
{
    if(S->top==S->base) return ERROR;
    *e=*--S->top;
    return OK;
}
Status StackLength(Stack S)//求栈的长度
{
    return (S.top-S.base);
}


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


//后序遍历的递归
void PostOrder(BiTree T)
{
    // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
    // 中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
    if(T)
    {
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    vi(T->data);
    }
} // InOrderTraverse

int main()
{
    printf("先序输入二叉树(空格代表空节点)：\n");
    CreateBiTree(&T);
    printf("递归先序输出二叉树：\n");
    PreOrder(T);
    printf("\n");
    printf("非递归中序输出二叉树：\n");
    InOrderTraverse(T, vi);
    printf("\n");
    printf("递归后序输出二叉树：\n");
    PostOrder(T);
    printf("\n");
    return 0;
}

运行结果：