非递归中序遍历二叉树-蒲公英云

非递归中序遍历二叉树

/*非递归中序遍历二叉树*/
#include<stdio.h>
#define maxsize 100
typedef char datatype;
/*二叉链表类型定义*/
typedef struct Binnode
{
    datatype data;                   /*数据域*/
    struct BinNode* lchild,*rchild;  /*指向左、右孩子的指针*/
}BinNode,*Bintree;
/*顺序栈类型定义*/
typedef struct
{
    Bintree data[maxsize];            /*存储栈中数据元素*/
    int top;                          /*标志栈顶位置*/
}SeqStk;
/*初始化栈*/
int InitStack(SeqStk *stk)
{
    stk->top=0;
    return 1;
}
/*判栈空*/
int EmptyStack(SeqStk *stk)
{
    if(stk->top==0)                   /*若栈为空，则返回值1，否则返回0.*/
        return 1;
    else
        return 0;
}
/*入栈*/
int Push(SeqStk *stk,Bintree x)
{
   if(stk->top==maxsize-1)                      /*判断栈是否满*/
   {
       printf("栈满\n");
       return 0;
   }
   else
   {
       stk->top++;                              /*栈未满，top值加1.*/
       stk->data[stk->top]=x;                   /*元素x进栈*/
       return 1;
   }
}
/*出栈*/
int Pop(SeqStk *stk)
{
    if(EmptyStack(stk))                         /*判断是否下溢（栈空）*/
    {
        printf("下溢\n");
        return 0;
    }
    else                                        /*未下溢，栈顶元素出栈。*/
    {
        stk->top--;                             /*top值减1*/
        return 1;
    }
}
/*取栈顶数据元素，栈顶数据元素通过参数返回。*/
Bintree GetTop(SeqStk *stk)
{
    if(EmptyStack(stk))
        printf("栈空\n");                        /*栈空，返回NULLData.*/
    else
        return stk->data[stk->top];             /*返回栈顶数据元素*/
}
/*按先序创建二叉树*/
Bintree CreateTree(Bintree T)
{
    datatype ch;
    scanf("%c",&ch);
    if(ch=='#')
        return NULL;
    else
    {
        T=(Bintree)malloc(sizeof(BinNode));
        T->data=ch;
        T->lchild=CreateTree(T->lchild);/*创建左子树*/
        T->rchild=CreateTree(T->rchild);/*创建右子树*/
        return T;
    }
}
/*非递归中序遍历二叉树*/
void preorder(Bintree T)
{
    Bintree p;
    SeqStk s;
    InitStack(&s);
    p=T;
    while(p || !EmptyStack(&s))
    {
        if(p)
        {
            Push(&s,p);                 /*当前结点指针入栈*/
            p=p->lchild;                /*当前指针指向左孩子*/
        }
        else
        {
            p=GetTop(&s);               /*栈顶元素退栈*/
            Pop(&s);
            printf("%c ",p->data);      /*访问当前结点*/
            p=p->rchild;                /*当前指针指向右孩子*/
        }
    }
}
main()
{
    Bintree t;
    printf("请按先序的方式输入二叉树的结点元素（注：#表示节点为空）:");
    t=CreateTree(t);
    printf("非递归中序遍历二叉树:");
    preorder(t);
}