자체 제작 트리로 조직도 구현하기

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

위 코드와 같이 자식을 두 개 가지는 것을 이진트리라 한다.
이진 트리를 위한 기본 구조를 만든 뒤
각각의 노드는 다른 두 개의 노드에 대한 링크를 가지게끔 한다.
이를 통해 데이터의 계층 구조를 나타낼 수 있다.
여기서는 노드에 조직도상의 직책만을 저장했지만,
해당 담당자의 이름을 추고할 수도 있고, 모든 직원 정보를 담는 구조체를 데이터에 저장할 수도 있다.
 

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

이 함수는 트리 노드를 만드는 정적 함수이다.
이제 트리 구조를 확장 시키는 기능은 아래의 코드이다.
 
find 함수를 통해 특정 원소를 찾기위해 탐색하여 현재 노드이거나 왼쪽 또는 오른쪽 서브 트리에 있는지 확인하는 것이다.

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

만약 찾고자 하는 원소가 이니라면 왼쪽 서브 트리에서 다시 찾으려고 시도한다.
그래도 해당 원소를 찾지 못한다면 오른쪽 서브 트리도 검사하는 로직이다.
 
마지막은 새로운 원소(= 부하 직원)을 추가하는 삽입 함수이다.

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

아래는 코드 전문이다.

#include <iostream>
#include <queue>
#include <string>

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

struct org_tree
{
	node* root;

	static org_tree create_org_structre(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);
	}

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