[자료 구조] C++ Preorder 구현

#include <iostream>
#include <vector>
#include <string>
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);
    Node* getRoot();
    void insertNode(int parent, int data);
    void preOrder(Node* curNode);
    int depth(Node* curNode);

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);
}

Node* Tree::getRoot() {
    return root;
}

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

void Tree::insertNode(int parent, int data) {
    int idx = find(parent, nodeList);
    if (idx != -1) {
        vector<Node*>& child = nodeList[idx]->childList;
        Node* newNode = new Node(data, nodeList[idx]);
        child.push_back(newNode);
        nodeList.push_back(newNode);
    }
}

void Tree::preOrder(Node* curNode) {
    vector<Node*>& child = curNode->childList;
    if (child.size() == 0) {
        cout << depth(curNode) << ' ';
    }
    else {
        cout << child.size() << ' ';
        for (int i = 0; i < child.size(); ++i) {
            preOrder(child[i]);
        }
    }
}

int Tree::depth(Node* curNode) {
    Node* nextNode = curNode->parent;
    int depth = 0;
    while (nextNode != NULL) {
        depth++;
        nextNode = nextNode->parent;
    }
    return depth;
}

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

    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int N;
        cin >> N;
        Tree* tree = new Tree(1);
        for (int j = 0; j < N - 1; ++j) {
            int x, y;
            cin >> x >> y;
            tree->insertNode(x, y);
        }
        tree->preOrder(tree->getRoot());
    }

    return 0;
}