[트리(Tree)] 이진 트리 형태의 회사 조직도와 트리 순회 방법(중위/전위/후위, 레벨 순회)

reference: "전문가를 위한 C++" / 마크 그레고리

트리는 노드와 노드 사이를 연결하는 에지를 이용하여 계층을 구성함.

회사 조직도 트리로 나타내기(이진 트리 형태)

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

// 최대 2명의 부하 조직원을 거느릴 수 있음
struct node {
	string position;
	node* first;
	node* second;
};

// 조직 트리
struct org_tree {
	node* root;

	// 조직 트리 생성함수. 루트는 CEO
	// 새로운 트리를 만드는 정적(static) 함수
	static org_tree create_org_tree(const string& pos) {
		org_tree tree;
		tree.root = new node{ pos, NULL, NULL };
		return tree;
	}

	// find(): 특정 직책의 이름을 받아서 이에 해당하는 노드를 반환하는 함수
	static node* find(node* root, const string& value) {
		if (root == NULL)
			return NULL;

		if (root->position == value)
			return root;
		
        
        // 왼족 서브트리 탐색
		auto firstFound = org_tree::find(root->first, value);
		if (firstFound != NULL)
			return firstFound;
        // 왼쪽 서브트리에 없다면 오른쪽 서브트리 탐색
		else
			return org_tree::find(root->second, value);
	}

	// 새로운 원소(부하 직원)를 추가하는 삽입 함수
    // 새로운 부하 직원의 상사도 인자로 전달
	// find() 함수 사용
	bool addSubordinate(const string& manager, const string& subordinate) {
		auto managerNode = org_tree::find(root, manager);

		if (!managerNode) {
			cout << manager << "을(를) 찾을 수 없습니다." << endl;
			return false;
		}

		// 이미 두 부하가 존재한다면
		if (managerNode->first && managerNode->second) {
			cout << manager << " 아래에 새로운 직원을 추가할 수 없음. " << endl;
			return false;
		}

		if (!managerNode->first) 
			managerNode->first = new node{ subordinate, NULL, NULL };
		else
			managerNode->second = new node{ subordinate, NULL, NULL };

		cout << subordinate << "를 " << managerNode << " 아래에 추가." << endl;
		return true;
	}
};

테스트

int main() {
				// CEO가 루트노드인 트리 생성
    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("마케팅부장", "홍보팀장");
    
    ...
}

---

중위 순회, 전위 순회, 후위 순회

	...
    
	/* 전위 순회: "가운데" -> 왼쪽 -> 오른쪽
    * 
    * 전위 순회는 항상 부모 노드를 방문한 다음 왼쪽 자식 노드, 
    * 오른쪽 자식 노드를 차례대로 방문한다. 
    * '전위(pre)'의 뜻은 상위 노드를 하위노드보다 먼저 방문함을 뜻함.
    */ 
	static void preOrder(node* start) {
		if (!start)
			return;
		
		// 가운데
		cout << start->position << " ";

		// 왼쪽
		preOrder(start->first);
        // 오른쪽
		preOrder(start->second);
	}
    // CEO -> 부사장 -> IT부장 -> 보안팀장 -> 앱개발 팀장
    // -> 마케팅부장 -> 물류팀장 -> 홍보팀장



	/* 중위 순회: 왼쪽 -> "가운데" -> 오른쪽
    *
    * 왼쪽 노드를 먼저 방문하고, 그 다음에는 현재 노드, 
    * 마지막으로 오른쪽 노드를 방문 
    */
	static void inOrder(node* start) {
		if (!start)
			return;

		inOrder(start->first);
		cout << start->position << " ";
		inOrder(start->second);
	}
    // 보안팀장 -> IT부장 -> 앱개발 팀장 -> 부사장 
    // -> 물류팀장 -> 마케팅부장 -> 홍보팀장 -> CEO
    
    

	/* 후위 순회: 왼쪽 -> 오른쪽 -> "가운데"
    *
    * 두 자식 노드를 먼저 방문한 후, 현재 노드(부모 노드)를 방문
    */
	static void postOrder(node* start) {
		if (!start)
			return;

		postOrder(start->first);
		postOrder(start->second);
		cout << start->position << " ";
	}
    // 보안팀장 -> 앱개발팀장 -> IT부장 -> 물류팀장
    // -> 홍보팀장 -> 마케팅부장 -> 부사장 -> CEO
};

레벨 순회

트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽 노드에서 오른쪽 노드 순서로 방문.
트리의 루트 노드부터 단계별로 차례대로 나열하는 것
ex)
CEO
부사장
IT부장 마케팅부장
보안팀장 앱개발팀장 물류팀장 홍보팀장

=> 큐(queue)를 활용한다!

	...
    
	// 레벨 순회
	// #include <queue>
	static void levelOrder(node* start) {
		if (!start)
			return;

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

		while (!q.empty()) {
			// 한 번의 레벨
			int size = q.size();	// 하나의 단계에서 크기를 구함. 
            						// ex) IT부장 마케팅부장 => size = 2

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