#include <stdio.h>
#include <malloc.h>
#include <conio.h>
typedef char DataType;
typedef struct Node
{
    DataType data;
    struct Node *LChild;
    struct Node *RChild;
}BiTNode, *BiTree;
void CreateBiTree(BiTree *bt)
{
    char ch;
    ch = getchar();
    if(ch=='.') *bt=NULL;
    else
    {
        *bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
        (*bt)->data=ch;
        CreateBiTree(&((*bt)->LChild)); //生成左子树
        CreateBiTree(&((*bt)->RChild)); //生成右子树
    }
}
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
typedef BiTree StackElementType;
typedef struct
{
    StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
    int top;                  /*用来存放栈顶元素的下标，top为-1表示空栈*/
}SeqStack;
/*初始化*/
void InitStack(SeqStack *S)
{
    /*构造一个空栈S*/
      S->top = -1;
}
/*判栈空*/
int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
{
    return(S->top==-1?TRUE:FALSE);
}
/*判栈满*/
int IsFull(SeqStack *S)    /*判断栈S为满栈时返回值为真，反之为假*/
{
    return(S->top==Stack_Size-1?TRUE:FALSE);
}
int Push(SeqStack *S,StackElementType x)
{
    if(S->top==Stack_Size-1)  先序中序后序遍历二叉树
        return(FALSE);  /*栈已满*/
    S->top++;
    S->elem[S->top] = x;
    return(TRUE);
}
int Pop(SeqStack *S,StackElementType *x)
{ 
    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
    if(S->top == -1)  /*栈为空*/
        return(FALSE);
    else
    {
          *x = S->elem[S->top];
        S->top--;    /* 修改栈顶指针 */
          return(TRUE);
    }
}
#include "bitree.h"
#include "stack.h"
void Visit(char ch)
{
    printf("%c  ",ch);
}
void inorder(BiTree root)  /* 中序遍历二叉树，root为二叉树的根结点 */
{
    int top=0;
    BiTree p;
    BiTree s[Stack_Size];
    int m;
    m = Stack_Size-1;
    p = root;
    do
    {
        while(p!=NULL)
        {
            if (top>m) return;
            top=top+1; 
            s[top]=p;
            p=p->LChild;
        };  /* 遍历左子树 */
        if(top!=0)
        {
            p=s[top];
            top=top-1;
            Visit(p->data);  /* 访问根结点 */
            p=p->RChild;  /* 遍历右子树 */
        } 
    }
    while(p!=NULL || top!=0);
}
void  InOrder(BiTree root) /* 中序遍历二叉树的非递归算法 */
{
    SeqStack S;
    BiTree p;
    InitStack (&S);
    p=root;
    while(p!=NULL || !IsEmpty(&S))
    {
        if (p!=NULL)  /* 根指针进栈，遍历左子树 */
        {
            Push(&S,p);
            p=p->LChild;
        }
        else
        {  /*根指针退栈，访问根结点，遍历右子树*/
            Pop(&S,&p);
            Visit(p->data); 
            p=p->RChild;
        }
    }
}
void main()
{
    BiTree T;
    printf("按扩展先序遍历序列建立二叉树，请输入序列:\n");
    CreateBiTree(&T);
    printf("中序遍历输出叶子结点1为:");
    inorder(T);
    printf("\n");
    printf("中序遍历输出叶子结点2为:");
    InOrder(T);
    getch();
}