[C++] 트리 순회(Tree Traversal)

트리 순회(Traversal)

트리 순회 방법

• 트리 순회 방법은 다음과 같이 4가지가 있음.
  • 전위 순회(Preorder Traversal)
  • 중위 순회(In-Order Traversal)
  • 후위 순회(Post-Order Traversal)
  • 레벨 순서 순회(Level Order Traversal)

 

조직도 계층을 표현하는 이진 트리

 

전위 순회(Preorder Traversal)

• 재귀적 인 방식으로 다음의 노드를 방문함.
  • ① 현재 노드 (C)
  • ② 현재 노드의 왼쪽 하위 노드 (L)
  • ③ 현재 노드의 오른쪽 하위 노드 (R)
• 전위(Pre)
  • 상위 노드를 하위 노드보다 먼저 방문한다는 뜻
• 전위 순회는 항상 부모 노드 를 방문한 다음, 왼쪽자식 노드, 오른쪽 자식 노드를 차례로 방문함.
• 이러한 방식의 순회를 루트 노드에서만 수행하는 것이 아니라, 루트 노드 아래의 모든 서브 트리 에 대해서도 수행함.
• 구현

static void preOrder(node* start) {
    if (!start) {
        return;
    }
    std::cout << start->position <<", ";    // (C)
    preOrder(start->first);                 // (L)
    preOrder(start->second);                // (R)
}

CEO, 부사장, IT부장, 보안팀장, 앱개발팀장, 마케팅부장, 물류팀장, 홍보팀장

 

중위 순회(In-Order Traversal)

• 재귀적 인 방식으로 다음의 노드를 방문함.
  • ① 왼쪽 노드 (L)
  • ② 현재 노드 (C)
  • ③ 오른쪽 노드 (R)
• 구현

static void inOrder(node* start) {
    if (!start) {
        return;
    }
    inOrder(start->first);                  // (L)
    std::cout << start->position << ", ";   // (C)
    inOrder(start->second);                 // (R)
}

보안팀장, IT부장, 앱개발팀장, 부사장, 물류팀장, 마케팅부장, 홍보팀장, CEO

 

후위 순회(Post-Order Traversal)

• 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문함.
• 재귀적 인 방식으로 다음의 노드를 방문함.
  • ① 왼쪽 노드 (L)
  • ② 오른쪽 노드 (R)
  • ③ 현재 노드 (C)
• 구현

static void postOrder(node* start) {
    if (!start) {
        return;
    }
    postOrder(start->first);                // (L)
    postOrder(start->second);               // (R)
    std::cout << start->position << ", ";   // (C)
}

보안팀장, 앱개발팀장, IT부장, 물류팀장, 홍보팀장, 마케팅부장, 부사장, CEO

 

레벨 순서 순회(Level Order Traversal)

• 트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽 노드에서 오른쪽 노드 순서로 방문함.
  • 트리의 루트 노드부터 단계별로 차례대로 나열하는 것과 같음.
• 다른 트리 순회 방법과는 달리, 레벨 순서 순회 방법은 현재 노드에 직접 연결되지 않은 노드 로 이동함.
  • 이러한 경우, 재귀를 사용하지 않고 구현하는 것이 더 쉬움.

• 구현
  • 현재 레벨의 노드를 방문할 때, 다음 레벨 노드를 미리 큐에 추가하는 방식
    • 먼저 루트 노드를 방문하고, 그 다음에 자식 노드를 방문함.
      • 자식 노드를 방문할 때, 해당 노드의 자식 노드를 모두 큐(Queue) 에 추가함.
    • 현재 레벨의 모든 노드 방문이 끝나면, 큐에 저장된 노드를 꺼내어 방문함.
    • 이러한 작업을 큐가 완전히 빌 때까지 반복

static void levelOrder(node* start) {
    if (!start) {
        return;
    }

    std::queue<node*> q;
    q.push(start);

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto current = q.front();
            q.pop();

            std::cout << current->position << ", ";
            if (current->first) {
                q.push(current->first);
            }
            if (current->second) {
                q.push(current->second);
            }
        }
        std::cout << std::endl;
    }
}

CEO,
부사장,
IT부장, 마케팅부장,
보안팀장, 앱개발팀장, 물류팀장, 홍보팀장,

 

코드

