트리 - 상하 반전된 형태

 

 

트리

일반적인 트리 (뿌리 모양)

뒤집은 트리 (나뭇가지 모양)

 

 

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

트리이 계층 구조를 화면에 도식적으로 나타내려면 말 그대로 나무 형태로 나타낼 수 있으며,

이때 에지는 나뭇가지처럼 표현된다.

트리의 중심이 되는 노드를 루트 노드라고 부르고, 이 노드는 보통 가장 맨 위에 나타낸다.

즉, 트리 구조를 그림으로 나타낼 때는 실제 나무와는 정 반대로 뿌리 모양처럼 생기게 된다.

그 외에도 다양한 트리 모양이 있다.

 

 

 

 

연습 문제  : 조직도 구조 만들기

 

 

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

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

		auto firstFound = org_tree::find(root->second, value);
	}
	
	// 해당 함수는 원소(부하 직원)를 정상적으로 삽입하면 true를, 실패하면 false를 반환한다.
	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("부사장", "재무부장");

	return 0;
}