题解 P1305 【新二叉树】
rui_er
2019-05-23 19:56:00
# 方法简述
虽然不用建树,我还是建了一个,用的是顺序存储结构(数组)
```cpp
char tree[501];
```
# 头文件
```cpp
#include <iostream>
#include <memory.h>
#include <map>
using namespace std;
```
其中memory.h是为memset做准备的(我说的是memset,后面没有0!开个玩笑)
# 建树
```cpp
char tree[501];
map<char, int> k;
memset(tree, '*', 501);
int n;
cin>>n;
char a, b, c;
for(int i=0;i<n;i++)
{
cin>>a>>b>>c;
if(!i)
{
tree[1] = a;
k[a] = 1;
}
k[b] = k[a] * 2;
tree[k[b]] = b;
k[c] = k[a] * 2 + 1;
tree[k[c]] = c;
}
```
memset行用于给tree赋值。
> 听说第一行就是有关根节点的一行
if行用于判断是否为第一行,将根节点写入。k用于存字符出现的下标地址,方便查询一个节点的位置。
# 遍历
```cpp
void DLR(int n)
{
if(tree[n] == '*') return;
cout<<tree[n];
DLR(n*2);
DLR(n*2+1);
}
```
还记得前文的memset吗?输入的空结点用```*```表示,所以方便起见把树初始化成```*```。如果遇到```*```,则代表该结点不存在,自然就可以退出那个结点了。
根据前序遍历的定义,写出递归函数即可。
# 程序
```cpp
#include <iostream>
#include <memory.h>
#include <map>
using namespace std;
char tree[501];
map<char, int> k;
void DLR(int n)
{
if(tree[n] == '*') return;
cout<<tree[n];
DLR(n*2);
DLR(n*2+1);
}
int main()
{
memset(tree, '*', 501);
int n;
cin>>n;
char a, b, c;
for(int i=0;i<n;i++)
{
cin>>a>>b>>c;
if(!i)
{
tree[1] = a;
k[a] = 1;
}
k[b] = k[a] * 2;
tree[k[b]] = b;
k[c] = k[a] * 2 + 1;
tree[k[c]] = c;
}
DLR(1);
return 0;
}
```