#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define error 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;
#define initsize 100   //栈的初始化容量
#define stackinc   10  //栈的增加容量


typedef int  ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;


typedef    struct                        //构建栈
{
    BiTree *base;                //指针要和所指的元素类型保持一致
    BiTree    *top;
    int stacksize;
}SqStack;

int InitStack(SqStack &S)
{//初始化栈

    S.base=(BiTree*)malloc(initsize*sizeof(BiTree));
    if(!S.base)  return error;
    S.base=S.top;
    S.stacksize=initsize;
    return OK;
}
int Push(SqStack &S,BiTree e)                    //入栈
{
    if(S.top-S.base>=S.stacksize)
    {
    S.base=(BiTree*)realloc(S.base,(S.stacksize+stackinc)*sizeof(BiTree));
    if(!S.base)
        return error;
    S.top=S.base+S.stacksize;
    S.stacksize+=stackinc;
    }
    *S.top=e;
    S.top++;

return OK;
}

BiTree Pop(SqStack &S,BiTree e)                //出栈
{
    if(S.top==S.base)
        return error;
    e=*(S.top-1);
    S.top--;
    return e;
}

int StackEmpty(SqStack &S)
{
    if(S.top==S.base)
        return OK;
    else
        return 0;
}




Status insertNode(BiTree &T,int n)                            //插入函数
{
    if(!T)
    {
        if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;                        //一定要进行空间分配 动态分配空间
        T->data=n;
        T->lchild=NULL;
        T->rchild=NULL;
    }
    else
    {
        if(n<=T->data)
            insertNode(T->lchild,n);
        else
            insertNode(T->rchild,n);
    }
    return OK;
}
   



Status CreateBiTree(BiTree &T)                        //初始化二叉树
{
    T=NULL;

    int m,n;
    scanf("%d",&m);
    while(m--)
    {
        
        scanf("%d",&n);
        insertNode(T,n);
    }
    return OK;                        
   

  return OK;
} // CreateBiTree








Status PrintElement(ElemType e ) {  // 输出元素e的值
printf("%d ", e);
return OK;
}// PrintElement











Status Search(BiTree T,int key,BiTree f,BiTree &p)                                //遍历树，查找是否存在元素，存在用TURE  错误返回FLASE
{                                                                                //此处也可以bool函数


    if(!T){p=f;return FALSE;}                                                    //查找不成功，
    else if(key==T->data){p=T;return TRUE;}                                        //查找成功
    else if(key<T->data) return Search(T->lchild,key,T,p);                        //在左子树中继续查找
    else  return Search(T->rchild,key,T,p);                                        //在柚子树中继续查找
}

Status Insert(BiTree &T,int e)                                                    //按二叉排序树，插入关键字
{
    BiTree s;
    BiTree p;
    p=T;

   

    if(!Search(T,e,NULL,p))
    {
        
        s=(BiTNode *)malloc(sizeof(BiTNode));
        s->data=e;
        s->lchild=s->rchild=NULL;
        if(!p) T=s;                                                            //被插入结点s为新的根结点
        else if(e<p->data) p->lchild=s;                                        //插入的是左孩子
        else p->rchild=s;                                                    //插入的是柚孩子
        return TRUE;
    }
    else return FALSE;
}



int InOrderT(BiTree T)
{
    //非递归中序遍历二叉树    算法6.3
    SqStack S;
    BiTree p;
printf("11111");////////////
    InitStack(S);
    p=T;
    while(p||!StackEmpty(S))
    {
        printf("222222");////////////
        if(p){Push(S,p);p=p->lchild;}
        else{
            p=Pop(S,p);
            if(!PrintElement(p->data))
                return error;
            p=p->rchild;
            }
    }
    return OK;
}





int main()   //主函数
{
   BiTree T;
   BiTree p;
   CreateBiTree(T);
   p=T;

    int g;                                                        
    scanf("%d",&g);   
   
    Insert(T,g);
        


 InOrderT(T);
printf("%d",g);

   return OK;
   
 }//main
/*
7
40 20 60 18 50 56 90
30




输出样例



18 20 30 40 50 56 60 90

*/

顶一个  

额，那个

栈初始化中 把 S.base=S.top;改成  S.top=S.base;