蓝桥杯 - [2013年第四届真题]横向打印二叉树(排序二叉树)

题目链接:http://lx.lanqiao.cn/problem.page?gpid=T34
时间限制：1.0s 内存限制：256.0MB

问题描述

二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如下图所示，其中.表示空白。

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

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

输入格式

输入数据为一行空格分开的N个整数。 N<100，每个数字不超过10000。
输入数据中没有重复的数字。

输出格式

输出该排序二叉树的横向表示。为了便于评卷程序比对空格的数目，请把空格用句点代替：

样例输入

10 5 20

5 10 20 8 4 7

样例输出

...|-20
10-|
...|-5

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

解题思路

这道题应该考察的是排序二叉树和对字符串的处理。

首先我们可以发现：
1.一行只有一个数;
2.字符只有'.', '-', '|'三种;
3.非第一列的数前面都有"|-";
4.非叶子节点的数后面都有"-|";

我们可以先整理好的二叉树存到字符串数组里面，然后再插入'|'.

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int lson, rson, num, row;
}tree[105];
int cnt = 1, row = 0;
char str[105][605];
void Create(int root, int delta) {
    if (tree[root].num < delta) {
        if (tree[root].rson != -1)
            Create(tree[root].rson, delta);
        else {
            tree[root].rson = cnt;
            tree[cnt++].num = delta;
        }
    }
    else {
        if (tree[root].lson != -1)
            Create(tree[root].lson, delta);
        else {
            tree[root].lson = cnt;
            tree[cnt++].num = delta;
        }
    }
}
int get_dig(int n) {//计算数字的位数
    int cnt = 0;
    while (n) {
        cnt++;
        n /= 10;
    }
    return cnt;
}
void print_1(int root, int col, int num) {//将二叉树存到数组里面
    int pre = num + get_dig(tree[root].num) + (!col ? 1 : 3);
    if (tree[root].rson != -1)//寻找右子树，往上走
        print_1(tree[root].rson, col + 1, pre);
    for (int i = 0; i < num; i++)
        str[row][i] = '.';
    if (!col) {//第一列
        if (tree[root].lson != -1 || tree[root].rson != -1)
            sprintf(str[row] + num, "%d%s", tree[root].num, "-|");
        else sprintf(str[row] + num, "%d", tree[root].num);
    }
    else {
        if (tree[root].lson != -1 || tree[root].rson != -1)
            sprintf(str[row] + num, "%s%d%s", "|-", tree[root].num, "-|");
        else sprintf(str[row] + num, "%s%d", "|-", tree[root].num);
    }  
    tree[root].row = row++;//进入下一行
    if (tree[root].lson != -1)
        print_1(tree[root].lson, col + 1, pre);
}
void print_2(int root, int col, int num) {//往数组里面插入'|'
    int pre = num + get_dig(tree[root].num) + (!col ? 1 : 3);
    if (tree[root].rson != -1) {
        print_2(tree[root].rson, col + 1, pre);
        for (int i = tree[tree[root].rson].row; i < tree[root].row; i++)
            str[i][pre] = '|';
    }
    if (tree[root].lson != -1) {
        print_2(tree[root].lson, col + 1, pre);
        for (int i = tree[tree[root].lson].row; i > tree[root].row; i--)
            str[i][pre] = '|';
    }
}
int main() {
    int delta;
    memset(tree, -1, sizeof(tree));
    scanf("%d", &delta);
    tree[0].num = delta;
    while (~scanf("%d", &delta))
        Create(0, delta);
    row = 0;
    print_1(0, 0, 0);
    print_2(0, 0, 0);
    for (int i = 0; i < row; i++)
        printf("%s\n", str[i]);
    return 0;
}