算法基础——二叉树

一、⼆叉树的概念

1. 二叉树的定义 

注意：⼆叉树结点的两个孩⼦，⼀个被称为左孩⼦，⼀个被称为右孩⼦。其顺序是固定的，就像⼈ 的左⼿和右⼿，不能颠倒混淆。

2. 特殊的⼆叉树

（1）满⼆叉树

（2）完全⼆叉树

        对⼀棵树有 个结点的⼆叉树按层序编号，所有的结点的编号从 样深度的满⼆叉树的编号为从 1 ∼n 1 ∼n 。如果这棵树所有结点和同 比特就业课 的结点位置相同，则这棵⼆叉树为完全⼆叉树。 

注意：要从后往前依次删除！！！ 

二、⼆叉树的存储

1. 顺序存储 

2. 链式存储

输⼊描述：

#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++){cin >> l[i] >> r[i];}return 0;
}

三、 ⼆叉树的遍历

1. 深度优先遍历 

案例：

题⽬描述：

有⼀个 n(n ≤ 10^6 ) 个结点的⼆叉树。给出每个结点的两个⼦结点编号（均不超过 n ），建⽴⼀棵⼆叉树（根节点的编号为1 ），如果是叶⼦结点，则输⼊ 0 0。

输⼊描述：

第⼀⾏⼀个整数 n ，表⽰结点数。之后 n ⾏，第 i ⾏两个整数 l 、 r ，分别表⽰结点 i 的左右⼦结点编号。若 l = 0m则表⽰⽆左⼦结点， r = 0 同理。

测试⼀：40 23 40 00 0
测试⼆：22 00 0
测试三：32 30 00 0
测试四：72 30 45 60 00 07 00 0

代码实现：

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

2. 宽度优先遍历

        这个就和常规的树的遍历⽅式⼀样，直接⽤队列帮助层序遍历即可。

#include <iostream>
#include <queue>using namespace std;const int N = 1e6 + 10;int n;
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()
{cin >> n;for(int i = 1; i <= n; i++){cin >> l[i] >> r[i];}bfs();return 0;
}