非递归遍历二叉树的四种策略先序、中序、后序和层序

 先序遍历二叉树算法1

源码打印？
  1. // Copyright (c) 2009, ALex ZhonG. All rights reserved.  
  2.   
  3. Status PreOrderTraverse(BiTree T, Status (Visit *)(TElemType e))  
  4. {  
  5.     InitStack(S);  
  6.     Push(S, T);  
  7.     p = T;//或 GetTop(S, p);  
  8.     while(!StackEmpty(S) && p)  
  9.     {  
  10.         while(p)  
  11.         {  
  12.             if(!Visit(p->data))  
  13.                 return ERROR;  
  14.             Push(p->rchild);   
  15.             p = p->lchild;  
  16.         }  
  17.         Pop(S, p);  
  18.     }  
  19.     DestroyStack(S);  
  20.     return OK;  
  21. }  

先序遍历二叉树算法2

源码打印？
  1. // Copyright (c) 2009, ALex ZhonG. All rights reserved.  
  2.   
  3. Status PreOrderTraverse(BiTree T, Status (Visit *)(TelemType))  
  4. {  
  5.     InitStack(S);  
  6.     Push(S, T);  
  7.     p = T;  
  8.     while(!StackEmpty(S) && p)  
  9.     {  
  10.         while(p)  
  11.         {  
  12.             if(!Visit(p->data))  
  13.                 return ERROR;  
  14.             Push(S, p);  
  15.             p = p->lchild;  
  16.         }  
  17.         if(!StackEmpty(S))  
  18.         {  
  19.             Pop(S, p);  
  20.             p = p->rchild;  
  21.         }  
  22.     }  
  23.     DestroyStack(S);  
  24.     return OK;  
  25. }  

中序遍历二叉树算法

源码打印？
  1. // Copyright (c) 2009, ALex ZhonG. All rights reserved.  
  2.   
  3. Status InOrderTraverse(BiTree T, Status (Visit *)(TelemType e))  
  4. {  
  5.     InitStack(S);  
  6.     Push(S, T)'  
  7.     p = T;  
  8.     while(!StackEmpty(S) && p)  
  9.     {  
  10.         while(p)  
  11.         {  
  12.             Push(S, p);  
  13.             p = p ->lchild;  
  14.         }  
  15.         Pop(S, p);  
  16.         if(!Visit(p->data))  
  17.             return ERROR;  
  18.         p = p->rchild;  
  19.     }  
  20.     DestroyStack(S);  
  21.     return OK;  
  22. }  

后序遍历二叉树算法

源码打印？
  1. // Copyright (c) 2009, ALex ZhonG. All rights reserved.  
  2.   
  3. Status PostOrderTraverse(BiTree T, Status (Visit *)(TelemType e))  
  4. {  
  5.     InitStack(S);  
  6.     Push(S, T);  
  7.     p = T;  
  8.     while(!StackEmpty(S) && p)  
  9.     {  
  10.         if(p)  
  11.         {／／一直走到最左下的结点  
  12.             Push(S, p);  
  13.             p = p->lchild;  
  14.         }  
  15.         else  
  16.         {//p为NULL时  
  17.             GetTop(S, p);  
  18.             if(p->rchild && p->rchild != r)  
  19.             {//p有右孩子或p的右孩子不是刚刚被访问的  
  20.                 p = p->rchild;  
  21.                 Push(S, p);  
  22.                 p = p->lchild;  
  23.             }  
  24.             else  
  25.             {//p无右孩子或p右孩子刚刚被访问过时  
  26.                 Pop(S, p);  
  27.                 Visit(p->data);  
  28.                 r = p;  
  29.                 p = NULL;  
  30.             }  
  31.         }  
  32.     }  
  33.     DestroyStack(S);  
  34.     return OK;  
  35. }  

层序遍历二叉树算法

源码打印？
  1. // Copyright (c) 2009, ALex ZhonG. All rights reserved.  
  2.   
  3. Status LevelOrderTraverse(BiTree T, Status (Visit *)(TelemType e))  
  4. {  
  5.     InitQueue(Q);  
  6.     p = T;  
  7.     if(p)  
  8.     {  
  9.         if(!Visit(p->data)  
  10.             return ERROR;  
  11.         EnQueue(Q, p->lchild);  
  12.         EnQueue(Q, p->rchild);  
  13.         while(Q)  
  14.         {  
  15.             DeQueue(Q, p);  
  16.             if(!Visit(p->data))  
  17.                 return ERROR;  
  18.             if(p->lchild)  
  19.                 EnQueue(Q, p->lchild);  
  20.             if(p->rchild)  
  21.                 EnQueue(Q, p->rchild);  
  22.         }  
  23.     }  
  24.     return OK;  
  25. }  

欢迎讨论、批评和指正！

ALex ZhonG


原文链接：http://blog.csdn.net/poechant/article/details/4811531

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/10jschen/p/2637930.html