本文共 2877 字，大约阅读时间需要 9 分钟。

题目链接:

时间限制：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 
   
    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;}
   

转载地址：http://qmftf.baihongyu.com/