2014-07-06

UVa 12010 - Boring Homework

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

Professor Z. always gives his students lots of boring homework. Last week, after explaining binary search trees (BSTs), he asked his students to draw a picture of BST according to the list of numbers inserted into the tree sequentially. Maryanna spent so much time playing the game “Starcraft II” that she can’t finish her homework in time. She needs your help.

A binary search tree, which may sometimes also be called ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
-from Wikipedia

To draw a picture of BST, you may follow the rules listed below:

The picture of a 1-node BST, whose size is 1*1, is a single ‘o’ (15th small Latin letter).
If a BST has a non-empty subtree, draw a single ‘|’ just above the subtree’s root, and a single ‘+’ just above previous drawn ‘|’. Finally, in the row of ‘+’, use the least number (including 0) of ‘-‘s to connect ‘+’ (denoting the left subtree and right subtree) and ‘o’ (denoting the parent node of the subtree)
The left subtree (if exists) must be drawn on the left side of its parent. Similarly, the right subtree (if exists) must be drawn on the right side of its parent.
The column of the BST’s root must not contain any character from left subtree or right subtree.
Any column containing any characters from BST’s left subtree must not contain any characters from BST’s right subtree, and vice versa. That is, for a node of the BST, the picture of its left subtree and the picture of its right subtree do not share common columns in the picture of the whole tree.

The sample output may give a clear clarification about the format of the picture.

Input

The first line contains T ( T$\le$2500), the number of test cases. T lines follow. Each line contains a positive integer N (N < 80), followed by N integers - a permutation of 1 to N. The permutation indicates the insert order for the BST.

Output

For each test case:

Output the case number counting from 1 in the first line. The next lines should be the image described above without any trailing spaces. See the sample for more format details.

Note: Notice that no trailing whitespaces after the last visible characters of each line are allowed.

Sample Input

3
3 3 1 2
6 4 5 6 1 3 2
5 3 4 5 2 1

Sample Output

Case #1:
+-o
|
o+
 |
 o
Case #2:
+--o+
|   |
o-+ o+
  |  |
 +o  o
 |
 o
Case #3:
 +o+
 | |
+o o+
|   |
o   o

Solution

題目描述：

請先依序插入節點，並且建造一棵二分搜尋樹，接著打印出來。

以 o 表示節點，而用 + 表示左右子樹的存在，並且用 - 來移動其位置。盡可能用最少的 - 來完成。並且每一列 (縱向) 只會有一個 o 存在。

題目解法：

根據中序搜索，可以得到由左至右的打印節點順序，根據這個打印順序著手左右的 - 計算。

#include <stdio.h>
#include <string.h>
struct Node {
    int v, l, r, porder;
};
Node BST[128];
char g[256][128];
int porder = 0, mxdep;
void build(int nd, int dep) {
    if(dep > mxdep)	mxdep = dep;
    if(BST[nd].l != -1)
        build(BST[nd].l, dep+2);
    BST[nd].porder = porder++;	
    if(BST[nd].r != -1)
        build(BST[nd].r, dep+2);
        
    if(BST[nd].l != -1) {
        g[dep][BST[BST[nd].l].porder] = '+';
        g[dep+1][BST[BST[nd].l].porder] = '|';
        for(int i = BST[BST[nd].l].porder + 1; i < BST[nd].porder; i++)
            g[dep][i] = '-';
    }
    g[dep][BST[nd].porder] = 'o';
    if(BST[nd].r != -1) {
        for(int i = BST[BST[nd].r].porder - 1; i > BST[nd].porder; i--)
            g[dep][i] = '-';
        g[dep][BST[BST[nd].r].porder] = '+';
        g[dep+1][BST[BST[nd].r].porder] = '|';
    }
}
int main() {
    int testcase, cases = 0, N;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &N);
        memset(BST, -1, sizeof(BST));
        scanf("%d", &BST[0].v);
        int size = 1, x;
        for(int i = 1; i < N; i++) {
            scanf("%d", &x);
            int idx = 0;
            do {
                if(x < BST[idx].v) {
                    if(BST[idx].l != -1)
                        idx = BST[idx].l;
                    else
                        BST[idx].l = size, BST[size++].v = x, idx = 0;
                } else {
                    if(BST[idx].r != -1)
                        idx = BST[idx].r;
                    else
                        BST[idx].r = size, BST[size++].v = x, idx = 0;
                }
            } while(idx);
        }
        porder = 0, mxdep = 0;
        memset(g, ' ', sizeof(g));
        build(0, 0);
        printf("Case #%d:\n", ++cases);
        for(int i = 0; i <= mxdep; i++) {
            for(int j = N; g[i][j] == ' '; j--)
                g[i][j] = '\0';
            printf("%s\n", g[i]);
        }
    }
    return 0;
}

Morris' Blog