题解 P1305 【新二叉树】
kradcigam
2019-07-18 16:31:40
好像没有人搞 map 反映。
# map 使用
map 是一个特别好的东西，有很大的用处。
> map 第一个好处是作为一个数组，可以开很大！
- 值域范围特别大：
```cpp
map<int,int>a;
```
你可以把 $a$ 数组当成普通数组用，不过要注意一点：
> map 是 STL，所以当你定义了一个后，就不能像普通数组一样使用一些的数组函数，比如 memset。
> - 你就不能写
> ```cpp
> memset(a,0,sizeof(a));
> ```
> - 取而代之的是 STL 的函数
> ```cpp
> a.clear();
> ```
> map 第二个好处是可以实现下标类型不一定为 int 的数组。
- 类型不一定为 int
map<下标类型,数值类型>
- 比如
```cpp
map<string,char>a;
string st="123";
a[st]='1';
```
## 补充说明
map 不仅可以开一维数组，还可以开二维数组。
- 比如：
```cpp
map<int,map<int,int> /*注意这里是一定要有空格的，否则在没有c++11的情况下会编译错误*/>；
```
# 回归本题
有了这些知识储备，我们可以更轻松地来做这道题，首先，题目中看到了遍历，我们就要先存储图。
```cpp
void find(char ch){
cout<<ch;
if(x[ch]!='*')find(x[ch]);
if(y[ch]!='*')find(y[ch]);
}
```
这里，我用了 map，`x[ch]` 表示了 `ch` 的左儿子，`y[ch]` 表示了 `ch` 的右儿子。
是不是很方便？ map 是个好东西！
有了 map，有了程序的框架，代码也自然浮出了水面。
```cpp
#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;//结束程序
}
```