二叉树的递归遍历比较简单，如果要求非递归遍历，那么我们可以考虑使用栈来模拟递归调用，具体见代码：
class Tree { public: int val; Tree *left = NULL, *right = NULL; } vector<int> pre,in,post; //前序遍历 void pre_trans_recursion(Tree* root) { if(root==NULL) return; pre.push_back(root->val); pre_trans_recursion(root->left); pre_trans_recursion(root->right); } void pre_trans(Tree* root) { stack<Tree*> s; Tree* node = root; while(node!=NULL||!s.empty()) { while(node!=NULL) { pre.push_back(node->val); //先序遍历在入栈的时候进行输出 s.push(node); node = node->left; } if(!s.empty()) { node = s.top(); s.pop(); node = node->right; } } } //中序遍历 void in_trans_recursion(Tree* root) { if(root==NULL) return; in_trans_recursion(root->left); in.push_back(root->val); in_trans_recursion(root->right); } void in_trans(Tree* root) { stack<Tree*> s; Tree* node = root; while(node!=NULL||!s.empty()) { while(node!=NULL) { s.push(node); node=node->left; } if(!s.empty()) { node = s.top(); in.push_back(node->val); //中序遍历在出栈的时候进行输出 s.pop(); node = node->right; } } } //后序遍历 void post_trans_recursion(Tree* root) { if(root==NULL) return; post_trans_recursion(root->left); post_trans_recursion(root->right); post.push_back(root->val); } void post_trans(Tree* root) { if(root==NULL) return; stack<Tree*> s; Tree* pre_node = NULL; Tree* node = root; s.push(root); while(node!=NULL||!s.empty()) { node = s.top(); //当此时已经为叶子节点。或者某节点左右子树已经遍历过了，那么就进行输出，然后弹出栈 if((node->left==NULL&&node->right==NULL)||(pre_node!=NULL&&(pre_node==node->left||pre_node==node->right)) { post.push_back(node->val); s.pop(); pre_node = node; } else //如果node此时左右子树不都为空，那么就进行压入栈 { if(node->right!=NULL) //先压入右子树，这样先弹出的就是左子树 s.push(node->right); if(node->left!=NULL) s.push(node->left); } } }
