二叉树的遍历
二叉树的遍历是指通过一定顺序访问二叉树的所有结点。遍历方法一般有四种：先序遍历、中序遍历、后序遍历、层序遍历，其中，前三种一般使用深度优先所搜（DFS）实现，而层序遍历一般使用广度优先搜索 （BFS）实现。
1、先序遍历的实现：
void preOrder(node* root){
if(root == NULL){ //递归边界
return;
}
printf("%d\n", root->data); //访问根结点，例如将其数据域输出
preOrder(root->lchild); //访问左子树
preOrder(root->rchild); //访问右子树
}
2、中序遍历的实现：
void inOrder(node* root){
if(root == NULL){ //递归边界
return;
}
inOrder(root->lchild); //访问左子树
printf("%d\n", root->data); //访问根结点，例如将其数据域输出
inOrder(root->rchild); //访问右子树
}
3、后序遍历的实现：
void postOrder(node* root){
if(root == NULL){ //递归边界
return;
}
postOrder(root->lchild); //访问左子树
postOrder(root->rchild); //访问右子树
printf("%d\n", root->data); //访问根结点，例如将其数据域输出
}
4、层序遍历的实现：
void layerOrder(node* root){
queue<node*> q; //注意队列中存的是地址
q.push(root); //将根结点地址入队
while(!q.empty()){
node* now = q.front(); //取出队首元素
q.pop();
printf("%d", now->data); //访问队首元素
if(now->lchild != NULL){ //左子树非空
q.push(now->lchild);
}
if(now->rchild != NULL){ //右子树非空
q.push(now->rchild);
}
}
}
