二叉树的前序、中序、后序三种遍历的六种实现方式（递归、非递归）（C++）

实现语言：C++

存储方式：链式存储

struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(NULL),right(NULL); }一、前序遍历

前序遍历方式：根左右

递归实现：递归实现的方式代码一般比较简单快捷。

void preorder1(TreeNode* root){ if(root){ cout<<root->val; preorder1(root->left); preorder1(root->right); } cout<<endl; } 非递归实现：由于前序遍历方式有回溯的过程，所以需要用到栈把遍历过的节点存起来。 void preorder2(TreeNode* root){ if(root==NULL) cout<<"The tree is empty!"<<endl; stack<TreeNode*> s; while(root||!s.empty()){ while(root){ cout<<root->val; s.push(root); root=root->left; } root=s.top(); s.pop(); root=root->right; } }

二、中序遍历

中序遍历的方式：左根右

递归实现：

<pre name="code" class="cpp">void midorder1(TreeNode* root){ if(root){ midorder1(root->left); cout<<root->val; midorder1(root->right); } }

非递归实现：

void midorder2(TreeNode* root){ if(root) cout<<"empty!"<<endl; stack<int> s; while(root||!s.empty()){ while(root){ s.push(root); root=root->left; } root=s.top(); s.pop(); cout<<root->val; root=root->right; } } 三、后序遍历

后序遍历的方式：左右根

递归实现：

void postorder1(TreeNode* root){ if(root){ postorder(root->left); postorder(root->right); cout<<root->val; } }非递归实现：后序遍历的过程比较麻烦，有些节点需要遍历两遍（含有右子树的那些节点） 所以通过设置一个标志位来标志节点的当前遍历次数。

void postorder2(TreeNode* root){ if(root==NULL) cout<<"empty!"<<endl; else{ stack<TreeNode*> s; stack<int> v; while(root){ s.push(root); v.push(0); root=root->left; } while(!s.empty()){ root=s.top(); while(root->right&&v.top()==0) { v.pop(); v.push(1); root=root->right; s.push(root); v.push(0); while(root->left){ s.push(root); v.push(0); root=root->left; } } root=s.top(); cout<<root->val; s.pop(); v.pop(); } } }