引言

二叉树有4种典型的遍历方法：前序、中序、后续、层序。每种遍历的方法在此不在赘述，主要给出四种方法的C++代码。

首先设二叉树结点的数据结构如下：

struct TreeNode{ int value; //结点值 TreeNode* left; //左孩子 TreeNode* right; //右孩子 TreeNode(int _value,TreeNode* _left,TreeNode* _right): value(_value),left(_left),right(_right){} };

1、前序遍历

递归：

void preRecrusion(TreeNode* root){ if(root == NULL) return; std::cout << root->value << endl; //根 preRecrusion(root->left); //左 preRecrusion(root->right); //右 }

非递归：

void preRecrusion(TreeNode* root){ std::stack<TreeNode*> m_stack; //采用辅助栈来完成 while(root != NULL || !m_stack.empty()){ if(root != NULL){ std::cout<< root->value <<endl; //输出 m_stack.push(root); root = root->left; } else{ root = m_stack.top(); m_stack.pop(); root = root->right; } } }

2、中序遍历

递归：

void inRecrusion(TreeNode* root){ if(root == NULL) return; inRecrusion(root->left); //左 std::cout << root->value << endl; //根 inRecrusion(root->right); //右 }

非递归：

void inRecrusion(TreeNode* root){ std::stack<TreeNode*> m_stack; //采用辅助栈来完成 while(root != NULL || !m_stack.empty()){ if(root != NULL){ m_stack.push(root); root = root->left; } else{ root = m_stack.top(); std::cout<< root->value <<endl; //输出 m_stack.pop(); root = root->right; } } }

3、后序遍历

递归：

void postRecrusion(TreeNode* root){ if(root == NULL) return; postRecrusion(root->left); //左 postRecrusion(root->right); //右 std::cout << root->value << endl; //根 }

非递归：

void postRecrusion(TreeNode* root){ std::stack<TreeNode*> m_stack; //采用辅助栈来完成 TreeNode* lastvisit = root; while(root != NULL || !m_stack.empty()){ if(root != NULL){ m_stack.push(root); root = root->left; } else{ root = m_stack.top(); if(root->right == NULL || root->right == lastvisit){ std::cout<< root->value <<endl; //输出 m_stack.pop(); lastvisit = root; root = NULL; } else{ root = root->right; } } } }