트리(조직도 구조 만들기)

"트리"는 계층적인 자료구조를 표현하기 위해서 사용한다. 이진트리를 구현해보자.

이진트리는 하나의 노드에 두 개의 자식노드를 가질 수 있다.

데이터가 저장된 부분을 노드(node)라고 한다. 노드와 노드 사이를 잇는 선을 간선(edge)라고한다.

회사의 조직도를 구현해본다. 예를 들어서 다음 그림과 같은 모습이다.

 

 

#include <iostream>

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)
	{
		if (root == NULL)
			return NULL;

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

		auto firstFound = org_tree::find(root->first, value);

		if (firstFound != NULL)
			return firstFound;

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

	// 루트 노드의 first와 second 둘 중 빈 곳이 있으면 값을 삽입하는 함수
	bool addSubordinate(const std::string& manager, const std::string& subordinate)
	{
		auto managerNode = org_tree::find(root, manager);

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

		if (managerNode->first && managerNode->second)
		{
			std::cout << manager << " 아래에 " << subordinate << "을(를) 추가할 수 없습니다." << std::endl;
			return false;
		}
		if (!managerNode->first)
			managerNode->first = new node{ subordinate, NULL, NULL };
		else
			managerNode->second = new node{ subordinate, NULL, NULL };

		std::cout << manager << " 아래에 " << subordinate << "을(를) 추가했습니다." << std::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("부사장", "재무부장");
}

실제 구현된 모습을 그림으로 표현하면 다음과 같다.