馨儿341 馨儿341
酱油是拿来打的,不是拿来喝的。。。
关注数: 17 粉丝数: 23 发帖数: 1,154 关注贴吧数: 15
等下就删,重要东西 #include <iostream> #define STACK_INIT_SIZE 100 #define STACK_ADD 10 //节点定义 typedef struct BiTNode { int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //栈定义 typedef struct SqStack { BiTree base,top; long stacksize; }SqStack; //初始化栈 void initStack(SqStack &S) { S.top=S.base=(BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTNode)); while(!S.base) { S.top=S.base=(BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTNode)); } S.stacksize=STACK_INIT_SIZE; } //压栈 void push(SqStack &S,BiTree e) { if(S.top-S.base>=S.stacksize) { S.base=(BiTree)realloc(S.base,(S.stacksize+STACK_ADD)*sizeof(BiTNode)); while(!S.base) { S.base=(BiTree)realloc(S.base,(S.stacksize+STACK_ADD)*sizeof(BiTNode)); } S.stacksize+=STACK_ADD; } *(S.top++)=*e; } //出栈 void pop(SqStack &S,BiTree &e) { if(S.base==S.top) exit(0); else *e=*(--S.top); } // bool stackEmpty(SqStack &S) { if(S.top==S.base) return true; else return false; } //得到栈顶 bool getTop(SqStack &S,BiTree &p) { p=S.top; if(p) return true; else return false; } //创建树 void createBiTree(BiTree &T) { int num; std::cin>>num; if(num==0) T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); while(!T) { T=(BiTree)malloc(sizeof(BiTNode)); } createBiTree(T->lchild); createBiTree(T->rchild); } } //遍历树 void preOrderserve(BiTree &T,SqStack &S) { BiTree p; initStack(S); push(S,T); while(!stackEmpty(S)) { while(!getTop(S,p) && p) { push(S,T->lchild); } pop(S,p); if(!stackEmpty(S)) { pop(S,p); std::cout<<p->data<<std::endl; push(S,p->rchild); } } } int main(int argc,char* argv[]) { SqStack S; BiTree T; createBiTree(T); preOrderserve(T,S); return 0; }
1 下一页