[C++] Binary Tree: 순회

 이진 트리는 각 노드가 최대 두 개의 자식 노드(왼쪽과 오른쪽)를 가질 수 있는 계층적 자료 구조이다.

 

이 구조에서 모든 노드는 데이터를 저장하며, 주로 탐색, 정렬 작업에 효율적이다. 이진 트리는 다양한 형태(예: 이진 탐색 트리, AVL 트리)로 존재한다.

 

우선 가장 기본적인 형태의 이진 트리로 아래와 같은 조직도를 구현하려고 한다.

 

 

코드와 함께 살펴보자.

#include <iostream>
#include <deque>
#include <queue>

using namespace std;

struct node {
    string position; // 각 노드는 'position'이라는 문자열을 가지며, 직책을 나타낸다.
    node* first;     // 'first' 포인터는 첫 번째 자식 노드를 가리킨다.
    node* second;    // 'second' 포인터는 두 번째 자식 노드를 가리킨다.
};

struct org_tree {
    node* root;      // 'org_tree'는 'root' 노드 포인터를 가지며, 트리의 시작점을 나타낸다.

    /* root node 생성 */
    static org_tree create_org_structure(const string& pos) {
        org_tree tree;
        tree.root = new node{pos, NULL, NULL}; // 새로운 트리를 생성하고, 루트 노드를 초기화한다.
        return tree;
    }

    /* root, first, second 순으로 검색 */
    static node* find(node* root, const string& value) {
        // 주어진 직책의 이름을 가진 노드를 찾는 함수이다.
        if(root == nullptr) return nullptr;

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

        auto firstFound = org_tree::find(root -> first, value);
        if(firstFound != nullptr) return firstFound;

        return org_tree::find(root -> second, value);
    }

    bool addSubordinate(const string& manager, const string& subordinate) {
        // 특정 직책 아래에 새로운 하위 직책을 추가하는 함수이다.
        auto managerNode = org_tree::find(root, manager);

        // 관리자 노드가 존재하지 않을 경우 false를 반환한다.
        if(!managerNode) {
            cout << manager << "을 찾을 수 없습니다: " << endl;
            return false;
        }

        // 두 자식 노드가 이미 존재하는 경우, 추가할 수 없다.
        if(managerNode->first && managerNode->second) {
            cout << manager << " 아래에 " << subordinate << "을 추가할 수 없습니다. " << endl;
            return false;
        }

        // 첫 번째 또는 두 번째 자식 노드에 새로운 노드를 추가한다.
        if(!managerNode->first)
            managerNode->first = new node {subordinate, NULL, NULL};
        else
            managerNode->second = new node{subordinate, NULL, NULL};

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

        return true;
    }

    // 각각의 순회 함수들은 트리를 다양한 방법으로 탐색하여 출력한다.
    /* pre order: root -> first -> second
	 *
	 * out: CEO, 부사장, IT부장, 보안팀장, 앱개발팀장, 마케팅부장, 물류팀장, 홍보팀장
	 * */
	static void preOrder(node* start) {
		if(!start) return;

		cout << start -> position << ", ";

		preOrder(start->first);
		preOrder(start->second);
	}

	/* in order: first -> root -> second
	 *
	 * out: 보안팀장, IT부장, 앱개발팀장, 부사장, 물류팀장, 마케팅부장, 홍보팀장, CEO
	 * */
	static void inOrder(node* start) {
		if(!start) return;

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

	/* post order: first -> second -> root
	 *
	 * out: 보안팀장, 앱개발팀장, IT부장, 물류팀장, 홍보팀장, 마케팅부장, 부사장, CEO
	 * */
	static void postOrder(node* start) {
		if(!start) return;

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

	/* level order: from the top node to bottom. from left to right.
	 *
	 * out:
	 * CEO,
	 * 부사장,
	 * IT부장, 마케팅부장,
	 * 보안팀장, 앱개발팀장, 물류팀장, 홍보팀장
	 *
	 * */
	static void levelOrder(node* start) {
		if(!start) return;

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

				cout << current->position << ", ";

				if(current->first) q.push(current->first);
				if(current->second) q.push(current->second);
			}

			cout << endl;
		}
	}

};

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

	//tree.preOrder(tree.root);
	//tree.inOrder(tree.root);
	//tree.postOrder(tree.root);
	//tree.levelOrder(tree.root);
}

...? indent가 조금 이상하게 잡히네...?

 

 level order만 조금 더 설명을 붙이자면, 먼저 루트 노드를 방문하고, 그 다음에 자식 노드를 방문한다. 자식 노드를 방문할 때, 해당 노드의 자식 노드를 모두 queue에 추가한다. 그리고 나서 현재 레벨의 모든 노드 방문이 끝나면 큐에 저장된 꺼내어 방문한다. 

 

이 작업을 큐가 완전히 빌 때까지 반복하면 level 순회 작업이 완료된다.

 

이진 트리의 원소 순회는 워낙 간단해서... 주석으로 설명한 거 이외에 딱히 설명할 게 없는 거 같다.

 

 

끝!