二叉树的递归遍历操作根据根节点的遍历顺序分为前序遍历，中序遍历，后序遍历。
前序遍历： 在遍历以当前节点为根节点的树的左右节点前（此时左右节点都还未遍历），输出当前节点的值。 如下图所示二叉树，前序遍历结果应为：
A B D E C F G
前序遍历（图示）：
中序遍历： 在遍历以当前节点为根节点的树的右节点前（此时左节点已经遍历），输出当前节点的值。 如下图所示二叉树中，中序遍历结果应为：
D B E A F C G
中序遍历（图示）：
后序遍历： 在遍历以当前节点为根节点的树的左右节点后（此时左右节点都已经遍历），输出当前节点的值。 如下图所示二叉树中，后序遍历结果应为：
D E B F G C A
后序遍历（图示）：
层序遍历： 除以上三种遍历方法以外，二叉树还有一种层序遍历方法，即从上到下，从左到右依次遍历所有节点。层序遍历的实现需要借助队列，有些不太一样。 如上所示二叉树，层序遍历结果应为：
A B C D E F G
具体实现如下代码。
代码实现：
#include <iostream> #include <queue> using namespace std; struct TNode { char _val; TNode* _left; TNode* _right; TNode(char val):_val(val), _left(NULL), _right(NULL) {} }; class Tree { public: Tree(); ~Tree(); public: void PreOrder(); //先序遍历 void InOrder(); //中序遍历 void PostOrder(); //后序遍历 void LevelOrder();//层序遍历 private: //为了避免类的调用者访问类的私有成员 root_ //将具体操作封装为类私有函数供公共接口调用 TNode* Creat(); //创建树 void Release(TNode* root); //释放树 void preOrder(TNode* root); void inOrder(TNode* root); void postOrder(TNode* root); void levelOrder(TNode* root); private: TNode* root_; }; TNode* Tree::Creat() { TNode* temp; char val; cin >> val; //若输入的节点的值为 # ，则表示以当前节点为根节点创建一棵空树 if (val == '#') temp = NULL; else { temp = new TNode(val); temp->_left = Creat(); temp->_right = Creat(); } return temp; } void Tree::Release(TNode* root) { if (root == NULL) return ; else { Release(root->_left); Release(root->_right); delete root; } } void Tree::preOrder(TNode* root) { //若以当前节点为根节点的树为空，则退出当前节点的遍历 if (root == NULL) return ; else { cout << root->_val << ' ';//输出节点内的值。注意输出位置（前） preOrder(root->_left); preOrder(root->_right); } } void Tree::inOrder(TNode* root) { if (root == NULL) return ; else { inOrder(root->_left); cout << root->_val << ' ';//输出节点内的值（中） inOrder(root->_right); } } void Tree::postOrder(TNode* root) { if (root == NULL) return ; else { postOrder(root->_left); postOrder(root->_right); cout << root->_val << ' ';//输出节点内的值（后） } } void Tree::levelOrder(TNode* root) { //层序遍历。利用队列实现 queue<TNode*> q; if (root == NULL) return ; else { //若树不为空，将树的根节点入队 q.push(root); } while (!q.empty()) { TNode* temp = q.front(); q.pop(); cout << temp->_val << ' '; //从队列中弹出当前节点并输出值后，将以当前节点为根节点的树的左右子树入队 //若当前节点为空（深度已经大于叶子节点），则不入队 if (temp->_left != NULL) q.push(temp->_left); if (temp->_right != NULL) q.push(temp->_right); } } Tree::Tree() { root_ = Creat(); } Tree::~Tree() { Release(root_); } void Tree::PreOrder() { cout << "前序遍历："; preOrder(root_); cout << endl; } void Tree::InOrder() { cout << "中序遍历："; inOrder(root_); cout << endl; } void Tree::PostOrder() { cout << "后序遍历："; postOrder(root_); cout << endl; } void Tree::LevelOrder() { cout << "层序遍历："; levelOrder(root_); cout << endl; } int main() { //测试数据：A B D # # E # # C F # # G # # Tree t; t.PreOrder(); t.InOrder(); t.PostOrder(); t.LevelOrder(); return 0; }运行结果：
