P8603 [蓝桥杯 2013 国 C] 横向打印二叉树 题解

· · 题解

题意

给定一个数组，依次插入进排序二叉树（这玩意不是叫二叉搜索树吗）中，然后 横向 打印这棵树。

解法

二叉搜索树的部分不再多说，题目里说的很清楚了，主要是输出格式。为了方便，本人把它存进一个字符数组 mp[1010][1010]，最后再输出。

样例 1 输出:

...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4

观察样例 1，可发现这就是一个中序遍历，所以我处理时是用递归中序遍历的。

void output(LL p, LL space);

(虽然叫 output 但它不是输出，是处理怎样输出的。)

其中 p 是当前结点的编号，space 是要输出几个空格。

为了方便，可以将结点的值转换为字符串。

string trans(LL x){
    string res;
    while (x > 0)
        res = ((char)(x % 10 + '0')) + res, x /= 10;
    return res;
}

（很简单不说了。）

再观察，可发现每一层增加的空格都是由 这个数 和 两边的 -| 与 |- 组成，要特判一下 根节点 ，因为根节点开头没有字符。

所以 增加的空格数就是：

string num = trans(val);
LL Add = (p == 1 ? 0 : 2) + (LL)num.size() + 1;

（三元运算符的意思就是如果这个是编号 1 的根节点，就不加上开头的 2 个字符，否则加上。）

由于是中序遍历，所以结构这样：

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
...
void output(LL p, LL space){
    ...
    output(ls(p), space + Add);
    ....
    ....
    output(rs(p), space + Add);
    ....
    return ;
}

（(线段树好习惯)ls(x) 是 x 的左儿子，rs(x) 同理，Add 就是刚才求出的增加空格数。）

在处理完左子树后，就该处理自己结点了。

先在全局定义一个变量 nowL，代表现在处理到第几行了。

再是一个局部变量 ind，代表 index，现在处理到这一行的第几个了，初始化为 0。

开始我们应先输出全部的空格。

for (LL i = 1; i <= space; i ++){
    if (mp[nowL][++ ind] != '|')
        mp[nowL][ind] = '.';
}

关于这个 if 有什么用，暂不讨论，看下面。

再次观察样例 1。

可发现除了根节点和叶子结点外，输出的就为 |- 加上 这个数（可以用刚才的字符串） 加上 -| 。

根节点就除去开头的 |-。

叶子结点就除去结尾的 -|。

如下：

// 根节点特判
if (p != 1){
    mp[nowL][++ ind] = '|'; mp[nowL][++ ind] = '-';
}

// 输出这个数字
for (LL i = 0; i < (LL)num.size(); i ++)
    mp[nowL][++ ind] = num[i];

// 叶子结点特判
if (tree[ls(p)] != -1 || tree[rs(p)] != -1)
    mp[nowL][++ ind] = '-', mp[nowL][++ ind] = '|';

为了输出方便，可在结尾加上一个标识符，代表这一行结束。

mp[nowL][++ ind] = '@';

然后处理左子树（根据前面的结构代码）。

这样算完成了 80\%。

最后是重头戏。

继续观察样例，可发现如果自身与子节点隔了几行，那么要在那几行加上几个 |，列的位置和自己这一行的最后那一个 | 是一样的。

这样就还要开一个数组 line[110] 表示当前结点所在的行数。

// 如果有左子树
if (tree[ls(p)] != -1){
    // L 为 左子树的 行位置
    LL L = line[ls(p)], now = line[p];
    for (LL i = L; i >= now; i --)
        mp[i][ind - 1] = '|';
}
// 如果有右子树
if (tree[rs(p)] != -1){
    // R 为 右子树的 行位置
    LL R = line[rs(p)], now = line[p];
    for (LL i = now; i >= R; i --)
        mp[i][ind - 1] = '|';
}

这样在看刚才输出空格时的 if，就明白了它是什么意思了吧，它就是 防止后面的空格把前面的 | 覆盖。

这样整个代码就差不多完成了。

其余部分不讲了。

Code

#include<bits/stdc++.h>
#define LL long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define Fcin\
    ios :: sync_with_stdio(0);\
    cin.tie(0); cout.tie(0)
using namespace std;
const LL N = 110;
LL n, tree[N * 4], nowL = 0, line[N * 4];
char mp[N * 10][N * 10]; 

void insert(LL x, LL p){
    if (tree[p] == -1){
        tree[p] = x;
        return ;
    }
    if (x < tree[p])
        insert(x, ls(p));
    else
        insert(x, rs(p));
    return ;
}

string trans(LL x){
    string res;
    while (x > 0)
        res = ((char)(x % 10 + '0')) + res, x /= 10;
    return res;
}

void output(LL p, LL space){
    if (tree[p] == -1)
        return ;
    LL val = tree[p];

    string num = trans(val);
    LL Add = (p == 1 ? 0 : 2) + (LL)num.size() + 1;

    output(rs(p), space + Add);

    ++ nowL;
    line[p] = nowL;
    LL ind = 0;

    for (LL i = 1; i <= space; i ++){
        if (mp[nowL][++ ind] != '|')
            mp[nowL][ind] = '.';
    }

    if (p != 1){
        mp[nowL][++ ind] = '|'; mp[nowL][++ ind] = '-';
    }

    for (LL i = 0; i < (LL)num.size(); i ++)
        mp[nowL][++ ind] = num[i];

    if (tree[ls(p)] != -1 || tree[rs(p)] != -1)
        mp[nowL][++ ind] = '-', mp[nowL][++ ind] = '|';

    mp[nowL][++ ind] = '@';
    output(ls(p), space + Add);

    if (tree[ls(p)] != -1){
        LL L = line[ls(p)], now = line[p];
        for (LL i = L; i >= now; i --)
            mp[i][ind - 1] = '|';
    }
    if (tree[rs(p)] != -1){
        LL R = line[rs(p)], now = line[p];
        for (LL i = now; i >= R; i --)
            mp[i][ind - 1] = '|';
    }   

    return ;
}

int main(){
    memset(tree, -1, sizeof(tree));
    Fcin;
    LL x;
    while (cin >> x){
        ++ n;
        insert(x, 1);
    }

    output(1, 0);
    for (LL i = 1; i <= nowL; i ++){
        LL j = 1;
        while (mp[i][j] != '@'){
            cout << mp[i][j];
            ++ j;
        }
        cout << "\n";
    }

    return 0;
}