zhan.txt

来自「用栈实现二叉数的遍历 其中构造的栈是一个动态的栈」· 文本 代码 · 共 132 行

#include<stdio.h>
#include<malloc.h>
#define struct_sizes 20
#define adds 10 

typedef struct bitnode
{ 
char data;
struct bitnode *lchild,*rchild;
}*bitree; 


typedef struct 

{ 
bitree *base;
bitree *top;
int stacksize; 
}sqstack; 

int initstack(sqstack *S)
{ 
S->base=(bitree *)malloc(struct_sizes*sizeof(bitnode));
if(!S->base)return 0;
S->top = S->base;
S->stacksize = struct_sizes;
return 1; 
}

int stackempty(sqstack *S)

{ 
if(S->base==S->top)return 1;
else return 0; 
} 

int push(sqstack *S,bitree e)
{ 
if(S->top - S->base >= S->stacksize)
{ 
S->base = (bitree *)realloc(S->base,(S->stacksize + adds) * sizeof (bitree));
if(!S->base)return 0;
S->top = S->base + S->stacksize;
S->stacksize += adds;
} 
*(S->top++)=e;
return 1; 
}

int pop(sqstack *S,bitree &e)
{ 
if(S->top == S->base)return 0;
e = * --S->top;

return 1; 
}

int gettop(sqstack *S,bitree &e)
{ 
if(S->top == S->base) return 0;
e = *(S->top - 1);

return 1; 
}

void createBinTree(bitree &t)

{

       t=(bitree)malloc(sizeof bitnode);

       char c;

       scanf("%c",&c);

       if(c==' ')

              t=NULL;

       else

       {

              t->data=c;

              createBinTree(t->lchild);

              createBinTree(t->rchild);

       }

}
int InOrder(bitree T)
 { if(T)
 {
   InOrder( T->lchild);
   printf("%c ",T->data);
   InOrder( T->rchild);
   } return 1;
 }
 int mid_norecursion(bitree T,sqstack *S)

{ 

bitree p;
p=T; 
if(!T)return 0; 
initstack(S);
push(S,T);
while(!stackempty(S)) 
{ 
while(gettop(S,p)&&p)
push(S,p->lchild);
pop(S,p);
if(!stackempty(S))
{ 
pop(S,p);printf(" %c",p->data); 
push(S,p->rchild); 
} 
} 
return 1; 
}
 void main()
{bitree a;
 createBinTree(a);

 sqstack S;

 
 mid_norecursion(a,&S);

}