[자료 구조] C++로 Tree 구현

#include <iostream>
#include <vector>
using namespace std;

#define endl '\n'

struct Node {
    int data;
    Node *parent;
    vector<Node *> childList;
    Node(int data, Node *parent) {
        this->data = data;
        this->parent = parent;
    }
};

class Tree {
public:
    Tree(int data);
    void insertNode(int parent, int data);
    void deleteNode(int data);
    void printParent(int data);
    void printChild(int data);
    void min_maxChild(int data);

private:
    Node* root;
    vector<Node *> nodeList;

    int find(int data, vector<Node *> &list);
};

Tree::Tree(int data) {
    root = new Node(data, NULL);
    nodeList.push_back(root);
}

int Tree::find(int data, vector<Node *> &list) {
    // 노드가 없으면 -1
    for (int i = 0; i < list.size(); ++i) {
        if (list[i]->data == data)
            return i;
    }
    return -1;
}

void Tree::insertNode(int parent, int data) {
    if (find(data, nodeList) != -1) {
        cout << -1 << endl;
        return;
    }
    if (find(parent, nodeList) == -1) {
        cout << -1 << endl;
        return;
    }
    Node* parNode = nodeList[find(parent, nodeList)];
    Node* newNode = new Node(data, parNode);

    nodeList[find(parent, nodeList)]->childList.push_back(newNode);
    nodeList.push_back(newNode);
}

void Tree::deleteNode(int data) {
    if (find(data, nodeList) == -1) {
        cout << -1 << endl;
        return;
    }
    int idx = find(data, nodeList);
    Node *delNode = nodeList[idx];
    Node *parNode = delNode->parent;

    for (int i = 0; i < delNode->childList.size(); ++i) {
        delNode->childList[i]->parent = parNode;
        parNode->childList.push_back(delNode->childList[i]);
    }

    vector<Node *> &child = parNode->childList;
    child.erase(child.begin() + find(data, child));
    nodeList.erase(nodeList.begin() + idx);
    delete delNode;
}

void Tree::printParent(int data) {
    int idx = find(data, nodeList);
    if (find(data, nodeList) == -1) {
        cout << -1 << endl;
        return;
    }
    cout << nodeList[idx]->parent->data << endl;
}

void Tree::printChild(int data) {
    int idx = find(data, nodeList);
    if (idx == -1) {
        cout << -1 << endl;
        return;
    }

    vector<Node *> &child = nodeList[idx]->childList;
    if (child.size() == 0) {
        cout << -1 << endl;
        return;
    }

    for (int i = 0; i < child.size(); ++i) {
        cout << child[i]->data << ' ';
    }
    cout << endl;
}

void Tree::min_maxChild(int data) {
    int idx = find(data, nodeList);
    if (idx == -1) {
        cout << -1 << endl;
        return;
    }
    vector<Node *> &child = nodeList[idx]->childList;
    if (child.size() < 2) {
        cout << -1 << endl;
        return;
    }

    int max = 0;
    int min = 10'002;
    for (int i = 0; i < child.size(); ++i) {
        int tmp = child[i]->data;
        if (max < tmp) {
            max = tmp;
        }
        if (min > tmp){
            min = tmp;
        }
    }

    cout << max + min << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    Tree *tree = new Tree(1);

    string cmd;

    int M;
    cin >> M;
    while (M--) {
        cin >> cmd;
        if (cmd == "insert") {
            int x, y;
            cin >> x >> y;
            tree->insertNode(x, y);
        }
        else if (cmd == "delete") {
            int x;
            cin >> x;
            tree->deleteNode(x);
        }
        else if (cmd == "parent") {
            int x;
            cin >> x;
            tree->printParent(x);
        }
        else if (cmd == "child") {
            int x;
            cin >> x;
            tree->printChild(x);
        }
        else if (cmd == "min_maxChild") {
            int x;
            cin >> x;
            tree->min_maxChild(x);
        }
    }

    return 0;
}