邻接表存图
int h[N], e[N], ne[N], idx;
void add(int a, int b) //添加一条a->b的有向边
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
//初始化头结点
memset(h, -1, sizeof h);
pat建树的方式 一般给出总结点数量 非叶子结点数量 给出每个非叶子结点的儿子们
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --)
{
int id, k;
cin >> id >> k;
while (k --)
{
int son;
cin >> son;
add(id, son);
}
}
树dfs
/*
1.根结点
2.for循环里dfs下一层
3.叶子结点记得return
*/
int cnt[N], max_depth;
void dfs(int u, int depth) //一个简单的带高度遍历树
{
max_depth = max(depth, max_depth);
if (h[u] == -1) //只有叶子结点才会做的事
{
cnt[depth] ++;
return;
}
for (int i = h[u]; ~i; i = ne[i])
{
//为什么每次选择e[i]作为dfs的下一层 因为e[i]不仅代表结点编号 也达标头结点位置
h[j]代表与j第一个相邻结点的指针
int j = e[i];
dfs(j, depth + 1);
}
}
后序+中序建树
int build(int il, int ir, int pl, int pr) //灵活性很大 也可以带高度什么啊更新数据
{
int root = post[pr];
int k = pos[root];
if (il < k) l[root] = build(il, k - 1, pl, pl + (k - 1 - il));
if (ir > k) r[root] = build(k + 1, ir, pl + (k - 1 - il) + 1, pr - 1);
return root;
}
for (int i = 0; i < n; i ++) cin >> post[i];
for (int i = 0; i < n; i ++)
{
cin >> in[i];
pos[in[i]] = i; //哈希表存储位置
}
BFS
/*
bfs念经 while 队列不空 取出队头 判断队头的孩子是否存在 存在就入队 结束
*/
int q[N];
void bfs(int root)
{
int hh = 0, tt = -1;
q[++ tt] = root;
while (hh <= tt) //队列不空
{
auto t = q[hh ++]; //取出队头元素
if (l.count(t)) q[++ tt] = l[t]; //左孩子入队
if (r.count(t)) q[++ tt] = r[t]; //右孩子入队
}
//你会惊奇的发现 q数组里存的就是层次遍历的序列
cout << q[0];
for (int i = 1; i < n; i ++) cout << ' ' << q[i];
cout << endl;
}
*/
并查集判断连通块
/*
并查集 一开始是k个结点k个连通块 每合并一次k –- 最后如果k != 1说明有多个连通块
*/
int p[N];
int find(int x) //核心操作
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
//并查集初始化
for (int i = 1; i <= n; i ++) p[i] = i;
//合并操作
int k = n;
for (int i = 0; i < n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
int pa = find(a), pb = find(b);
if (pa != pb)
{
p[pa] = pb;
k --;
}
}
无向边dfs一定要用st数组标记是否访问过 不然会无限递归
/*
多次dfs要把st数组清0
*/
void dfs(int u, int depth, int& max_depth)
{
max_depth = max(depth, max_depth);
st[u] = true; //一般进入本层dfs的时候就打个标记
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j, depth + 1, max_depth);
}
}
二叉搜索树
/*
二叉搜索树的中序遍历序列是所有序列从小到大排序
左子树小于根 右子树大于等于根 所以找根结点位置从左往右找到第一个满足的点即可 后面重复就不管了
镜像后 左子树大于等于根 右子树小于根 找的时候就从右往左找到第一个满足的即可
镜像记得reverse中序序列-从大到小了
*/
能返回是否成功建树的模板
bool build(int il, int ir, int pl, int pr, int type)
{
if (il > ir) return true; //判错的时候加了一层虚拟叶子层
int root = preorder[pl];
int k;
if (type == 0)
{
for (k = il; k <= ir; k ++ )
if (inorder[k] == root)
break;
if (k > ir) return false; //没找到根结点的时候gg
}
else
{
for (k = ir; k >= il; k -- )
if (inorder[k] == root)
break;
if (k < il) return false; //没找到根结点的时候gg
}
bool res = true;
bool lres = build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), type);
bool rres = build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, type);
//只有左右子树同时返回正确时候 本次才OK
//成功的时候就是叶子结点不断返回true的时候
if (!lres || !rres) res = false;
postorder[cnt ++] = root; //此处也是反映了后序遍历序列的操作 记住
return res;
}
完全二叉树
/*
用数组下标存从1开始
编号为x的下标的左孩子下标是2 * x, 右孩子下标是2 * x + 1
下标对应的权值开另一个数组来存
*/
//中序遍历完全二叉树 顺便中序序列的值赋值给对应数组的下标
//其实这个顺序理解不是很会 但二叉树遍历容易啊 就那几种顺序 换着写就好了
void dfs(int u)
{
if (u * 2 <= n) dfs(u * 2); //左
w[u] = in[cnt ++]; //根
if (u * 2 + 1 <= n) dfs(u * 2 + 1); //右
}
在栈中 push是前序遍历 pop是中序遍历
/*栈*/
stack<int> s;
s.top(); //栈顶
s.push(); //栈顶插入元素
s.pop(); //栈顶弹出元素
题型 给二叉搜索树形态和要插入的值构建树
/*
和完全二叉树+二叉搜索树的思想一样
对形态树进行中序遍历 沿途过程中访问的下标对应到中序序列的值里
*/
void dfs(int u)
{
if (l.count(u)) dfs(l[u]);
w[u] = in[cnt ++];
if (r.count(u)) dfs(r[u]);
}
/*
BFS这种树的话 bfs的是下标 输出的是对应下标的权值哦
*/
int q[N];
void bfs(int u)
{
int hh = 0, tt = -1;
q[++ tt] = u;
while (hh <= tt)
{
auto t = q[hh ++];
if (l.count(t)) q[++ tt] = l[t];
if (r.count(t)) q[++ tt] = r[t];
}
cout << w[q[0]];
for (int i = 1; i < n; i ++) cout << ' ' << w[q[i]];
cout << endl;
}
翻转二叉树
/*
可以建树的时候就反着建
*/
//技巧 判断根结点可以开个has_father的bool数组
bool has_father[N];
for (int i = 0; i < n; i ++)
{
string a, b;
cin >> a >> b;
if (a[0] != '-')
{
r[i] = stoi(a);
has_father[r[i]] = true;
}
if (b[0] != '-')
{
l[i] = stoi(b);
has_father[l[i]] = true;
}
}
int root;
for (root = 0; root < n; root ++) if (has_father[root] == false) break;
判断是否是完全二叉树
/*
k是想象的下标 根结点从1开始 在里面更新最大的下标编号
左子树 k * 2 右子树 k * 2 + 1
最后max_n如果等于n就是完全二叉树
递归过程中顺便把下标对应的权值存起来
*/
void dfs(int u, int k, int& max_n)
{
max_n = max(k, max_n);
w[k] = u;
if (l.count(u)) dfs(l[u], k * 2, max_n);
if (r.count(u)) dfs(r[u], k * 2 + 1, max_n);
}
从空开始按照给定序列建立二叉搜索树!!!!
/*
经典模板 谨记
建立后的树l,r如果为0则代表该结点是叶子结点
*/
int w[N], idx = 0;
void insert(int x, int& u)
{
if (!u) // u是0 表示这个位置可以插
{
u = ++ idx;
w[u] = x; //将要插入的值赋值给对应下标呀
return;
}
//此时lu和u已经无关了 保证的是如果lu为0的话
//从上往下已经是定好的东西了 不然就不会到最底层的递归层
//insert里的u一旦变化 比如 从上一层传进来的是l[4] 本层 u变成5 则 l[4] = 5
else if (x <= w[u]) insert(x, l[u]);
else insert(x, r[u]);
}
cin >> n;
int root = 0; //此处也关键 第一次插入后 root就永远变成1了
for (int i = 0; i < n; i ++)
{
int x;
cin >> x;
insert(x, root);
}
前序+后序遍历 –爆搜区间范围–很难总结 看题吧 里面用vector引用传回子树的遍历序列
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 40;
int pre[N], post[N];
int n;
int build(int l1, int r1, int l2, int r2, vector<int>& in)
{
if (l1 > r1) return 1;
if (pre[l1] != post[r2]) return 0;
int root = pre[l1];
int res = 0;
//遍历左区间的长度 从0到r1 - l1
for (int i = 0; i <= r1 - l1; i ++)
{
vector<int> lin, rin;
int lres = build(l1 + 1, i + l1 , l2, l2 + i - 1, lin);
int rres = build(i + l1 + 1, r1, l2 + i, r2 - 1, rin);
if (lres * rres != 0)
{
res += lres * rres;
in.clear();
in.insert(in.end(), lin.begin(), lin.end());
in.push_back(root);
in.insert(in.end(), rin.begin(), rin.end());
if (res >= 2) return res;
}
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++) cin >> pre[i];
for (int i = 0; i < n; i ++) cin >> post[i];
vector<int> in;
int res = build(0, n - 1, 0, n - 1, in);
if (res == 1) puts("Yes");
else puts("No");
cout << in[0];
for (int i = 1; i < in.size(); i ++) cout << ' ' << in[i];
cout << endl;
return 0;
}
z字形遍历二叉树–这个题可以学到一个思想 可以每次固定的按层搜索
int q[N];
void bfs(int root)
{
int hh = 0, tt = -1;
q[++ tt] = root;
int step = 1;
while (hh <= tt)
{
int left = hh, right = tt;
//本层结点的使命就是把下一层结点加进来 使命结束后就可以在下面reverse了
//本层结点结束于right
while (hh <= right)
{
auto t = q[hh ++];
if (l.count(t)) q[++ tt] = l[t];
if (r.count(t)) q[++ tt] = r[t];
}
if (step % 2 == 1) reverse(q + left, q + right + 1);
step ++;
}
cout << q[0];
for (int i = 1; i < n; i ++) cout << ' ' << q[i];
cout << endl;
}
前序+中序建树
void build(int il, int ir, int pl, int pr)
{
int root = pre[pl];
int k = pos[root];
if (il < k) build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il));
if (k < ir) build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr);
post[cnt ++] = root;
}
BIG boss avl树 –知识点很多 尽量写注释了
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 30;
int l[N], r[N], v[N], idx;
int h[N];
int n;
void update(int u)
{
h[u] = max(h[l[u]], h[r[u]]) + 1;
}
// //右旋 根结点
void R(int& u)
{
int temp = l[u];
l[u] = r[temp], r[temp] = u;
update(temp), update(u);
u = temp;
}
//对称于左旋的操作
void L(int& u)
{
int temp = r[u];
r[u] = l[temp], l[temp] = u;
//int x = u;
//u = temp;
//update(temp), update(x); //为什么先更新高度再更新根节点呢
//最终我们想得到的是新根的高度吧
//如果先把根重置 那么老根的高度就没更新啦 只有新根的高度是对的
update(temp), update(u);
u = temp;
}
//获得u节点的平衡因子
int get_balance(int u)
{
return h[l[u]] - h[r[u]];
}
//理解就是只会沿着这一条路结束
void insert(int& u, int w)
{
//最后插入的结点的高度也会更新的
//插入完成的时候就往上递归了 更新这一条路的所有高度 其他路的高度不会弄弄
//但不要忘了返回的时候执行的update函数会进行+1操作
if (!u)
{
u = ++ idx;
v[u] = w;
update(u);
return; //如果你要在最后这个地方return 记得先更新一下高度哦
}
//必然不是在插入的结点进行左旋或者右旋的调整操作
else if (w < v[u]) // 你居然在这里出错!!!!!!!
{
insert(l[u], w);
//插入后开始返回啦
if (get_balance(u) == 2)
{
if (get_balance(l[u]) == 1) R(u); //LL
else if (get_balance(l[u]) == -1) L(l[u]), R(u); //LR
}
}
else
{
insert(r[u], w);
if (get_balance(u) == -2)
{
if (get_balance(r[u]) == -1) L(u); //RR
else if (get_balance(r[u]) == 1) R(r[u]), L(u); //RL
}
}
update(u); //从最底部开始一直往上更新 递归路径就是树的插入路径
return;
}
int main()
{
cin >> n;
int root = 0;
for (int i = 0; i < n; i ++)
{
int w;
cin >> w;
insert(root, w);
}
cout << v[root] << endl;
return 0;
}
红黑树 这个题给人的提示就是找根结点 勿局限于绝对值 我们要找到k的坐标即可 返回的根结点还是可以是原数
#include <bits/stdc++.h>
using namespace std;
const int N = 40;
int pre[N], in[N];
unordered_map<int, int> pos;
int n, m;
bool ans;
int build(int il, int ir, int pl, int pr, int& s)
{
int root = pre[pl]; //根结点还是原来的数
int k = pos[abs(root)]; //找位置的时候要带绝对值
if (k < il || k > ir) //找不到的情况 写简洁一点 不要用什么傻逼vector了
{
ans = false;
return -1;
}
int lroot = 0, rroot = 0; // 递归返回左右子树的路径黑结点数量
int ls = 0, rs = 0;
if (il < k)
{
lroot = build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), ls);
}
if (k < ir)
{
rroot = build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, rs);
}
if (root < 0 && (lroot < 0 || rroot < 0))
{
ans = false;
}
if (ls != rs) ans = false;
if (root > 0) s = ls + 1;
else s = ls;
return root;
}
int main()
{
cin >> m;
while (m --)
{
cin >> n;
pos.clear();
for (int i = 0; i < n; i ++)
{
int x;
cin >> x;
pre[i] = x;
in[i] = abs(x);
}
sort(in, in + n);
for (int i = 0; i < n; i ++) pos[in[i]] = i;
ans = true;
int s;
int root = build(0, n - 1, 0, n - 1, s);
if (root < 0) ans = false;
if (ans) puts("Yes");
else puts("No");
}
return 0;
}
等重路径搜索
/*
这是一种新模式 利用vecot<int> path 与 vector<vector<int>> res; 经典dfs
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5500;
int h[N], e[N], ne[N], w[N], idx;
int n, m, s;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
vector<int> path;
vector<vector<int>> res;
void dfs(int u, int sum)
{
if (h[u] == -1)
{
if (sum == s) res.push_back(path);
return;
}
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
path.push_back(w[j]);
dfs(j, sum + w[j]);
path.pop_back();
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> s;
for (int i = 0; i < n; i ++) cin >> w[i];
while (m --)
{
int id, k;
cin >> id >> k;
while (k --)
{
int son;
cin >> son;
add(id, son);
}
}
path.push_back(w[0]);
dfs(0, w[0]);
sort(res.begin(), res.end(), greater<vector<int>>());
for (int i = 0; i < res.size(); i ++)
{
auto& t = res[i];
cout << t[0];
for (int j = 1; j < t.size(); j ++) cout << ' ' << t[j];
cout << endl;
}
return 0;
}
找最大最小值 活用堆 这样会方便很多的
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int h[N], e[N], ne[N], idx;
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
priority_queue<pair<int, int>> heap; //结点数 层数 //大根堆
unordered_map<int, int> l;
void dfs(int u, int depth)
{
l[depth] ++;
heap.push({l[depth], depth});
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j, depth + 1);
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --)
{
int id, k;
cin >> id >> k;
while (k --)
{
int son;
cin >> son;
add(id, son);
}
}
dfs(1, 1);
cout << heap.top().first << ' ' << heap.top().second << endl;
return 0;
}
三个销售额的题-dfs找出叶子结点的深度 根据题意求该求的东西就好了 记得英文里看清题意
堆路径
/*
堆是一个完全二叉树 题要求右左根的顺序 dfs的时候改变一下就好了
至于大小根堆的情况 可以在dfs上下层的时候顺便判断一下
*/
vector<int> path;
bool lt, gt;
void dfs(int k)
{
//叶子结点
if (k * 2 > n)
{
cout << path[0];
for (int i = 1; i < path.size(); i ++) cout << ' ' << path[i];
cout << endl;
}
if (k * 2 + 1 <= n)
{
if (w[k * 2 + 1] < w[k]) gt = true;
else lt = true;
path.push_back(w[k * 2 + 1]);
dfs(k * 2 + 1);
path.pop_back();
}
if (k * 2 <= n)
{
if (w[k * 2] < w[k]) gt = true;
else lt = true;
path.push_back(w[k * 2]);
dfs(k * 2);
path.pop_back();
}
}
中缀表达式 注意什么时候加括号 什么时候不加括号 本质还是递归
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 40;
int l[N], r[N], n;
string op[N];
bool has_father[N];
//检查是否为叶子结点
bool check_leaf(int u)
{
if (l[u] == -1 && r[u] == -1) return true;
return false;
}
string dfs(int u)
{
string res, lres, rres;
//叶子结点就不加括号 否则加括号
if (l[u] != -1)
{
lres = dfs(l[u]);
if (check_leaf(l[u])) res = res + lres;
else res = "(" + lres + ")";
}
res = res + op[u];
if (r[u] != -1)
{
rres = dfs(r[u]);
if (check_leaf(r[u])) res = res + rres;
else res = res + "(" + rres + ")";
}
return res;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
int a, b;
cin >> op[i] >> a >> b;
l[i] = a, r[i] = b;
if (a != -1) has_father[a] = true;
if (b != -1) has_father[b] = true;
}
int root;
for (root = 1; root <= n; root ++) if (!has_father[root]) break;
cout << dfs(root) << endl;
}
最低公众祖先
/*
一个模板吧
*/
while (level[x] != level[y])
{
if (level[x] > level[y]) x = p[x];
else y = p[y];
}
//cout << x << ' ' << y << endl;
while (x != y)
{
x = p[x];
y = p[y];
}
/*
离散化映射 哈希表虽然也是o(1)的时间复杂度 但是哈希表的话还是比较的慢比起数组的o(1) 将各数映射到0~n-1
注意两点就好了 互相之间要存对应关系 方便查回
*/
for (int i = 0; i < n; i ++)
{
cin >> pre[i];
in[i] = pre[i];
}
sort(in, in + n);
//解决中序映射 很简单
for (int i = 0; i < n; i ++)
{
pos[in[i]] = i; //将中序的数映射到下标
seq[i] = in[i];
in[i] = i;
}
for (int i = 0; i < n; i ++)
{
pre[i] = pos[pre[i]]; //将下标拿回来
}