typedef int StackData;
typedef struct _node { StackData data; struct _node *next; }Node; typedef struct _linkStack { Node *top; }LinkStack; LinkStack *Create_Stack() { LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack)/sizeof(char)); if (s == NULL) { errno = MALLOC_ERROR; return NULL; } // 置空栈 s->top = NULL; return s; } void level_order(BTreeNode *node) { if (node == NULL) return; LinkStack *s1 = Create_Stack (); LinkStack *s2 = Create_Stack (); Push (s1,node); // 根节点进队 while (StackEmpty (s1) != TRUE) { // 队头元素出队 BTreeNode* tmp = NULL; if (StackEmpty (s2) != TRUE) //栈2不空，就出栈2 { Pop (s2,&tmp); } else { Pop (s1,&tmp); while(StackEmpty (s1) != TRUE) //把栈1的元素导入到栈2，最后一 个不用，直接输出 { Push (s2,tmp); Pop (s1,&tmp); } } printf ("L", tmp->data); if (tmp->lchild != NULL) Push (s1,tmp->lchild); // 左节点入队 if (tmp->rchild != NULL) Push (s1,tmp->rchild); // 右节点入队 } free(s1); free(s2); }
