트리(Tree)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

트리의 주요 용어

• 루트(Root)가 가장 위에 있는 상하 반전 형태이다.
• 노드(Node)와 간선(Edge)을 활용해 계층을 구성한다.
• 부모(Parent) 노드와 자식(Child) 노드를 가질 수 있다.
• 부모의 다른 자식 노드를 형제(Sibling) 노드라고 한다.
• 특정 노드를 루트로 하는 부트리(Subtree)가 존재한다.
• 자식이 없는 가장 끝의 노드들을 단말(Leaf) 노드라고 한다.
• 단말 노드가 아닌 노드를 내부(Internal) 노드라고 한다.
• 부모 노드와 그 부모들을 선조(Ancestor)라고 한다.
• 자식 노드와 그 자식들을 자손(Descendant)라고 한다.
• 자신을 포함한 모든 자손 노드의 개수를 노드의 크기(Size)라고 한다.
• 루트에서 해당 특정 노드까지의 간선 개수를 노드의 깊이(Depth)라고 한다.
• 특정 깊이를 갖는 노드의 집합을 레벨(Level)이라고 한다.
• 특정 노드의 부트리 혹은 자식 노드의 개수를 노드의 차수(Degree)라고 한다.
• 트리의 최대 차수를 트리의 차수(Degree of tree)라고 한다.
• 트리의 최대 깊이를 트리의 높이(Height)라고 한다.
• 서로 독립인 트리의 집합을 숲(Forest)이라고 한다.

 

트리의 특징

• 계층 구조이다.
• 연결된 비순환 그래프(Connected Acyclic Graph)의 한 종류이다.
  (모든 노드가 연결되어 있으며 루프가 존재하지 않는다.)
• N개의 노드로 구성된 트리는 N - 1개의 간선을 갖는다.
• 루트에서 특정 노드로 가는 경로(Path)는 유일하다.
• 전위순회, 중위순회, 후위순회를 통해 순회할 수 있다.

 

 

트리의 순회

• 전위 순회 (Pre-order)
  부모 노드 > 왼쪽 자식 > 오른쪽 자식의 우선순위를 가지며 부모 노드를 먼저 방문
• 중위 순회 (In-order)
  왼쪽 자식 > 부모 노드 > 오른쪽 자식의 우선순위를 가지며 부모 노드를 중간에 방문
• 후위 순회 (Post-order)
  왼쪽 자식 > 오른쪽 자식 > 부모 노드의 우선순위를 가지며 부모 노드를 마지막에 방문
• 레벨 순회 (Level-order)
  부모 노드 -> 왼쪽 자식 -> 오른쪽 자식 순으로 낮은 레벨의 왼쪽부터 차례로 방문한다.
  
  

 

 

깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)

• 깊이 우선 탐색(DFS)
  순회 우선순위에 따라 가장 깊이가 깊은 노드부터 재귀적으로 방문한다.
• 너비 우선 탐색(BFS)
  자식을 먼저 확인하여 같은 레벨을 우선으로 방문한다.

 

#include <iostream>
#include <queue>

using namespace std;

struct node
{
    string position;    // 직책
    node* first;        // 첫 번째 부하 직원
    node* second;       // 두 번째 부하 직원
};

struct org_tree
{
    node* root;

    // 조직 생성 함수
    static org_tree create_org_structure(const string& pos)
    {
        org_tree tree;
        tree.root = new node{pos, nullptr, nullptr};

        return tree;
    }

    // 직책으로 검색 (전위순회)
    static node* find(node* root, const string& pos)
    {
        node* first;

        if (root == nullptr)
            return nullptr;

        if (root->position == pos)
            return root;

        if ((first = find(root->first, pos)) != nullptr)
            return first;
        else
            return find(root->second, pos);
    }

    // manager 직책을 갖는 상사의 부하 직원으로 subordinate 추가
    bool addSubordinate(const string& manager, const string& subordinate)
    {
        node* managerNode = find(root, manager);
        node* subordinateNode;

        // 해당 직책의 상사가 존재하지 않는다.
        if (managerNode == nullptr)
            return false;

        // 이미 2명의 부하 직원을 갖고 있다.
        if (managerNode->first && managerNode->second)
            return false;

        subordinateNode = new node{subordinate, nullptr, nullptr};

        if (managerNode->first == nullptr)  // 첫 번째 부하 직원으로 삼을 수 있다.
            managerNode->first = subordinateNode;
        else    // 첫 번째 부하 직원은 있으므로 두 번째로 삼을 수 있다.
            managerNode->second = subordinateNode;

        return true;
    }

    // 전위 순회
    static void preOrder(node* start)
    {
        if (start == nullptr)
            return;

        cout << start->position << ", ";
        preOrder(start->first);
        preOrder(start->second);
    }

    // 중위 순회
    static void inOrder(node* start)
    {
        if (start == nullptr)
            return;

        preOrder(start->first);
        cout << start->position << ", ";
        preOrder(start->second);
    }

    // 후위 순회
    static void postOrder(node* start)
    {
        if (start == nullptr)
            return;

        preOrder(start->first);
        preOrder(start->second);
        cout << start->position << ", ";
    }

    // 레벨 순회
    static void levelOrder(node* start)
    {
        if (start == nullptr)
            return;

        queue<node*> que;
        que.push(start);

        while (!que.empty())
        {
            size_t size = que.size();
            
            for (int i = 0; i < size; ++i)
            {
                node* current = que.front();
                que.pop();

                // 부모 노드를 방문하고
                cout << current->position << ", ";

                // 자식 노드를 큐에 삽입한다.
                if (current->first)
                    que.push(current->first);

                if (current->second)
                    que.push(current->second);

                // front에 가까울 수록 레벨이 낮은 노드가 위치한다.
            }

            cout << endl;
        }
    }
};

void main()
{
    org_tree 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("부사장", "재무부장");

    cout << "[전위 순회]" << endl;
    org_tree::preOrder(tree.root); cout << endl << endl;

    cout << "[중위 순회]" << endl;
    org_tree::inOrder(tree.root); cout << endl << endl;

    cout << "[후위 순회]" << endl;
    org_tree::postOrder(tree.root); cout << endl << endl;

    cout << "[레벨 순회]" << endl;
    org_tree::levelOrder(tree.root);
}

 

출력

[전위 순회]
CEO, 부사장, IT부장, 보안팀장, 앱개발팀장, 마케팅부장, 물류팀장, 홍보팀장,

[중위 순회]
부사장, IT부장, 보안팀장, 앱개발팀장, 마케팅부장, 물류팀장, 홍보팀장, CEO,

[후위 순회]
부사장, IT부장, 보안팀장, 앱개발팀장, 마케팅부장, 물류팀장, 홍보팀장, CEO,

[레벨 순회]
CEO,
부사장,
IT부장, 마케팅부장,
보안팀장, 앱개발팀장, 물류팀장, 홍보팀장,