输入int类型的01，默认输入1

for(int i=0;~b;i++) 这里的~b为b!=-1

memset(数组名，赋的初值，sizeof 数组名) 初始化数组

单链表

在解决图和树的数据结构问题时，常常用邻接表来存储。邻接表是由很多条单链表构成的，而单链表的实现方式有很多，如数组，结构体，vector等容器实现，在这些实现方式中，静态数组的速度是最快的。
image.png

  • 传统结构体表示链表

    1. struct Node{
    2.   int value;
    3.   Node* next;
    4. }

    每次创建新的链表节点，都需要new一个新的结构体，在竞赛级别的算法题目里，链表的长度都是十万百万级，如果每次创建一个新节点都new一次，光创建出这个链表就已经超时了。

  • 静态数组表示

这里的静态和动态其实是指是否需要重复开辟空间。提前开辟好空间以后用这些空间去表示称为静态，与之对应的每次都需要开辟空间称为动态。

那，如何表示呢？
image.png
e[N], ne[N], head, idx来表示一个单链表！
e[N] 存放每一个节点的值，ne[N]存放下一个节点的下标，head指向头结点，idx表示已经用到了数组中的哪个节点。

  • 具体操作 ```cpp // 初始化 void init() { head = -1; idx = 0; }

// 将x插到头结点 void add_to_head(int x) { e[idx] = x, ne[idx] = head, head = idx ++ ; }

// 将x插到下标是k的点后面 void add(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ; }

// 将下标是k的点后面的点删掉 void remove(int k) { ne[k] = ne[ne[k]]; }

  1. <a name="XApYp"></a>
  2. ### 邻接表
  3. <a name="Vfhyr"></a>
  4. #### 用邻接表表示一棵树
  5. 用idx，h[N]，ne[N]，e[N]表示<br />h[N]用于存放邻接表的表头<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/21844768/1644752203959-99352828-8678-468d-957e-8dacd6222deb.png#clientId=u40621dd4-76a7-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=342&id=ufb408385&margin=%5Bobject%20Object%5D&name=image.png&originHeight=424&originWidth=782&originalType=binary&ratio=1&rotation=0&showTitle=false&size=53922&status=done&style=none&taskId=u4711ee5b-59be-497d-9359-c296498111c&title=&width=630.8571226342106)<br />构建树
  6. ```cpp
  7. add(int parent_id,int child_id){ //为值为parent_id的父节点添加一个值为child_id的子节点
  8.     e[idx] = child_id,ne[idx]=h[parent_id],h[parent_id] = idx++;
  9. }
  • e[]的索引是idx，值是节点中存放的值
  • ne[]的索引是idx，值是下一个节点的idx
  • h[]的索引是节点中存放的值，值是下一个节点的idx

    树的遍历

  1. 前序遍历，中序遍历，后续遍历（DFS）
  • 前序遍历 (preorder) 根左右
  • 中序遍历 (inorder)左跟右
  • 后续遍历 (postorder)左右跟

    倒推—

image.png

  • 前序的第一个是root，后序的最后一个是root。
  • 先确定跟节点，然后根据中序遍历，在根左边的为左子树，根右边的为右子树
  • 对于每一个子树可以看成一个全新的树，仍然遵循上面的规律。

