트리 : 상하 반전된 형태

이선아·2021년 9월 11일

자료 구조와 알고리즘 with c++

목록 보기

3/4

📌 비선형 문제

선형 자료 구조로 표현할 수 없는 대표적인 2가지 문제에는 계층적 문제(hierarchical problem)와 순환 종속성(cyclic dependency) 문제가 있습니다.

☝🏻 계층적 문제

계층적으로 표현되는 이러한 구성의 데이터는 배열, 벡터, 연결 리스트와 같은 자료 구조로 표현하기가 어렵습니다.
이런 형태의 문제를 풀기 위해서는 트리(Tree)라고 불리는 자료 구조를 사용해야 합니다. 데이터가 저장된 부분을 노드(node)라고 부르고, 노드와 노드 사이를 잇는 선을 에지(edge, 간선)라고 합니다.

✌🏻 순환 종속성

비선형 구조를 사용하는 것이 더 좋은 형태인 그래프(graph) 입니다. 친구 관계도를 예로 들면 사람 이름(원소)이 노드에 해당하고, 사람들 사이의 관계는 에지로 표현합니다. 이러한 구조는 SNS 상에서 사람들과의 친구 관계를 나타내는 용도로 자주 사용됩니다. 그래프 구조의 다른 예를 들자면 도시와 도시를 잇는 도로망도 포함이 됩니다.

📌 트리 : 상하 반전된 형태

트리는 노드와 노드 사이를 연결하는 에지를 이용하여 계층을 구성합니다. 트리의 계층 구조를 화면에 도식적으로 나타내면 나무 형태로 나타낼 수 있으며, 에지는 나뭇가지처럼 표현됩니다. 트리의 중심이 되는 노드를 루드 노드(root node)라고 부르고 보통 맨 위에 자리를 잡고 있습니다. 즉 트리 구조를 그림으로 나타내게 되면 실제 나무와는 반대로 뿌리가 맨 위에 위치하는 상하 반전된 형태로 표현합니다.

🔸 계층적 문제와 비슷한 형태의 회사 조직도 코드 구현

코드 보러가기

🔸 트리 순회

트리가 구성되어 있다면 이 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 있습니다.

🔥 1. 전위 순회(preorder traversal)

현재 노드를 먼저 방문, 그 다음 현재 노드의 왼쪽 하위 노드, 마지막으로 현재 노드의 오른쪽 하위 노드를 재귀적 방식으로 방문하는 방법입니다. 위 회사 조직도의 트리를 전위 순회 방식으로 탐색하면

CEO - 부사장 - IT부장 - 보안팀장 - 앱개발팀장 - 마케팅부장 - 물류팀장 - 홍보팀장

전위 순회는 항상 부모 노드를 방문한 후 왼쪽 자식 노드, 오른쪽 자식 노드를 차례로 방문합니다. 이러한 방식의 순회는 루트 노드에서만 수행되는 것이 아닌 루트 노드 아래의 모든 서브 트리에도 적용됩니다.

static void preOrder(node* start) {
	if(!start)
		return;
        
	cout<<start->position<<", ";
    	preOrder(start->first);
    	preOrder(start->second);
}

🔥 2. 중위 순회(in-order traversal)

왼쪽 노드 먼저 방문, 그 다음 현재 노드, 마지막으로 오른쪽 노드를 방문하는 방법입니다. 위 회사 조직도의 트리를 중위 순회 방식으로 탐색하면

보안팀장 - IT부장 - 앱개발팀장 - 부사장 - 물류팀장 - 마케팅부장 - 홍보팀장 - CEO

static void inOrder(node* start) {
	if(!start)
		return;
        
    	inOrder(start->first);
    	cout<<start->position<<", ";
    	inOrder(start->second);
}

🔥 3. 후위 순회(post-order traversal)

두 자식 노드를 먼저 방문한 후, 현재 노드를 방문하는 방법입니다. 위 회사 조직도의 트리를 후위 순회 방식으로 탐색하면

보안팀장 - 앱개발팀장 - IT부장 - 물류팀장 - 홍보팀장 - 마케팅부장 - 부사장 - CEO

static void postOrder(node* start) {
	if(!start)
		return;
        
    	postOrder(start->first);
    	postOrder(start->second);
        cout<<start->position<<", ";
}