[자료구조] 트리

트리

• 노드로 이루어진 자료구조.
• 배열, 리스트와 같은 선형 자료구조로 표현할 수 없는 문제를 해결할 때 사용.
• 계층적 문제(hierarchical problem), 순환 종속성 문제(cyclic dependency) 등이 있음.

계층도의 예시

• 다음과 같은 계층도는 일반적인 vector, array로 표현이 불가능 함.
• 위와 같이 CEO, 부사장과 같이 데이터가 저장된 부분을 Node라고 하며, 노드와 노드 사이를 잇는 선을 Edge라고 함.
• 계층도는 비순환 그래프이며, 방향성이 있는 그래프의 한 종류이다.

트리 구현

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

// 직책과 바로 밑의 부하직원을 나타내는 node 
struct node 
{
    string position;
    node* first;
    node* second;
};

struct org_tree 
{
    // tree에 기반이 되는 root를 생성.
    node* root;

    // root노드를 설정하는 함수.
    static org_tree create_org_structure(const string& pos) 
    {
        org_tree tree;
        tree.root = new node {pos, NULL, NULL};
        return tree;
    }

    // node가 있는지 없는지 확인하는 함수.
    static node* find(node* root, const string& value) 
    {
        // root가 없을 경우 NULL을 리턴.
        if (root == NULL) 
            return NULL;
        // root의 position 값이 찾는 값과 같을경우 root를 리턴.
        if (root->position == value)
            return root;

        // 찾는 값이 root가 아닐 경우 재귀를 통해 first node를 탐색.
        auto firstFound = find(root->first, value);

        if(firstFound != NULL)
            return firstFound;

        // 찾는 값이 firstFound가 아닐 경우 재귀를 통해 second node를 탐색.
        return find(root->second, value);
    }

    // 트리에 간선 추가
    bool addSubordinate(const string& manager, const string subordinate) 
    {
        auto managerNode = find(root, manager);

        // managerNode를 못 찾을 경우 추가 X.
        if(!managerNode)
        {
            cout << manager << "을 찾을 수 없습니다." << endl;
            return false;
        }

        // managerNode에 first, second값이 있다면 추가 X.
        if(managerNode->first && managerNode->second)
        {
            cout << manager << " 아래에 " << subordinate << "을 추가할 수 없습니다." << endl;
            return false;
        }

        // 비어있는 node에 삽입.
        if(!managerNode->first) 
            managerNode->first = new node {subordinate, NULL, NULL};
        else 
            managerNode->second = new node {subordinate, NULL, NULL};

        cout << manager << " 아래에 " << subordinate << "을 추가했습니다." << endl;

        return true;
    }
};

int main()
{
    auto tree = org_tree::create_org_structure("CEO");

    tree.addSubordinate("CEO", "부사장");
    tree.addSubordinate("부사장", "IT부장");
    tree.addSubordinate("부사장", "마케팅부장");
    tree.addSubordinate("IT부장", "보안팀장");
    tree.addSubordinate("IT부장", "웹개발팀장");
    tree.addSubordinate("마케팅부장", "물류팀장");
    tree.addSubordinate("마케팅부장", "홍보팀장");
    tree.addSubordinate("부사장", "재무부장");
}

결과 값