划重点！！根据上面的推论，只要确定了根节点的位置，根据中序遍历我们就能确定左右子树的位置，递归从而构建出整个二叉树。也就是说，我们知道一颗二叉树前序遍历和中序遍历或者后续遍历和中序遍历，就能构建二叉树，而知道前序遍历和后续遍历则不行。

  1. // 一边建树一边遍历
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int N = 50010;
  5. unordered_map<int,int> l,r,pos;
  6. int in[N],pre[N],n;
  7. vector <int> post;
  8. int build(int il,int ir,int pl,int pr){
  9.     int root = pre[pl];
  10.     int k = pos[root];
  11.     if(il<k) l[root] = build(il,k-1,pl+1,pl+1+k-1-il);
  12.     if(k<ir) r[root] = build(k+1,ir,pl+1+k-il,pr);
  13.     // 一边建树 一边遍历
  14.     post.push_back(root);
  15.     return root;
  16. }
  17. int main(){
  18.     cin>>n;
  19.     for(int i=0;i<n;i++){
  20.        cin>>pre[i]; 
  21.     }
  22.     for(int i=0;i<n;i++){
  23.         cin>>in[i];
  24.         pos[in[i]]=i;
  25.     }
  26.     int root=build(0,n-1,0,n-1);
  27.     cout<<post[0];
  28.     return 0;
  29. }
  1. 层序遍历（BFS）
    1. //p存放层序遍历的结果，l存放父节点的左儿子，r存放父节点的右儿子
    2. void bfs(int root){
    3.  p[0] = root;
    4.  int hh=0,kk=0;
    5.  while(hh<=kk){
    6.      int t = p[hh++];
    7.      if(l.count(t)) p[++kk] = l[t];
    8.      if(r.count(t)) p[++kk] = r[t];
    9.  }
    10.  cout<<p[0];
    11.  for(int i=1;i<n;i++) cout<<' '<<p[i];
    12. }

    并查集

  • 并查集有思维巧妙，代码简短的特点，是面试热点问题。

    简单描述一下并查集

现在有两个集合a和b，从这两个集合中取出任意一个元素，如何判断该元素属于哪个集合？以及如何快速将两个集合合并？
—常见思路—
定义一个belong[]数组存储元素归属

  1. if(belong[x]=='a') puts('a');
  2. else puts('b');

定义数组操作，查询元素归属的时间复杂度是O(1)；但合并两个操作呢？
只能在定义一个新的数组，然后把每个集合中的元素都存进去，时间复杂度为O(n)！
有没有什么办法实现这两个操作且时间复杂度低？
并查集可以在近乎O(1)的时间复杂度下实现这两个操作!!

  • 将集合中的元素存在树中，定义一颗树的跟节点为这个集合的id，定义一个数组p[]存取每个元素的父节点, x的父节点是p[x],而根节点的父节点就是其本身，即p[x]=x，所以我们只要一直不断向上查询这个元素的根节点，就能知道归属。
  • 对于合并集合，由于这两个集合是以两颗树的形式存在，我们只要让一颗树的根节点的父节点为另一颗树的根节点，即可把这两颗树连起来。

image.png
代码实现

  • p[]数组存放每个元素的父节点，即x的父节点是p[x]
  • find(int x)：查找某一元素的根节点
  • 判断归属 if( find(a) == find(b) ) 属于同一个集合
  • 合并 p[find(a)] = find(b)
  • 如何实现find()函数 ```cpp //常规思路，由于每次都要while一遍，所以查找根节点的时间复杂度是个问题 int find(int x){ while(p[x]!=x) x = p[x]; return x; }

// 采用路径压缩优化，路径压缩就是在查询根节点的过程中，将路径上的每一个节点的父节点都 //重新设置为根节点，避免重复查找，这样时间复杂度可以近乎缩减为O(1); int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }

  1. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/21844768/1645013585450-ce0a656f-d84c-416a-83b7-a45329a96e15.png#clientId=u43e60836-e9dc-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=575&id=u1bad6c01&margin=%5Bobject%20Object%5D&name=image.png&originHeight=713&originWidth=732&originalType=binary&ratio=1&rotation=0&showTitle=false&size=44839&status=done&style=none&taskId=u25992a16-387c-4dcc-be13-e55491de5a3&title=&width=590.5209894734554)
  2. ```cpp
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. const int N = 100010;
  6. int p[N];
  7. int find(int x) // 返回x的祖宗节点 + 路径压缩
  8. {
  9.     if (p[x] != x) p[x] = find(p[x]);
  10.     return p[x];
  11. }
  12. int main(){
  13.     int n,m;
  14.     cin>>n>>m;
  15.     for(int i=1;i<=n;i++){
  16.         p[i] = i;
  17.     }
  18.     while(m--){
  19.         char ins;
  20.         int a,b;
  21.         cin>>ins>>a>>b;
  22.         if(ins=='M') p[find(a)] = find(b);
  23.         else{
  24.             if(find(a)==find(b)) puts("Yes");
  25.             else puts("No");
  26.         }
  27.     }
  28.     return 0;
  29. }

