쿼드 트리

쿼드 트리 뒤집기

트리 만들기만 하면 된다!!

// 쿼드 트리
#include <iostream>
 
using namespace std;
 
int C;
char OrigStr[1001];
int index = 0;    //인덱스를 글로벌로 설정해서 꼬이지 않게 함. 
typedef struct tree* Quadtree;
struct tree {
    char elem;
    Quadtree child[4];
};
 
void printTree(Quadtree t) {
    if (t == NULL) {
        return;
    }
    cout << t->elem;
    for (int i = 0; i < 4; i++) {
        printTree(t->child[i]);
    }
}
 
Quadtree reverseTree(Quadtree t) {
    if (t == NULL)
        return NULL;
    if (t->elem != 'x') 
        return t;
 
    for (int i = 0; i < 2; i++) {
        Quadtree tmp = NULL;
        tmp = t->child[i];
        t->child[i] = t->child[i + 2];
        t->child[i + 2] = tmp;
    }
    for (int i = 0; i < 4; i++) {
        t->child[i] = reverseTree(t->child[i]);
    }
    return t;
 
}
 
Quadtree createTree(Quadtree t) {
    char current = OrigStr[index];
    // base condition
    if (current == '\0')
        return t;
    if (t != NULL)
        return t;
 
    // null ptr 메모리할당
    t = (Quadtree)malloc(sizeof(tree));
    t->elem = current;
    index++;
 
    //NULL로 초기화 함
    for (int i = 0; i < 4; ++i) {
        t->child[i] = NULL;
    }
    if (current == 'x') {
        for (int i = 0; i < 4; ++i) {
            t->child[i] = createTree(t->child[i]);
        }
    }
    return t;
}
int main() {
    //freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; ++c) {
        cin >> OrigStr;
        Quadtree t = NULL;
        index = 0;
        t = createTree(t);
        //printTree(t);
        //cout << endl;
        t = reverseTree(t);
        printTree(t);
        cout << endl;
    }
    return 0;
}