1.先序遍历

1 void PreorderTraversal(BinTree BT) 2 { 3     BinTree T; 4     std::stack
     
       BtStack; 5     T = BT; 6     while (T || !BtStack.empty()) 7     { 8         while (T) 9         {10             BtStack.push(T);11             printf("%c ", T->Data);12             T = T->Left;13         }14         T = BtStack.top();15         BtStack.pop();16         T = T->Right;17 18     }19 }
     

2.中序遍历

1 void InorderTraversal(BinTree BT) 2 { 3     BinTree T; 4     std::stack
     
       BtStack; 5     T = BT; 6     while (T || !BtStack.empty()) 7     { 8         while (T) 9         {10             BtStack.push(T);11             T = T->Left;12         }13         T = BtStack.top();14         BtStack.pop();15         printf("%c ", T->Data);16         T = T->Right;17 18     }19 }
     

3.后序遍历（重难点）

在树的结构体结点中添加一个表示访问次数的数据域，visit:

1 typedef Position BinTree;    //二叉树类型2 struct TNode {3     ElementType Data;    //结点数据4     int visit;5     BinTree Left;        //指向左子树6     BinTree Right;        //指向右子树7 };

 遍历的代码程序：

1 void PostorderTraversal(BinTree BT) 2 { 3     BinTree T = BT; 4     std::stack
     
       BtStack; 5     while (T || !BtStack.empty()) 6     { 7         while (T) 8         { 9             T->visit++;10             BtStack.push(T);11             T = T->Left;12         }13         if (!BtStack.empty())14         {15             T = BtStack.top();        //第二次或第三次访问该结点16         17             if (T->visit == 2)                //当visit == 2时，该结点已经被访问了3次，所以可以被输出了18             {19                 printf("%c ", T->Data);20                 BtStack.pop();21                 T = NULL;22             }23             else24             {25                 T->visit++;        //第二次访问26                 T = T->Right;    //即将进入第三次访问27             }28         }29     }30 }