[UVA][Tree] 12458 - Oh, my trees!＠Morris' Blog

2012-05-06 17:56:21| 人氣431| 回應0 | 上一篇 | 下一篇

[UVA][Tree] 12458 - Oh, my trees!

Background

Pablito likes trees of all kinds: palm trees, pine trees, orange trees, eggplants, etc. But his favorites are binary search trees.

As you should know, binary search trees (BST) are binary trees (i.e., each node of the tree can have zero, one or two subtrees, which are called left and right subtrees) with the following property:

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.

Pablito is very proud of his huge collection of BS trees. However, he has a younger brother who loves deleting trees. Poor thing! He is only 2 years old!

Pablito's brother has the ability of deleting only the edges of the trees, but not the nodes. Can you help Pablito to fix up the disaster made by his brother?

We have a set of different integer values, which are the keys of a BST. But the edges of the BST have been deleted; we know the level (or depth) of each key in the tree, but we do not know the father-child relationships.

Trees
A sample case. Left: a BST with the edges deleted. Right: the same tree with the left-child / right-child relationships undeleted.

Your task is to recover the right-child / left-child relationships for all nodes.

Input

The input can contain different test cases. The first line of the input indicates the number of test cases.

For each test case, the first line contains an integer, H, which is the total hight of the tree (i.e., the number of levels). Then, there are H lines, each of them with a set of integers separated by spaces. Each line contains the keys of each level of the BST. You can assume that the description of the tree is always valid; keys are not repeated.

For example, the previous tree would be represented as:

Output

For each test case, you have to output each key in a line, in the same order as they appear in the input. For eack key, you have to indicate his children in the following format:

node:leftChild-rightChild

If the node does not have left or right child, no number is printed. For example, in the previous three the result should be:

5:3-8
3:-
8:6-9
6:-7
9:-
7:-

Sample Input

Sample Output

5:3-8
3:-
8:6-9
6:-7
9:-
7:-
23:-59
59:35-
35:-39
39:36-
36:-
10:4-12
4:1-6
12:11-31
1:0-3
6:5-8
11:-
31:-51
0:-
3:-
5:-
8:-
51:34-
34:-49
49:40-
40:38-45
38:-
45:-

頗蠻麻煩的

#include <stdio.h>
#include <iostream>
#include <sstream>
using namespace std;

struct Node {
    Node *r, *l;
    int v, left, right;
    Node() {
        r = l = NULL;
        v = 0;
    }
};
char str[100000];
int num[100000], hnum[100000];
Node *h[100000];
int main() {
    int t, n;
    stringstream sin;
    string line;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        getchar();
        int i, j, idx, x;
        for(i = 0; i < n; i++) {
            getline(cin, line);
            sin.clear();
            sin << line;
            idx = 0;
            while(sin >> x) {
                num[idx++] = x;
            }
            h[i] = new Node[idx];
            for(j = 0; j < idx; j++) {
                h[i][j].v = num[j];
            }
            hnum[i] = idx;
        }
        h[0][0].left = -2147483647;
        h[0][0].right = 2147483647;
        for(i = 1; i < n; i++) {
            idx = 0;
            for(j = 0; j < hnum[i]; j++) {
                int v = h[i][j].v;
                while(true) {
                    if(h[i-1][idx].v > v) {
                        if(h[i-1][idx].left < v && h[i-1][idx].right > v) {
                            h[i-1][idx].l = &h[i][j];
                            h[i][j].left = h[i-1][idx].left;
                            h[i][j].right = h[i-1][idx].v;
                            break;
                        }
                    }
                    if(h[i-1][idx].v < v) {
                        if(h[i-1][idx].left < v && h[i-1][idx].right > v) {
                            h[i-1][idx].r = &h[i][j];
                            h[i][j].left = h[i-1][idx].v;
                            h[i][j].right = h[i-1][idx].right;
                            break;
                        }
                    }
                    idx++;
                }
            }
        }
        for(i = 0; i < n; i++) {
            for(j = 0; j < hnum[i]; j++) {
                printf("%d:", h[i][j].v);
                if(h[i][j].l != NULL) {
                    printf("%d", h[i][j].l->v);
                }
                putchar('-');
                if(h[i][j].r != NULL) {
                    printf("%d", h[i][j].r->v);
                }
                puts("");
            }
            delete[] h[i];
        }
    }
    return 0;
}