1452.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1452 on 2005-09-14 at 03:39:19 */ 
#include <cstdio>
#include <cstring>
using namespace std;

class Node {
    public:
    char content;
    Node *left;
    Node *right;
    Node *root;
    void leftRightRoot() {
        if(left != NULL) {    
            left->leftRightRoot();
        }
        if(right != NULL) {    
            right->leftRightRoot();
        }
        if(root != NULL) {
            root->leftRightRoot();
        }
        putchar(content);
        return;
    }
    Node(char c) {
        left = NULL;
        right = NULL;
        root = NULL;
        content = c;
    }    
};

Node* tree(Node* node[], int n, char *order);

int main()
{
    Node *node[26], *root;
    char rlr[30], lrr[30], ch, order[130];
    int i, len;
    
    while(1) {
        for(i = 0; i < 26; i++) {
            ch = getchar();
            if(ch == EOF) {
                return 0;
            } else if(ch == ' ') {
                break;
            } else {
                rlr[i] = ch;
                rlr[i+1] = 0;
            }    
        }
        scanf("%s", lrr);
        len = strlen(rlr);
        for(i = 0; i < len; i++) {
            order[rlr[i]] = i;
            node[i] = new Node(lrr[i]);
        }
        root = tree(node, len, order);
        root->leftRightRoot();
        printf("\n");
        while(getchar() != '\n')
            ;
    }
}

Node* tree(Node* node[], int n, char *order)
{
    int min = 100, i, posi;
    Node *left[30], *right[30];
    
    if(n == 0) {
        return NULL;
    } else if(n == 1) {
        return node[0];
    } else {
        for(i = 0; i < n; i++) {
            if(order[node[i]->content] < min) {
                min = order[node[i]->content];
                posi = i;
            }    
        }
        for(i = 0; i < posi; i++) {
            left[i] = node[i];
        }
        for(i = posi+1; i < n; i++) {
            right[i-posi-1] = node[i];
        }
        node[posi]->left = tree(left, posi, order);
        node[posi]->right = tree(right, n-posi-1, order);
        
        return node[posi];
    }
}