ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

题解 P1305 【新二叉树】

posted on 2019-07-18 16:31:40 | under 题解 |

好像没有人搞 $\color{green}map$ 反映,没有人用 $\color{green}map$ 反映搞并查集!

$\color{green}map$ 第一个好处是作为一个数组,可以开很大!

我自认为 $\color{green}map$ 是一个特别好的东西,如果你的数组要开很大,但会爆炸,就最好用 $\color{green}map$ ,可以把它当做普通的数组用。

比如:

map<int,int>x;

你可以把x数组当成普通数组用,不过要注意一点。

map<int,int>x;

你定义了x数组后,就不能使用c++的数组函数,比如memset

你就不能写

memset(a,0,sizeof(a));

$\color{green}map$ 第二个好处下标不一定是一个整数,可以甚至可以是一个字符串!

$\color{blue}map<$ 下标类型 $\color{blue},$ 数值类型 $\color{blue}>;$

比如:

map<string,char>a;
string st="123";
a[st]='1';

补充说明

$\color{blue}map$ 不仅可以开一维数组,还可以开二维数组。

比如:

map<int,map<int,int> /*注意这里是一定要有空格的,否则会编译错误*/>;

有了这些知识储备,我们可以更轻松地来做这道题。

首先,题目中看到了遍历,是我们本能地想到并查集

并查集是通过递归的形式遍历整个图的一种算法,我们先让并查集先遍历以左儿子为树根的子树,再让并查集先遍历以右儿子为树根的子树,于是,我们有了这段并查集代码:

void find(char ch){
    cout<<ch;
    if(x[ch]!='*')find(x[ch]);
    if(y[ch]!='*')find(y[ch]);
}

很显然,我用了 $\color{green}map$ , $\color{blue}x[ch]$ 表示了一 $\color{blue}ch$ 的左儿子, $\color{blue}y[ch]$ 表示了一 $\color{blue}ch$ 的右儿子。

是不是很方便? $\color{skyblue}map$ 是个好东西!

有了 $\color{skyblue}map$ ,有了并查集,有了程序的框架,代码也自然浮出了水面。

#include <bits/stdc++.h>//以万能头文件开始了整个代码
using namespace std;
map<char,char>x;//用map来记录一个节点的左儿子
map<char,char>y;//用map来记录一个节点的右儿子
char a[35];//节点
void find(char ch){//并查集
    cout<<ch;
    if(x[ch]!='*')find(x[ch]);
    if(y[ch]!='*')find(y[ch]);
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        char left,right;
        cin>>a[i]>>left>>right;
        x[a[i]]=left;
        y[a[i]]=right;
    }find(a[1]);//开始遍历整棵树
    return 0;//结束程序
}