1991번: 트리 순회

기본적인 트리 개념만 이해하고 있으면 풀 수 있는 문제다.

본인은 두 가지 방법으로 풀었다.

그런데.. 좀 더 효율적이게 구성할 수 있을 거 같아보인다.

나중에 다시 살펴보자.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
    
void DFS1(std::vector<std::pair<int, std::string>> tree[], int cur) {
    if (tree[cur].size() == 0) {
        std::cout << (char)(cur + '0');
    }
    else if (tree[cur].size() == 1) {
        std::cout << (char)(cur + '0');
        if (tree[cur][0].second == "left") {
            DFS1(tree, tree[cur][0].first);
        }
        else if (tree[cur][0].second == "right") {
            DFS1(tree, tree[cur][0].first);
        }
 
    }
    else if (tree[cur].size() == 2) {
        std::cout << (char)(cur + '0');
        DFS1(tree, tree[cur][0].first);
        DFS1(tree, tree[cur][1].first);
    }
}
 
void DFS2(std::vector<std::pair<int, std::string>> tree[], int cur) {
    if (tree[cur].size() == 0) {
        std::cout << (char)(cur + '0');
    }
    else if (tree[cur].size() == 1) {
        if (tree[cur][0].second == "left") {
            DFS2(tree, tree[cur][0].first);
            std::cout << (char)(cur + '0');
        }
        else if (tree[cur][0].second == "right") {
            std::cout << (char)(cur + '0');
            DFS2(tree, tree[cur][0].first);
        }
 
    }
    else if (tree[cur].size() == 2) {
        DFS2(tree, tree[cur][0].first);
        std::cout << (char)(cur + '0');
        DFS2(tree, tree[cur][1].first);
    }
}
 
void DFS3(std::vector<std::pair<int, std::string>> tree[], int cur) {
    if (tree[cur].size() == 0) {
        std::cout << (char)(cur + '0');
    }
    else if (tree[cur].size() == 1) {
        if (tree[cur][0].second == "left") {
            DFS3(tree, tree[cur][0].first);
            std::cout << (char)(cur + '0');
 
        }
        else if (tree[cur][0].second == "right") {
            DFS3(tree, tree[cur][0].first);
            std::cout << (char)(cur + '0');
        }
 
    }
    else if (tree[cur].size() == 2) {
        DFS3(tree, tree[cur][0].first);
        DFS3(tree, tree[cur][1].first);
        std::cout << (char)(cur + '0');
    }
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int N;
    std::cin >> N;
 
    std::vector<std::pair<int, std::string>> tree[200];
    char C, L, R;
    for (int i = 0; i < N; i++) {
        std::cin >> C >> L >> R;
        if (L != '.') {
            tree[C - '0'].push_back({ L - '0', "left"});
        }
        if (R != '.') {
            tree[C - '0'].push_back({ R - '0', "right"});
        }
    }
 
    DFS1(tree, 'A' - '0');
    std::cout << "\n";
    DFS2(tree, 'A' - '0');
    std::cout << "\n";
    DFS3(tree, 'A' - '0');
    std::cout << "\n";
 
    return 0;
}

#include<iostream>
#include<cstring>
#include<string>
#define MAX 10000 + 10
 
 
typedef struct linkedList {
    char data;
    struct linkedList *rLink;
    struct linkedList *lLink;
} linkedList;
 
linkedList* createNode() {
    linkedList *newNode= (linkedList*)malloc(sizeof(linkedList));
    newNode->data = NULL;
    newNode->lLink = NULL;
    newNode->rLink = NULL;
 
    return newNode;
}
 
linkedList *headNode = createNode();
linkedList *center = NULL;
int count = 0;
char centerNode, lNode, rNode, direction;
char addData;
 
void displayTree(linkedList *headNode, int method) {
    if (method == 0) {
        std::cout << headNode->data;
    }
    if (headNode->lLink != NULL) {
        displayTree(headNode->lLink, method);
    }
    if (method == 1) {
        std::cout << headNode->data;
    }
    if (headNode->rLink != NULL) {
        displayTree(headNode->rLink, method);
    }
    if (method == 2) {
        std::cout << headNode->data;
    }
}
 
void addNode(linkedList *centerNode, char direction, char data) {
    linkedList *newNode = createNode();
    newNode->data = data;
    /*linkedList *centerNode = NULL;
    centerNode = searchNode(headNode, center);*/
    //std::cout << centerNode->data << "\n";
    if (direction == 'l') {
        centerNode->lLink = newNode;
        //std::cout << "l, " << centerNode->data << "->" << newNode->data << "\n";
    }
    else if (direction == 'r') {
        centerNode->rLink = newNode;
        //std::cout << "r, " << newNode->data << "\n";
    }
}
 
void searchNode(linkedList *centerNode, char data) {
    if (centerNode->data == data) {
        //std::cout << centerNode->data << "\n";
        addNode(centerNode, direction, addData);
    }
    if (centerNode->lLink != NULL) {
        //std::cout << centerNode->data << "\n";
        searchNode(centerNode->lLink, data);
    }
    if (centerNode->rLink != NULL) {
        //std::cout << centerNode->data << "\n";
        searchNode(centerNode->rLink, data);
    }
 
    //return searchNode(centerNode->lLink, data);
}
 
 
int main(void) {
    headNode->data = 'A';
 
    std::cin >> count;
    for (int i = 0; i < count; i++) {
        std::cin >> centerNode >> lNode >> rNode;
        //std::cout << center->data << "\n";
 
        if (lNode != '.') {
            direction = 'l';
            addData = lNode;
            searchNode(headNode, centerNode);
        }
        if (rNode != '.') {
            direction = 'r';
            addData = rNode;
            searchNode(headNode, centerNode);
        }
    }
 
    for (int i = 0; i < 3; i++) {
        displayTree(headNode, i);
        std::cout << "\n";
    }
    return 0;
}