P1305 新二叉树 题解

· · 题解

P1305 新二叉树 题解

很水的一道二叉树的题。其实并不需要真正利用在程序中构造二叉树进行求解的思路，而是利用二叉树的性质，找出规律，从而得出结果。

首先让我们看到题目：

题目描述

输入一串二叉树，用遍历前序打出。

一看这个题目，似乎还无法得出一个规律。不过我们产生了问题：如何输入这一串二叉树？

输入格式

第一行为二叉树的节点数n。(n≤26)。

后面n行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用星号表示。

这样似乎就明了了：二叉树好像是通过这几种形式输入的：

输出格式

前序排列的二叉树。

既然要求这样输出，那么我们就可以寻找一下前序排列的规律：

在只有一个节点的情况下，这棵树长这样：

它的前序排列自然是这样： A

如果有了两个节点，则会变成这样：

前序排列为： AB

有了三个节点，会变成这样：

前序排列为： ABC

似乎还没有看出什么端倪。不过，让我们继续向下发展这棵二叉树：

前序排列： ABDC

等等，怎么……顺序发生了一些变化？不再是依字母表顺序排列了？

再来！

前序排列： ABDEC

原来规律是这样！

每次第一个输入的序列（根节点及其子节点） 直接被加入前序中；

后续有两种儿子的，则忽略 “ 星号 ” 字符，将左儿子插入序列中其父亲节点后的一位，将右儿子插入序列中其左儿子节点的后一位。

仅有一种儿子的（表现形式为 父亲 儿子 星号 ），就简单将其儿子插入父亲节点的后一位即可。

找到父亲节点或左儿子的方法很简单：通过 string 类的这个成员函数即可完成：

int find(string s);

这个成员函数的作用是返回子字符串s在原串中的位置。如果找不到，则返回：

string::npos

这个常量。（这个常量在不同的编译器中，有不同的值，虽然有些时候是 -1 ，但是可能其他时候会出差错。因此，我们在这里不写-1，而写这个常量更为保险。）

然后，我们再使用这个类里面的另一个函数 insert 向指定的位置插入代表子节点的字符：

void insert(int position,int length,string s);

它的作用是 从字符串中的第position个位置开始，插入length个字符，这些字符来源于s 。

这样，我们就可以得到这题的代码！

代码如下：

#include<bits/stdc++.h>
using namespace std;
string t;
int n;
string s;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        if(t.find(s[0])==string::npos){t=s;continue;}
        if(s[1]!='*') t.insert(t.find(s[0])+1,1,s[1]);
        if(s[2]!='*') t.insert(t.find(s[1])+1,1,s[2]);
    }
    cout<<t<<endl;
}
你觉得一次就能AC了？

并不是！

实际上！

这个只有20分！！！

为什么？为什么只有20分？

很简单。下载数据后，你会发现这是因为这份代码没有考虑到这种数据的存在：

“指示根节点及其子节点的第一行就含星号 ！！！”

这种数据会带来什么影响？

你的程序将把“ 星号 ”当作一种子节点！！！

于是，之后的输出就完全混乱了。毕竟，由于第一行是特判全部输入，“ 星号 ”这样的鬼东西都被插进了字符串里面。

不过这样一来，你就找到了修改的思路：

使用 string 类的这个成员函数： erase ！

void erase(string::iterator start,string::iterator end);

直接运用它，产生的作用其实是消除一个字符串中的一段连续的长度。那么怎么达到消除全部指定字符（此处为标明了根节点及其儿子的字符串中的 “ * ” ）呢？

使用 algorithm 库中的 remove 函数！

iterator remove(iterator start,iterator end,auto c);

有了这个，我们就能够不断地清除字符串中的目标字符，并不断返回指向其未被删除元素的下一个元素的迭代器，从而使用erase函数清除它。

于是，我们得到了用于清除一段字符串中全部指定字符的完整代码：

erase(remove(string::iterator start,string::iterator end,char c),string::iterator end);

那么，新的代码也呼之欲出了！

新代码如下：

#include<bits/stdc++.h>
using namespace std;
string t;
int n;
string s;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        if(t.find(s[0])==string::npos){
            s.erase(remove(s.begin(),s.end(),'*'),s.end());
            t=s;
            continue;
        }
        if(s[1]!='*') t.insert(t.find(s[0])+1,1,s[1]);
        if(s[2]!='*') t.insert(t.find(s[1])+1,1,s[2]);
    }
    cout<<t<<endl;
}
你又觉得这次就能AC了？

并不是！

其实！

这个只有30分！！！

才多过了一个点啊……

这次又是为什么？？！

下载数据后发现，这次是栽在了一种之前从未考虑到的输入情况上。

这次导致出错的输入数据为：

……

这也太坑了吧

我们为了AC此题，只能继续努力了……

这次更改并不需要什么新的技术，只需要添加几个判断即可绕过大坑。

代码如下：

#include<bits/stdc++.h>
using namespace std;
string t;
int n;
string s;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        if(t.find(s[0])==string::npos){
            s.erase(remove(s.begin(),s.end(),'*'),s.end());
            t=s;
            continue;
        }
        if(s[1]!='*'&&s[2]!='*'){
            t.insert(t.find(s[0])+1,1,s[1]);
            t.insert(t.find(s[1])+1,1,s[2]);
        }
        if(s[1]=='*'&&s[2]!='*'){
            t.insert(t.find(s[0])+1,1,s[2]);
        }
        if(s[1]!='*'&&s[2]=='*'){
            t.insert(t.find(s[0])+1,1,s[1]);
        }
    }
    cout<<t<<endl;
}

看着屏幕上蓝色方块上转着白色的圈圈，你想到：之前（指20分变30分那次）做了那么大的修改，才多过了一个点，想必这个算法还存在很多问题吧……难不成还得再重写几次？？！

然后……

？？？？？？

过了？？！就过了？？？？？！

历经千辛万苦，终于过了啊……（接受现实）

bilibili干杯！（好像并没有什么不对）