二叉树的遍历是通过一定顺序访问二叉树的所有结点。
遍历方法一般有四种：先序遍历、中序遍历、后序遍历及层次遍历，其中，前三种一般使用深度优先搜索（DFS）实现，而层次遍历一般用广度优先搜索（BFS）实现。
先序遍历
遍历顺序：根结点—>左子树—>右子树
需要两大件：递归式和递归边界
递归式：先序遍历的定义可得，即先访问根结点，再递归访问左子树，最后递归访问右子树
递归边界：二叉树是一棵空树，即在递归访问子树时，如果碰到子树为空，那么就说明到达了死胡同
void preorder(node* root) {
if(root == NULL) {
return ; //到达空树，递归边界
}
//访问根结点root，例如将其数据域输出
printf("%d\n", root->data);
//访问左子树
preorder(root->left);
//访问右子树
preorder(root->right);
}
性质：对一棵二叉树的先序遍历序列，序列的第一个一定是根结点。
中序遍历
遍历顺序：左子树—>根结点—>右子树
其递归式由中须遍历的性质可得，递归边界同先序遍历
void inorder(node* root) {
if(root == NULL) {
return ; //到达空树，递归边界
}
//访问左子树
preorder(root->left);
//访问根结点root，例如将其数据域输出
printf("%d\n", root->data);
//访问右子树
preorder(root->right);
}
性质：只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左子树和右子树
后序遍历
遍历顺序：左子树—>右子树—>根结点
其递归式由后须遍历的性质可得，递归边界同先序遍历
void postorder(node* root) {
if(root == NULL) {
return ; //到达空树，递归边界
}
//访问左子树
preorder(root->left);
//访问根结点root，例如将其数据域输出
preorder(root->right);
//访问右子树
printf("%d\n", root->data);
}
性质：对后序遍历序列来说，序列的最后一个一定是根结点
注意：无论是先序遍历序列还是后序遍历序列，都必须知道中序遍历序列才能唯一地确定一棵树。
因为通过先序遍历序列和后序遍历序列都只能得到根结点，而只有通过中序遍历才能利用根结点把左右子树分开，从而递归生成一棵二叉树。该方法需要保证所有元素都不相同时才能使用。
层次遍历
层次遍历是指按层次的顺序从根结点向下逐层进行遍历，且对同一层的结点为从左到右遍历。
层次遍历就相当于对二叉树从根结点开始的广度优先搜索。
基本思路：
- 将根结点root加入队列q
- 取出队首结点，访问它
- 如果该结点由左孩子，将左孩子入队
- 如果该结点有右孩子，将右孩子入队
- 返回2，直到队列为空
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); //右子树非空
}
}
注意：这里使用的是node* 而不是node型，同广度优先搜索一样，队列中保存的知识原元素的一个副本，如果队列中直接放node型，当需要修改队首元素时，就会无法对原元素进行修改（即只修改了队列中的副本），故存放node型变量的地址，也就是node* 型变量，这样就可以通过访问地址去修改原元素，就不会有问题了。
这里的node定义徐娅多加一个变量来记录层次layer。
struct node {
int data; //数据域
int layer; //层次
node* lchild; //左指针域
node* rchild; //右指针域
};
void LayerOrder(node* root) {
queue<node*> q; //注意队列里是存地址
root->layer = 1; //根结点的层号为1
q.push(root); //将根结点地址入队
while(!q.empty()) {
node* now = q.front(); //取出队首元素
q.pop();
printf("%d", now->data); //访问队首元素
if(now->lchild != NULL) { //左子树非空
now->lchild->layer = now->lchild + 1;
q.push(now->lchild);
}
if(now->rchild != NULL) { //右子树非空
now->rchild->layer = now->lchild + 1;
q.push(now->rchild);
}
}
}
实例：
给定一棵二叉树的先序遍历序列和中序遍历序列，重建这棵二叉树
分析：
先序序列的第一个元素pre1是当前二叉树的根结点。再由中序序列的性质可知，当前二叉树的根结点将中序序列划分为左子树和右子树。因此，要做的就是在中序序列中找到某个结点ink，使得ink == pre1，这样就在中序序列中找到了根结点。易知左子树的结点个数numLeft = k - 1。于是，左子树的先序序列区间就是[2, k]，左子树的中序序列区间[1, k - 1]；右子树的先序序列区间是[k + 1, n]，右子树的中序序列区间是[k + 1, n]，接着只需要往左子树和右子树进行递归构建二叉树即可。
只要先序序列的长度小于等于0时，当前二叉树就不存在了，于是就能以这个条件作为递归边界。
node* Create(int preL, int preR, int inL, int inR) {
if(preL > preR) {
return NULL; //先序序列长度小于等于0时，直接返回
}
node* root = new node; //新建一个结点，用来存放当前二叉树的根结点
root->data = pre[preL]; //新结点的数据域为根结点的值
int k;
for(k = inL; k <= inR; k++) {
if(in[k] == pre[preL]) { //在中序序列中找到in[k[ == pre[L]的结点
break;
}
}
int numLeft = k - inL; //左子树的结点个数
//左子树的先序区间为[preL + 1, preL + numLeft],中序区间为[inL, k - 1]
//返回左子树的根结点地址，赋值给root的左指针
root->lchild = Create(preL + 1, preL + numLeft, inL, k - 1);
//左子树的先序区间为[preL + numLeft + 1, preR],中序区间为[k + 1, inR]
//返回右子树的根结点地址，赋值给root的右指针
root->rchild = Create(preL + numLeft + 1, preR, k + 1, inR);
return root; //返回根结点地址
}
注意：中序序列可以和先序序列、后序序列、层次序列中任意一个来构建唯一的二叉树，但后三者两两搭配或是三个一起都无法构建唯一的二叉树
实例：
给出一棵二叉树的后序遍历序列和中序遍历序列，求这棵二叉树的层次遍历序列
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 50;
struct node {
int data;
node* lchild;
node* rchild;
};
int pre[maxn], in[maxn], post[maxn]; //先序、中序、后序
int n; //结点个数
//当前二叉树的后序序列区间为[postL, postR], 中序序列区间为[inL, inR]
//create函数返回构建出二叉树的根结点地址
node* create(int postL, int postR, int inL, int inR) {
if(postL > postR) {
return NULL; //后序序列长度小于等于0时，直接返回
}
node* root = new node; //新建一个新的结点，用来存放当前二叉树的根结点
root->data = post[postR]; //因为是倒序，用postR。新结点的数据域为根结点的值
int k;
for(k = inL; k < inR; k++) {
if(in[k] == post[postR]) { //在中序序列中找到in[k] == pre[postR]的结点
break;
}
}
int numLeft = k - inL; //左子树的结点个数
//返回左子树的根结点地址，赋值给root的左指针
root->lchild = create(postL, postL + numLeft - 1, inL, k - 1);
//返回右子树的根结点地址，赋值给root的右指针
root->rchild = create(postL + numLeft, postR - 1, k + 1, inR);
return root; //返回根结点地址
}
int num = 0; //已输出的结点个数
void BFS(node* root) {
queue<node*> q; //注意队列里是存地址
q.push(root); //将根结点地址入队
while(!q.empty()) {
node* now = q.front(); //取出队首元素
q.pop();
printf("%d", now->data); //访问队首元素
num++;
if(num < n) printf(" ");
if(now->lchild != NULL) q.push(now->lchild);
if(now->rchild != NULL) q.push(now->rchild);
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &post[i]);
}
for(int i = 0; i < n; i++) {
scanf("%d", &in[i]);
}
node* root = create(0, n - 1, 0, n - 1); //建树
BFS(root); //层次遍历
return 0;
}
二叉树的静态实现
可以用来更好理解前面的内容，如不能完全使用指针，可以简单使用数组来完成二叉树的上面所有操作
所谓的静态二叉链表是指，结点的左右指针域使用int型代替，用来表示左右子树的根结点在数组中的下标。为此需要建立一个大小为结点上限个数的node型数组，所有动态生成的结点都直接使用数组中的结点，所有对指针的操作都改为对数组下标的访问。
struct node {
typename data; //数据域
int lchild; //指向左子树的指针域
int rchild; //指向右子树的指针域
}Node[maxn];
int index = 0;
int newNode(int v) { //分配一个Node数组中的结点给新的结点，index为下标
Node[index].data = v; //数据域为v
Node[index].lchild = -1; //以-1或maxn表示空，因为数组范围是0~maxn-1
Node[index].rchild = -1;
return index++;
}
//查找，root为根结点在数组中的下标
void search(int root, int x, int newdata) {
if(root == -1) { //用-1来代替NULL
return; //空树，死胡同（递归边界）
}
if(Node[root].data == x) { //找到数据域为x的结点，把它修改成newdata
Node[root].data = newdata;
}
search(Node[root].lchild, x, newdata); //往左子树搜索x（递归式）
search(Node[root].rchild, x, newdata); //往右子树搜索x（递归式）
}
//插入，root为根结点在数组中的下标
void insert(int &root, int x) { //记得加引号
if(root == -1) { //空树，说明查找失败，也即插入位置（递归边界）
root = newNode(x); //给root赋以新的结点
}
if(由二叉树的性质x应该插在左子树) {
insert(Node[root].lchild, x); //往左子树搜索（递归式）
} else {
insert(Node[root].rchild, x); //往右子树搜索（递归式）
}
}
//二叉树的建立
int Create(int data[], int n) {
int root = -1; //新建根结点
for(int i = 0; i < n; i++) {
insert(root, data[i]); //将data[0]~data[n-1]插入二叉树中
}
return root; //返回二叉树的根结点下标
}
//先序遍历
void preorder(int root) {
if(root == -1) {
return; //到达空树，递归边界
}
//访问根结点root,例如将其数据域输出
printf("%d\n", Node[root].data);
//访问左子树
preorder(Node[root].lchild);
//访问右子树
preorder(Node[root].rchild);
}
//中序遍历
void inorder(int root) {
if(root == -1) {
return; //到达空树，递归边界
}
//访问左子树
inorder(Node[root].lchild);
//访问根结点root,例如将其数据域输出
printf("%d\n", Node[root].data);
//访问右子树
inorder(Node[root].rchild);
}
//先序遍历
void postorder(int root) {
if(root == -1) {
return; //到达空树，递归边界
}
//访问左子树
postorder(Node[root].lchild);
//访问右子树
postorder(Node[root].rchild);
//访问根结点root,例如将其数据域输出
printf("%d\n", Node[root].data);
}
//层次遍历
void LayerOrder(int root) {
queue<int> q; //此处队列存放结点下标
q.push(root); //将根结点地址入队
while(!q.empty()) {
int now = q.front(); //取出队首元素
q.pop();
printf("%d ", Node[now].data);
if(Node[now].lchild != -1) q.push(Node[now].lchild); //左子树非空
if(Node[now].rchild != -1) q.push(Node[now].rchild); //右子树非空
}
}
