6 冲刺600道AC，加油~~~

头文件 绝对忘得了，O(∩_∩)O哈哈~

#include<bits/stdc++.h>
using namespace std;
int main(){
    
    return 0;
}

二叉树-基本概念及定义和变体

<1> 指的最大度数只有2的树为二叉树（binary tree简写BT）
<2> 满二叉树：每一层的节点必须是满的 每一层节点数为 2的k(层数)-1次幂 任一左子节点一定为为偶数(2k)、右子节点
 -> 为奇数2k+1
<3> n0 = n2 + 1
<4> 完全二叉树：前n-1层为满二叉树，最后一层从左往右连续
<5> 总节点数：2^n-1 (n是总层数)
<6> 二叉排序树：一个节点的左子节点的所有节点均小于此节点、它的右子节点的所有节点均大于此节点
<7> 平衡二叉树：本质为二叉排序树，添加条件根节点的左右子树深度相差最大为1

------

样例1 (如下 满二叉树)
   O
 /   \
 O   O
/\   /\
OO   OO

样例2 (如下 完全二叉树)
   O
 /   \
 O   O
/\   /
OO   O

树基础

<1> 非线性数据结构 且不存在环
<2> 一棵树至少有一节点 这一节点没有前驱节点 这个节点叫根节点
<3> 子节点、孙节点均为其父节点的后继节点
<4> 孩子节点是子节点（会分左右：左子节点、右子节点，通常用于二叉树）如下图，根节点有三个子结点，他的度为3，
 -> 整个树中度最大的节点的度就是这个树的度
<5> 兄弟节点即为同一层的节点
<6> 定义根节点的层数为1，则从上向下2、3、4、5……进行数数，为树的层数
<7> 编号：从上到下，从左到右
------

样例 (如下)
  O ->根节点
/ | \
O O O ->为根节点的子节点
|
O ->为根节点的孙节点

树的遍历

<-> 共计六种
<1> 先序：根->左->右
<2> 中序：左->根->右
<3> 后序：左->右->根
<4> 层次遍历：从左至右，从上至下
<5> 深度遍历：类似于深度优先搜索
<6> 广度遍历：类似于广度优先搜索 层次遍历pro版/(^o^)/

数据结构

1.栈

// 头文件 : <stack>
// 栈 :  1、先进后出   2、只能从一端进出，另一端封闭
// push   :  往栈里添加一个元素 (进栈、入栈、压栈) 
// pop    :  从栈顶删除一个元素 (出栈、弹栈)
// top    :  访问栈顶元素
// empty  :  判断栈是否为空，如果为空 1
// size   :  获取栈中元素的个数

2.队列

// 头文件 :  <queue>
// 队列 :  1、先进先出    2、从一端进，另一端出
// 进数据的一端：队尾
// 出数据的一端：队首
// push   :  从队尾添加一个元素 (入队)
// pop    :  从队首删除一个元素 (出队)
// front  :  访问队首元素
// back   :  访问队尾元素
// empty  :  判断栈是否为空，如果为空 1
// size   :  获取栈中元素的个数

3.优先队列

// 头文件 :  <queue>
// 优先队列 :  具有最高优先级的元素先出的特征
// push   :  从队尾添加一个元素 (入队)
// pop    :  从队首删除一个元素 (出队)
// top    :  访问队首元素
// 不能访问队尾元素
// empty  :  判断栈是否为空，如果为空 1
// size   :  获取栈中元素的个数

// 1、优先队列存放的数据类型
// 2、优先队列的底层容器
// 3、优先级规则, 不写就默认降序
//      greater<int>  升序
//      less<int>     降序
priority_queue<int, vector<int>, greater<int> >  q;
priority_queue<int, vector<int>, less<int> > p;

4.哈希表

//哈希表常用用法
//日期: 2024/4/27

//概念:
//----------
    /*
    一键对一值
    键是唯一的
    值可以重复
    键不可修改
    值可以修改
    */
//----------

//初始化:
//----------
    //定义一个'键'为string类型'值'为int类型的哈希表
    map<string,int> ma_1;
//----------

//输出: 
//----------
    //mode 1
    cout<<ma_1["键"];
    //mode 2
    map<string,int>::iterator it;
    it = ma_1.find("2233");
    if(it!=end()){
        cout<<it->first<<" "<<it->second<<endl;
    }
    //遍历
    for(auto i: ma_1){
        cout<<i.first<<" "<<i.second<<endl;
    }
//----------

//操作:
//----------
    //新建一个键值对(键为"apple"值为1)
    ma_1.insert({"apple",32});
    //寻找哈希表中键为"boom"的迭代器
    ma_1.find("boom");
    //统计哈希表中"apple"出现的次数 (由于哈希表键不能重复 所以只会返回0\1)
    ma_1.count("2233");
    //删除键"2233"
    ma_1.erase("2233");
//----------

图的基础

点集：v={v1,v2,v3,v4,v5......}
边集：E={e1，e2，e3，e4，e5......}
G=(V,E)
注：点集不能为空，边集可以为空
1.无向图：没有方向，边上的两点可以相互到达
（1）-（2）
2.有向图：有方向，只能一点到另一点
（1）->（2）
3.完全图：<1>完全无向图：任意两点之间均有一条边
          有n个顶点的完全无向图边有[n*（n-1）]/2条边
         <2>完全有向图：任意两点之间均有两条边
          有n个顶点的完全有向图边有n*（n-1）条边
4.子图：从点集中取出一些点组成点的子集，从边集中取出一些边组成点的边集，由这两个子集组成的图就是子图
5.度：顶点的边的总数是这个点的度
(1)-(2) （4）
 |
(3)
（1）的度为2
（2）的度为1
（3）的度为1
（4）的度为0
6.路径：从一个点经过一系列的边到另一个点的路线
7.回路：起点和中点相同的路径
<1>欧拉回路:指经过所有边\点 且不重复经过的回路
8.环：不包含重复边的回路，且至少包含三个顶点
9.连通：任意两个点之间都有路径
10.强连通：有向图中，任意两个点之间都有路径
11.弱连通：有向图中，将所有边的方向忽略后，得到的无向图是连通的
12.权：图的边有一个数值，这个数值为权，代表经过的代价或距离
13.网：带有权的图称作网
14.极大连通子图：无法扩大的连通的子图
15.连通分量：就是极大连通子图
补充：极小连通子图--最小生成树
     边有n-1条边

图的存储

1.邻接矩阵
有向图：矩阵中非0的个数为有向图的边数
优点：结构简单，代码易懂，查询任意两边的连通关系的复杂度为O(1)
缺点：空间复杂度为O(n^2)
2.邻接表
优点：空间效率高，空间复杂度为O(n+m)
缺点：查询效率低

666 学废了吗