二叉树遍历非递归实现

1. 遍历是二叉树各种操作的基础，上一节给出的遍历算法是递归实现的，本节给出二叉树遍历的非递归实现，非递归实现需要使用前面讲到的数据结构——栈、队列来作为辅助空间。

   • 先序遍历
   [cpp]  view plain copy

   1. int preorder_traverse(bitree bt, int (*visit)(elemtype e))  
   2. {  
   3.     sqstack     s;  
   4.     bitree      p;  
   5.   
   6.     init_stack(&s);  
   7.   
   8.     p = bt;  
   9.     while (p || !is_stack_empty(s)) {  
   10.         while (p) {                              /* 左结点依次进栈，向左走到尽头 */  
   11.             visit(p->data);  
   12.             push_stack(&s, p);  
   13.             p = p->lchild;  
   14.         }  
   15.         if (!is_stack_empty(s)) {  
   16.             pop_stack(&s, &p);                 /* 出栈 */  
   17.             p = p->rchild;  
   18.         }  
   19.     }  
   20.     return OK;  
   21. }  

   根结点先进栈，访问结点值，左孩子依次进栈，直到最左的孩子进栈。然后栈顶指针出栈，退至上一层，然后访问右子树，右子树访问完成之后，退至上一层，直至栈空，节点访问完成。先序遍历访问结点值是在结点进栈时。理解此算法最好找一棵简单的树跟着程序走一遍，在纸上画出栈的进栈、出栈情况。
   • 中序遍历

   [cpp]  view plain copy

   1. int inorder_traverse(bitree bt, int (*visit)(elemtype e))  
   2. {  
   3.     sqstack     s;  
   4.     bitree      p;  
   5.   
   6.     init_stack(&s);  
   7.   
   8.     p = bt;  
   9.     while (p || !is_stack_empty(s)) {  
   10.         while (p) {  
   11.             push_stack(&s, p);  
   12.             p = p->lchild;  
   13.         }  
   14.         if (!is_stack_empty(s)) {  
   15.             pop_stack(&s, &p);  
   16.             visit(p->data);  
   17.             p = p->rchild;  
   18.         }  
   19.     }  
   20.     return OK;  
   21. }  

   中序遍历和先序遍历类似，只是访问结点值是在出栈的时候，而先序遍历是在进栈的时候。

   • 后序遍历

   [cpp]  view plain copy

   1. int postorder_traverse(bitree bt, int (*visit)(elemtype e))  
   2. {  
   3.     sqstack     s;  
   4.     bitree      p, q;  
   5.   
   6.     init_stack(&s);  
   7.   
   8.     p = bt;  
   9.     q = NULL;  
   10.     while (p || !is_stack_empty(s)) {  
   11.         while (p) {  
   12.             push_stack(&s, p);  
   13.             p = p->lchild;  
   14.         }  
   15.         if (!is_stack_empty(s)) {  
   16.             get_top(s, &p);                     /* 取栈顶元素 */  
   17.             if (!p->rchild || p->rchild == q) { /* 如果p没有右孩子，或右孩子已经访问过 */  
   18.                 visit(p->data);  
   19.                 q = p;  
   20.                 p = NULL;  
   21.                 --s.top;/* 退栈 */  
   22.             }  
   23.             else  
   24.                 p = p->rchild;  
   25.         }  
   26.     }  
   27.     return OK;  
   28. }  

   后序遍历和先序、中序类似，但要稍复杂一点，需要判断结点是否有右孩子和右孩子是否访问过。
   

   • 层次遍历

   [cpp]  view plain copy

   1. int levelorder_traverse(bitree bt, int (*visit)(elemtype e))  
   2. {  
   3.     sqqueue     sq;  
   4.     bitree      cur;  
   5.       
   6.     init_queue(&sq);  
   7.   
   8.     if (bt) {  
   9.         in_queue(&sq, bt);  
   10.         while (!is_queue_empty(sq)) {  
   11.             out_queue(&sq, &cur);  
   12.             visit(cur->data);  
   13.   
   14.             if (cur->lchild)  
   15.                 in_queue(&sq, cur->lchild);  
   16.             if (cur->rchild)  
   17.                 in_queue(&sq, cur->rchild);  
   18.         }  
   19.     }  
   20.     return OK;  
   21. }  

   层次遍历算法比较好理解，使用队列作为辅助空间，根节点首先进队列，如果队列不为空的话，访问结点值再出队列，然后左孩子进队列（如果有的话），右孩子进队列（如果有的话）。
   
   • 总结

   遍历二叉树算法基本操作是访问结点，不论按哪一种次序进行遍历，对含n个结点的二叉树时间复杂度都为O(n)。
   • 算法实现源码

   免费下载：http://download.csdn.net/detail/algorithm_only/3800074