本文主要介绍二叉树的前中后序遍历的递归实现，递归实现比较简单，很多关于二叉树的实现都可以用递归，非递归实现准备用另一篇文章介绍，前序、中序、后序的遍历顺序体现的是访问根节点的顺序，前序就是先访问根节点，然后左子树，最后右子树。而中序则先访问左子树，然后访问根节点，最后访问右子树。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x),left(NULL),right(NULL){}
};
//创建二叉树
void CreateTree(TreeNode* &root)
{
int data;
cin >> data;
if(-1 == data)
{
root =NULL;
}
else
{
root = new TreeNode(data);
CreateTree(root->left);
CreateTree(root->right);
}
}
//递归前序
void PreOrder(TreeNode *root)
{
if(root)
{
cout << root->val;
if(root->left) PreOrder(root->left);
if(root->right) PreOrder(root->right);
}
}
//递归中序
void MidOrder(TreeNode *root)
{
if(root)
{
if(root->left) MidOrder(root->left);
cout << root->val;
if(root->right) MidOrder(root->right);
}
}
//递归后序
void PostOrder(TreeNode *root)
{
if(root)
{
if(root->left) PostOrder(root->left);
if(root->right) PostOrder(root->right);
cout << root->val;
}
}
//队列实现层遍历
void levelOrder(TreeNode *root)
{
if(NULL == root) return;
queue <TreeNode *> que;
que.push(root);
while(!que.empty())
{
TreeNode *node = que.front();
cout << node->val;
que.pop();
if(node->left)
{
que.push(node->left);
}
if(node->right)
{
que.push(node->right);
}
}
}
int main()
{
TreeNode *root =NULL;
CreateTree(root);
cout<<endl;
PreOrder(root);
cout<<endl;
MidOrder(root);
cout<<endl;
PostOrder(root);
cout<<endl;
levelOrder(root);
getchar();
}