#include <iostream>
#include <queue>

struct node {
    std::string position;
    node* first;
    node* second;
};

struct org_tree {
    node* root;

    static org_tree create_org_structure(const std::string& pos) {
        org_tree tree;
        tree.root = new node {pos, NULL, NULL};
        return tree;
    }

    static node* find(node* root, const std::string& value) {
        ////// 1. 루트 노드가 존재하지 않을 경우
        if (root == NULL) {
            return NULL;
        }

        ////// 2. 루트 노드가 존재할 경우
        //// (1) 루트 노드에 찾고자 하는 값이 있을 경우
        if (root->position == value) {
            return root;
        }

        //// (2) 루트 노드에 찾고자 하는 값이 없을 경우
        // [1] 왼쪽 서브 트리 검사
        auto firstFound = org_tree::find(root->first, value);   

        if (firstFound != NULL) {
            return firstFound;
        }

        // [2] 오른쪽 서브 트리 검사
        return org_tree::find(root->second, value);   
    }

    bool addSubordinate(const std::string& manager, const std::string& subordinate) {
        auto managerNode = org_tree::find(root, manager);

        //// 1. 부하 직원 추가 실패
        // 상사 직원이 없을 경우
        if (!managerNode) {
            std::cout << manager << "을(를) 찾을 수 없습니다: " << std::endl;
            return false;
        }

        // 상사 직원 밑에 이미 2명의 부하 직원이 있을 경우
        if (managerNode->first && managerNode->second) {
            std::cout << manager << " 아래에 " << subordinate << "을(를) 추가할 수 없습니다." << std::endl;
            return false;
        }

        //// 2. 부하 직원 추가 성공
        // 상사 직원 밑에 부하 직원이 없을 경우
        if (!managerNode->first) {    // (1) 첫번째(first) 부하 직원이 없을 경우
            managerNode->first = new node {subordinate, NULL, NULL};
        }
        else {    // (2) 2번째(second) 부하 직원이 없을 경우
            managerNode->second = new node {subordinate, NULL, NULL};
        }
        std::cout << manager << " 아래에 " << subordinate << "을(를) 추가했습니다." << std::endl;

        return true;
    }

    static void preOrder(node* start) {
        if (!start) {
            return;
        }
        std::cout << start->position <<", ";    // (C)
        preOrder(start->first);                 // (L)
        preOrder(start->second);                // (R)
    }

    static void inOrder(node* start) {
        if (!start) {
            return;
        }
        inOrder(start->first);                  // (L)
        std::cout << start->position << ", ";   // (C)
        inOrder(start->second);                 // (R)
    }

    static void postOrder(node* start) {
        if (!start) {
            return;
        }
        postOrder(start->first);                // (L)
        postOrder(start->second);               // (R)
        std::cout << start->position << ", ";   // (C)
    }

    static void levelOrder(node* start) {
        if (!start) {
            return;
        }

        std::queue<node*> q;
        q.push(start);

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto current = q.front();
                q.pop();

                std::cout << current->position << ", ";
                if (current->first) {
                    q.push(current->first);
                }
                if (current->second) {
                    q.push(current->second);
                }
            }
            std::cout << std::endl;
        }
    }
};

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

    // 노드 추가
    std::cout << "[노드 추가]" << std::endl;
    tree.addSubordinate("CEO", "부사장");
    tree.addSubordinate("부사장", "IT부장");
    tree.addSubordinate("부사장", "마케팅부장");
    tree.addSubordinate("IT부장", "보안팀장");
    tree.addSubordinate("IT부장", "앱개발팀장");
    tree.addSubordinate("마케팅부장", "물류팀장");
    tree.addSubordinate("마케팅부장", "홍보팀장");

    std::cout << std::endl;

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

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

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

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

    return 0;
}

 

[노드 추가]
CEO 아래에 부사장을(를) 추가했습니다.
부사장 아래에 IT부장을(를) 추가했습니다.      
부사장 아래에 마케팅부장을(를) 추가했습니다.  
IT부장 아래에 보안팀장을(를) 추가했습니다.    
IT부장 아래에 앱개발팀장을(를) 추가했습니다.  
마케팅부장 아래에 물류팀장을(를) 추가했습니다.
마케팅부장 아래에 홍보팀장을(를) 추가했습니다.

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

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

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

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