二叉树

二叉树可以用两个数组 l[N] , r[N] 来表示, N 为节点数量，l[i] 记录节点 i 的左儿子，r[i] 记录节点i的右儿子

二叉树三种深度遍历

  1. // k用来记录当前位置，满足pat空格检测输出
  2. void dfs_pre(int root,int &k){
  3.     if(root == -1) return;
  4.     if(++k == n) cout<<root;
  5.     else cout<<root<<' ';
  6.     dfs_pre(l[root],k);
  7.     dfs_pre(r[root],k);
  8. }
  9. void dfs_in(int root,int &k){
  10.     if(root == -1) return;
  11.     dfs_in(l[root],k);
  12.     if(++k == n) cout<<root;
  13.     else cout<<root<<' ';
  14.     dfs_in(r[root],k);
  15. }
  16. void dfs_post(int root,int &k){
  17.     if(root == -1) return;
  18.     dfs_post(l[root],k);
  19.     dfs_post(r[root],k);
  20.     if(++k == n) cout<<root;
  21.     else cout<<root<<' ';
  22. }

二叉树的广度优先遍历

  1. void bfs(int root){
  2.     q[0] = root;
  3.     int hh=0,tt=0;
  4.     while(hh<=tt){
  5.         int t = q[hh++];
  6.         if(l[t]!=-1) q[++tt] = l[t];
  7.         if(r[t]!=-1) q[++tt] = r[t];
  8.     }
  9. }

二叉搜索树

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
  • 它的左、右子树也分别为二叉搜索树

如果是一棵二叉搜索树，那么其中序遍历必然为一组升序排列的数列！
c++里set容器就是用二叉搜索树实现的

完全二叉树可以用一维数组存储

反转二叉树

image.png

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 11;
  4. int l[N],r[N],q[N],n;
  5. bool has_father[N];
  6. void dfs_re(int root){
  7.     if(root == -1) return;
  8.     dfs_re(l[root]);
  9.     dfs_re(r[root]);
  10.     swap(l[root],r[root]);
  11. }
  12. void bfs(int root){
  13.     q[0] = root;
  14.     int hh=0,tt=0;
  15.     while(hh<=tt){
  16.         int t = q[hh++];
  17.         if(l[t]!=-1) q[++tt] = l[t];
  18.         if(r[t]!=-1) q[++tt] = r[t];
  19.     }
  20.     cout<<root;
  21.     for(int i=1;i<n;i++){
  22.         cout<<' '<<q[i];
  23.     }
  24.     cout<<endl;
  25. }
  26. void dfs_in(int root,int &k){
  27.     if(root == -1) return;
  28.     dfs_in(l[root],k);
  29.     if(++k == n) cout<<root;
  30.     else cout<<root<<' ';
  31.     dfs_in(r[root],k);
  32. }
  33. int main(){
  34.     // 初始化
  35.     memset(r,-1,sizeof r);
  36.     memset(l,-1,sizeof l);
  37.     // 读入数据
  38.     cin>>n;
  39.     for(int i=0;i<n;i++){
  40.         char a,b;
  41.         cin>>a>>b;
  42.         if(a!='-'){
  43.             l[i]=a-'0';
  44.             has_father[l[i]] = true;
  45.         }
  46.         if(b!='-'){
  47.             r[i]=b-'0';
  48.             has_father[r[i]] = true;
  49.         }
  50.     }
  51.     int root = 0;
  52.     // 寻找根节点
  53.     while(has_father[root]) root++;
  54.     // 反转二叉树
  55.     dfs_re(root);
  56.     // 输出层序遍历
  57.     bfs(root);
  58.     // 输出中序遍历
  59.     int k = 0; // 负责记录当前位置来判断是否需要输出空格
  60.     dfs_in(root,k);
  61.     return 0;
  62. }