蓝桥杯 - [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; }