》》》算法竞赛

/**
 * @file            
 * @author          jUicE_g2R(qq:3406291309)————彬(bin-必应)
 *						一个某双流一大学通信与信息专业大二在读	
 * 
 * @brief           一直在算法竞赛学习的路上
 * 
 * @copyright       2023.8
 * @COPYRIGHT			 原创技术笔记：转载需获得博主本人同意，且需标明转载源
 *
 * @language        C++
 * @Version         1.0还在学习中  
 */

• UpData Log👆 2023.8.21 更新进行中

• Statement0🥇 一起进步

• Statement1💯 整个blog代码暂时没有考虑数据范围，有的地方应该用long long数据类型而用了int

技术提升站点

12 搜索

阅读该代码前先对数据结构中==“树”==的知识有一定的认识（该blog仅用于提升代码能力）

12-1-1 BFS与DFS

12-1-2 层序遍历

在BFS的基础上，对每一层进行划分

层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

先看看 BFS 遍历的过程

BFS 遍历使用队列数据结构：

为什么要用队列？

对于 BFS 算法，我们需要一层一层遍历所有的相邻结点。那么相邻结点之间的先后顺序如何确定？需要使得先遍历的结点先被存储，直到当前层都被存储后，按照先后顺序，先被存储的结点也会被先取出来，继续遍历它的相邻结点。FIFO的理念就体现出来了。

//BFS遍历（使用队列）
#include<bits/stdc++.h>
using namespace std;
struct Tnode{
    int val;
    Tnode* lson;
    Tnode* rson;
    Tnode(int val,Tnode* lson=NULL,Tnode* rson=NULL):val(val),lson(lson),rson(rson){};//对要接收参数形式进行定义
};
void BFStraversal(Tnode* ptr){
    if(ptr==NULL) return;//void不会返回值
    queue<Tnode*> Q;
    Q.push(ptr);
    while(!Q.empty()){
        Tnode* node=Q.front();//返回但不删除队首元素
        cout<< node->val << " -> " ;
        if(node->lson!=NULL)
            Q.push(node->lson);
        if(node->rson!=NULL)
            Q.push(node->rson);
        Q.pop();
    }
}
int main(void){
    Tnode* n7=new Tnode(7); Tnode* n8=new Tnode(8); Tnode* n9=new Tnode(9);
    Tnode* n4=new Tnode(4); Tnode* n5=new Tnode(5,n7,NULL); Tnode* n6=new Tnode(6,n8,n9);
    Tnode* n2=new Tnode(2,n4,n5);Tnode* n3=new Tnode(3,NULL,n6);
    Tnode* n1=new Tnode(1,n2,n3);
    Tnode* root=n1;//n1与root指向同一个结点
    BFStraversal(root);
    return 0;
}

截取 BFS 遍历的某个过程

此时，队列（子序列）中既有第一层的元素，又有第二层的元素（第 1 层的结点还没出完，第 2 层的结点就进来了，而且两层的结点在队列中紧挨在一起），无法将他们区分开来。

只需在原来的BFS遍历算法上添加层序划分的功能，

在每一层遍历开始前，先记录队列中的结点数量n（也就是这一层的结点数量），然后一口气处理完这一层的 n个结点。

//原BFS的循环部分代码
while(!Q.empty()){
    Tnode* node=Q.front();//返回得到但不删除队首元素
    cout<< node->val << " -> " ;
    if(node->lson!=NULL)
        Q.push(node->lson);
    if(node->rson!=NULL)
        Q.push(node->rson);
    Q.pop();
}

//稍加修改的层序遍历的循环部分代码
while(!Q.empty()){
    int n=Q.size();
    for(int i=0;i<n;i++){
        Tnode* node=Q.front();//返回得到但不删除队首元素
        cout<< node->val << " -> " ;
        if(node->lson!=NULL)
            Q.push(node->lson);
        if(node->rson!=NULL)
            Q.push(node->rson);
        Q.pop();
    }
    cout<<endl;//换行分层
}

//输出展示
1 ->
2 -> 3 ->
4 -> 5 -> 6 ->
7 -> 8 -> 9 ->

12-2 双向广搜

技术提升站点