1、前序遍历的非递归实现
根据先序遍历的顺序，先访问根节点，再访问左子树，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，非递归的实现思路如下：
对于任一节点P，
1）输出节点P，然后将其入栈，再看P的左孩子是否为空；
2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；
3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4）若不为空，则循环至1）操作；
5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；
6）直到当前节点P为NULL并且栈空，遍历结束。
2、中序遍历的非递归实现
根据中序遍历的顺序，先访问左子树，再访问根节点，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，非递归的实现思路如下：
对于任一节点P，
1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3）若不为空，则重复1）和2）的操作；
4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
5）直到当前节点P为NULL并且栈为空，则遍历结束。
3、后序遍历的非递归实现
根据后序遍历的顺序，先访问左子树，再访问右子树，后访问根节点，而对于每个子树来说，又按照同样的访问顺序进行遍历。后序遍历的非递归的实现相对来说要难一些，要保证根节点在左子树和右子树被访问后才能访问，思路如下：
对于任一节点P，
1）先将节点P入栈；
2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
4）直到栈空，遍历结束。
//非递归前序遍历1 void pre_order (BTreeNode *node) { if (node == NULL) { errno = ERROR; return; } LinkStack *Stack = Create_Stack (); BTreeNode *tmp = node; //指向当前节点 while (tmp) { printf("L",tmp->data); Push (Stack,tmp); if (tmp->lchild) { tmp = tmp->lchild; continue; } while(StackEmpty(Stack) != TRUE) { Pop (Stack,&tmp); if(tmp = tmp->rchild) { break; } } } } } //非递归前序遍历2 void pre2_order (BTreeNode *node) { if (node == NULL) { errno = ERROR; return; } LinkStack *Stack = Create_Stack (); BTreeNode *tmp = node; //指向当前节点 while (tmp) { printf("L",tmp->data); Push (Stack,tmp); if (tmp->lchild) { tmp = tmp->lchild; continue; } while(Pop (Stack,&tmp) && (tmp = tmp->rchild) == NULL); } } //前序遍历（老师的） void pre1(BTreeNode *root) { if(root == NULL) return; LinkStack *stack = CreateStack(); BTreeNode* p = root; while (p != NULL || !StackEmpty(stack)) { while(p) { printf ("L", p->data); Push(stack, p); p = p->lchild; } if (!StackEmpty(stack)) { Pop (stack, &p); p = p->rchild; } } } //非递归中序遍历1 void mid_order (BTreeNode *node) { if (node == NULL) { errno = ERROR; return; } LinkStack *Stack = Create_Stack (); BTreeNode *tmp = node; //指向当前节点 while (tmp) { Push (Stack,tmp); if (tmp->lchild) { tmp = tmp->lchild; continue; } tmp = tmp->rchild; while(StackEmpty(Stack) != TRUE && tmp == NULL) { Pop (Stack,&tmp); printf("L",tmp->data); tmp = tmp->rchild; } } } //非递归中序遍历2 void mid2_order (BTreeNode *node) { if (node == NULL) { errno = ERROR; return; } LinkStack *Stack = Create_Stack (); BTreeNode *tmp = node; //指向当前节点 while (tmp) { Push (Stack,tmp); if (tmp->lchild) { tmp = tmp->lchild; continue; } tmp = tmp->rchild; while(tmp == NULL && Pop (Stack,&tmp)) { printf("L",tmp->data); tmp = tmp->rchild; } } } //中序遍历（老师的） void mid1(BTreeNode *root) { if(root == NULL) return; LinkStack *stack = CreateStack(); BTreeNode* p = root; while (p != NULL || !StackEmpty(stack)) { while(p) { Push(stack, p); p = p->lchild; } if (!StackEmpty(stack)) { Pop (stack, &p); printf ("L", p->data); p = p->rchild; } } } //非递归后序遍历 void last2_order (BTreeNode *node) { if (node == NULL) { errno = ERROR; return; } LinkStack *Stack = Create_Stack (); BTreeNode *tmp = node; //指向当前节点 BTreeNode *pre = NULL; //指向被输出的节点 Push (Stack,tmp); while (StackEmpty (Stack) != TRUE) { GetTop (Stack,&tmp); //若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出 if(tmp->lchild == NULL && tmp->rchild == NULL || pre != NULL &&(tmp->lchild == pre || tmp->rchild == pre)) { Pop (Stack,&tmp); printf("L",tmp->data); pre = tmp;//指向被输出的节点 continue; } if(tmp->rchild) { Push (Stack,tmp->rchild); } if(tmp->lchild) { Push (Stack,tmp->lchild); } } } //层次遍历（用栈代替队列） 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); } //层次遍历（队列实现）（老师的） void level_order(BTreeNode *root) { if (root == NULL) return; LinkQueue * queue = CreateQueue(); EnQueue (queue, root); // 根节点进队 while (!QueueEmpty(queue)) { // 队头元素出队 BTreeNode* p = NULL; DeQueue(queue, &p); printf ("L", p->data); if (p->lchild != NULL) EnQueue(queue, p->lchild); // 左节点入队 if (p->rchild != NULL) EnQueue(queue, p->rchild); // 右节点入队 } free(queue); }
