二叉树遍历攻略：前中后序与层序

之前讲过树分为许多种类，二叉树就是其中之一。二叉树指的是树的分支最多只有两支的特殊类型。而且二叉树是有序树，他的左右孩子不能颠倒！。

二叉树又有完全二叉树和满二叉树，满二叉树指的是二叉树的所有层数的分支都存在，完全二叉树指的是由1到N的编号的节点对应的1到N的节点的值是一 一对应的。在完全二叉树中

父节点的编号=他的孩子节点的编号*2；

左孩子节点的编号=他的父节点的编号/2；

右孩子节点的编号=他的父节点的编号/2+1；

二叉树的既然是树的种类之一，所以也可以用vector数组和链式前向星进行存储。如果用顺序存储，若不是完全二叉树，就需要额外开辟空间，所以一般采用链式存储，也只演示链式存储的代码：

#include <iostream> using namespace std; const int N = 1e6 + 10; int l[N], r[N]; int n; int main() { cin >> n; for (int i = 1; i < n; i++) { cin >> l[i] >> r[i]; } return 0; }

二叉树的深度优先遍历分为前序遍历，中序遍历，后序遍历。前序遍历指的是遍历 根 左 右节点的顺序，中序遍历指的是遍历 左 根 右节点的顺序，后续遍历指的是遍历左 右 根节点的顺序。

#include <iostream> using namespace std; const int N = 1e6 + 10; int l[N], r[N]; int n; void dfs1(int u)//前序遍历 { if (u == 0) { return; } cout << u << " "; dfs1(l[u]); dfs1(r[u]); } void dfs2(int u)//中序遍历 { if (u == 0) { return; } dfs2(l[u]); cout << u << " "; dfs2(r[u]); } void dfs3(int u)//后序遍历 { if (u == 0) { return; } dfs3(l[u]); dfs3(r[u]); cout << u << " "; } int main() { cin >> n; for (int i = 1; i < n; i++) { cin >> l[i] >> r[i]; } dfs1(1); dfs2(2); dfs3(3); return 0; }

二叉树的宽度优先遍历与树的相同，也是运用queue的方式来遍历：

#include <iostream> #include <queue> using namespace std; const int N = 1e6 + 10; int l[N], r[N]; int n; void bfs() { queue<int>q; q.push(1); while (q.size()) { int u = q.front(); q.pop(); cout << u << " "; if (l[u]) { q.push(l[u]); } if (r[u]) { q.push(r[u]); } } } int main() { cin >> n; for (int i = 1; i < n; i++) { cin >> l[i] >> r[i]; } bfs(); return 0; }

由此二叉树的基本操作已完结，待我后续学习再与大家分享