二叉树的结构：

1 typedef int ElementType;2 typedef struct TNode *Position;3 typedef Position BinTree;4 struct TNode5 {6     ElementType Data;7     BinTree Left;8     BinTree Right;9 };

 

二叉树先中后序遍历（递归实现）:

1 //递归实现中序遍历 2 void InorderTraversal(BinTree BT) 3 { 4     if(BT)   //如果不是空树 5     { 6         InorderTraversal(BT->Left); 7         printf("%d", BT->Data);       //此处假设对BT节点的访问就是打印数据 8         InorderTraversal(BT->Right); 9     }10 11 }12 13 14 //递归实现先序遍历15 void PreorderTraversal(BinTree BT)16 {17     if(BT)   //如果不是空树18     {19         printf("%d", BT->Data);20         PreorderTraversal(BT->Left);21         PreorderTraversal(BT->Right);22     }23 }24 25 26 //递归实现后序遍历27 void PostorderTraversal(BinTree BT)28 {29     if(BT)   //如果不是空树30     {31         PostorderTraversal(BT->Left);32         PostorderTraversal(BT->Right);33         printf("%d", BT->Data);34     }35 }

 

使用C++:

非递归实现中序遍历：

1 //非递归实现中序遍历 2 void InorderTraversal(BinTree BT) 3 { 4     stack
     
       S; 5     BinTree T = BT; 6     while(T || !S.empty()) 7     { 8         while(T) 9         {10             S.push(T);11             T = T->Left;12         }13         if(!S.empty())14         {15             T = S.top();16             printf("%d", T->Data);17             S.pop();18             T = T->Right;19         }20     }21 }
     

 

非递归实现先序遍历：

1 //非递归实现先序遍历 2 void PreorderTraversal(BinTree BT) 3 { 4     stack
     
       S; 5     BinTree T = BT; 6     while(T || !S.empty()) 7     { 8         while(T) 9         {10             printf("%d", T->Data);11             S.push(T);12             T = T->Left;13         }14         if(!S.empty())15         {16             T = S.top();17             S.pop();18             T = T->Right;19         }20     }21 }
     

 

非递归实现后序遍历：

因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用堆栈来存储节点，必须分清返回根节点时，是从左子树返回的，还从右子树返回的。

所以，使用辅助指针r，其指向最近访问过的节点。也可以在节点中增加一个标志域，记录是否已被访问。

1 //非递归实现后序遍历 2 void PostOrder3(BinTree BT)      3 { 4     BinTree T = BT, r = NULL;   //r用来标记最近访问过的节点 5     stack
     
       s; 6     while (T || !s.empty()) 7     { 8         if (T)  //T非空时，遇到一个节点就把这个节点入栈，走到最左边 9         {10             s.push(T);11             T = T->Left;12         }13         else14         {15             T = s.top();16             if (T->Right && T->Right != r)//右子树存在且未被访问17                 T = T->Right;18             else19             {20                 s.pop();21                 printf("%d", T->Data);22                 r = T;       //记录最近访问过的节点23                 T = NULL;    //节点访问完后，重置T指针24             }25         }//else26     }//while27 28 }
     

 

二叉树的层序遍历：

(1) 从队列中取出一个元素；

(2) 访问该元素所指节点；

(3) 若该元素所指节点的左右孩子节点非空，则将其左右孩子节点顺序入队。

不断执行这三步操作，直到队列为空，再无元素可取，二叉树的层序遍历就完成了。

1 //二叉树的层序遍历 2 void LeverorderTraversal(BinTree BT) 3 { 4     queue
     
       Q; 5     BinTree T; 6     if(!BT)     //如果是空树则直接返回 7         return; 8 　　 Q.push(BT); 9     while(!Q.empty())10     {11         T = Q.front();12         printf("%d", T->Data);13         Q.pop();14         if(T->Left)15             Q.push(T->Left);16         if(T->Right)17             Q.push(T->Right);18     }19 }