假设二叉树的节点为

1 template
     
      2 struct BTNode3 {4     T data;5     BTNode * left;6     BTNode * right;7 };
     

1. 先序遍历

1  template
     
       2  void PreOrder(BTNode *root, Func visit) 3  { 4      std::stack
      
        s; 5      BTNode *t = root;   //t总是指向下一个要访问的节点。 6      while(t) 7      { 8          visit(t -> data); 9          if(t -> right)              //访问当前节点后，下一个应该访问 t 的左孩子；栈总是保存右孩子10              s.push(t -> right);11          if(t -> left)              //左孩子存在，下一个要访问左孩子12              t = t -> left;13          else if(!s.empty())　　　　//t没左孩子，访问最后入栈的右孩子（不一定是t的）14          {15              t = s.top();16              s.pop();17          }18          else19              return;20      }21  }
      
     

2. 中序遍历

1  template
     
       2  void InOrder(BTNode * root, Func visit) 3  { 4      std::stack
      
        s; 5      auto goFarLeft = [&s](BTNode *node) -> BTNode*    //寻找根结点为node的子树的最左边的元素 6      { 7              if(!node) return NULL; 8              while(node->left) 9              {10                  s.push(node);11                  node = node -> left;12              }13              return node;14      }15      BTNode * t = goFarLeft(root);         //最左边的元素最先访问16      while(t)17      {18          visit(t->data);19          if(t->right)20              t = goFarLeft(t->right);21          else if(!s.empty())22          {23              t = s.top();24              s.pop();25          }      26          else27              t = NULL;28      }29  }
      
     

 3. 后序遍历

1 template
     
       2  void PostOrder(BTNode *root, Func visit) 3  { 4      std::stack
      
        s; 5       6      //从node节点往下走，能往左时就往左，否则就往右，直到走不动为止； 7      //将中间路过的节点入栈（不包括最后一个) 8      auto goFarLeftRight = [&s](BTNode *node) -> BTNode* 9      {10          if(!node)11              return NULL;12          while(node -> left || node -> right)13          {14              s.push(node);15              if(node -> left)16              　　node = node -> left;17              else18                  node = node -> right;19          }20          return node;21  22      }23  24      BTNode *t = goFarLeftRight(root);   25      while(t)26      {27          visit(t -> data);28          if(!s.empty())29          {30              t = s.top();31              if(t->left && t->right)32                  t = goFarLeftRight(t -> right);33              else34                  s.pop();35          }36          else37              return;38      }39  }