C++算法
二叉树概念、存储结构与遍历算法详解
二叉树是一种每个结点至多有两个子树的树型结构，包含满二叉树和完全二叉树等特殊形式。存储方式涵盖适合完全二叉树的顺序存储和通用的链式存储。遍历算法包括深度优先（先序、中序、后序）和宽度优先（层序），可通过递归或队列实现。文中提供相关 C++ 代码示例以辅助理解。
二叉树是一种每个结点至多有两个子树的树型结构，包含满二叉树和完全二叉树等特殊形式。存储方式涵盖适合完全二叉树的顺序存储和通用的链式存储。遍历算法包括深度优先（先序、中序、后序）和宽度优先（层序），可通过递归或队列实现。文中提供相关 C++ 代码示例以辅助理解。
二叉树是一种特殊的树型结构，它的特点是每个结点至多只有 2 棵子树（即二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。注意这里是最多有两个孩子，也可能没有孩子或者是只有一个孩子。
注：二叉树结点的两个孩子，一个被称为左孩子，一个被称为右孩子。其顺序是固定的，就像人的左手和右手，不能颠倒混淆。
一棵二叉树的所有非叶子节点都存在左右孩子并且所有叶子节点都在同一层上，那么这棵树就称为满二叉树。
对一棵树有 n 个结点的二叉树按层序编号，所有的结点的编号从 1~n。如果这棵树所有结点和同样深度的满二叉树的编号为从 1∼n 的结点位置相同，这棵二叉树为完全二叉树，实际上就是在满二叉树的基础上，在最后一层的叶子结点上，从右往左依次删除若干个结点，剩下的就是一棵完全二叉树。
在之前已经学过树的存储，二叉树也是树，也是可以用 vector 数组或者链式前向星来存储。仅需在存储的过程中标记谁是左孩子，谁是右孩子即可。
在完全二叉树以及满二叉树的性质那里，我们了解到：如果从根节点出发，按照层序遍历的顺序，由开始编号，那么父子之间的编号是可以计算出来的。那么在存储完全二叉树的时候，就按照编号，依次放在数组对应下标的位置上，然后通过计算找到左右孩子和父亲：设节点下标为 i。
如果不是完全二叉树，也是可以用顺序存储。但是首先要先把这棵二叉树补成完全二叉树，然后再去编号。不然就无法通过计算找到左右孩子和父亲的编号。
辨析：可以看到我们的二叉树其实只有 6 个节点，但是顺序存储却要分配 10 个空间，其中有 4 个空间都被浪费掉了。
如下图我们考虑一种极端的情况，一棵树右斜树，它只有 4 个节点，但是需要分配 2^4 - 1 个存储单元，这显然会对存储空间造成很大的浪费。所以，顺序存储结构一般只用于完全二叉树或满二叉树。
可以创建两个数组 l[N]，r[N]，其中 l[i] 表示结点号为 i 的结点的左孩子编号，r[i] 表示结点号为 i 的结点的右孩子编号。
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int l[N], r[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
// 存下 i 号结点的左右孩子
cin >> l[i] >> r[i];
}
return 0;
}
不同于常规树的深度优先遍历，二叉树因其独特的性质可以划分成三种深度优先遍历：先序遍历，中序遍历，和后序遍历。其中，三种遍历方式的不同在于处理根节点的时机。
对于一棵二叉树而言，整体可以划分成三部分：根节点 + 左子树 + 右子树：
// 先序遍历
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 << " "; // 根
}
测试：
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[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(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> l[i] >> r[i];
}
// dfs1(1); // 先序遍历
// dfs2(1); // 中序遍历
dfs3(1); // 后序遍历
return 0;
}
这个就和常规的树的遍历方式一样，直接用队列帮助层序遍历即可。
#include<iostream>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[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(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
bfs();
return 0;
}
运行结果：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online