[자료구조] TREE

아.. 트리 어렵다 어려워 

오늘은 어려워도 내일은 안어려웠으면 좋겠다는 마음을 담아 정리해본닷... 킁

 

[백준 11725] 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

#include <cstdio>
#include <list>
int N;
std::list<int> Tree[100000 + 2];

int ans[100000 + 2];
bool visited[100000 + 2];


void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N - 1; i++) {
		int u = 0; int v = 0;
		scanf("%d %d", &u, &v);
		Tree[u].push_back(v);
		Tree[v].push_back(u);
	}
}

void DFS(int n)
{
	visited[n] = true;

	for (int nn : Tree[n]) {
		if (visited[nn]) continue;
		ans[nn] = n;
		DFS(nn);
	}
}

void output(void)
{
	for (int i = 2; i <= N; i++) {
		printf("%d\n", ans[i]);
	}
}

int main()
{
	input();
	DFS(1);
	output();
	return 0;
}

1. 트리는 무향그래프이기 때문에 input 받을 때 u와 v에 대하여 양방향으로 push_back 해준다. 

2. 리스트에서 n에 인접한 노드들을 하나씩 꺼내 방문했다면 무시하고, 방문하지 않았다면 ans 배열의 nn 인덱스 자리에 n 값을 저장한다. nn의 부모노드가 n이 된다는 것이다. 이러한 로직이 가능한 이유는, DFS를 처음 콜할 때 최상단의 루트노드부터 순차적으로 뎁스를 내려가며 탐색하기 때문이다. 

3. 그리고 nn에 대하여 DFS를 콜하여 해당 노드에 인접한 노드들을 탐색해 나간다. 

 

 

[백준 1991] 트리 순회

"이진트리"
- 트리의 자식을 두개까지만 연결하는 경우 

"완전이진트리"
- 마지막 뎁스를 제외하고 모든 뎁스들이 완전히 채워져 있는 경우 
- 힙(heap) 구현 시 사용한다.

"전위순회(pre-order)"
: 루트 -> 왼쪽 -> 오른쪽
: 즉, 루트 노드를 먼저 보고 그 후 왼쪽 자식을 중심으로 한 서브 트리를 탐색한다. 그리고 그게 끝나면 오른쪽 자식을 중심으로 한 서브트리를 탐색한다. 

"중위순회(in-order)"
: 왼쪽 -> 루트 -> 오른쪽 

"후위순회(post-order)"
: 왼쪽 -> 오른쪽 -> 루트

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

// 구조체로 풀기 
#include <cstdio>
#include <vector>
int N;
struct _st
{
	char l;
	char r;
}Tree[26 + 2];


void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		char node; char left; char right;
		scanf(" %c %c %c", &node, &left, &right);
		Tree[node].l = left;
		Tree[node].r = right;
		//printf("%c %c %c\n", node, Tree[node].l, Tree[node].r);
	}
}

void pre_order(char n)	// 전위 순회 : 루트 -> 왼 -> 오
{
	if (n == '.') return;
	printf("%c", n);
	pre_order(Tree[n].l);
	pre_order(Tree[n].r);
}

void in_order(char n)	// 중위 순회 : 왼 -> 루트 -> 오
{
	if (n == '.') return;
	in_order(Tree[n].l);
	printf("%c", n);
	in_order(Tree[n].r);
}

void post_order(char n)		// 후위 순회 : 왼 -> 오 -> 루트
{
	if (n == '.') return;
	post_order(Tree[n].l);
	post_order(Tree[n].r);
	printf("%c", n);
}


int main()
{
	input();
	pre_order('A');
	printf("\n");
	in_order('A');
	printf("\n");
	post_order('A');
	printf("\n");
	return 0;
}

// 맵으로 풀기
#include <cstdio>
#include <unordered_map>
int N;

using namespace std;

struct _st
{
	char l;
	char r;
};

unordered_map<char, _st> Tree;


void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		char node; char left; char right;
		scanf(" %c %c %c", &node, &left, &right);
		Tree.insert({ node,{ left, right} });
	}
}


void pre_order(char n)
{
	if (n == '.') return;
	printf("%c", n);
	pre_order(Tree[n].l);
	pre_order(Tree[n].r);
}


void in_order(char n)
{
	if (n == '.') return;
	in_order(Tree[n].l);
	printf("%c", n);
	in_order(Tree[n].r);
}


void post_order(char n)
{
	if (n == '.') return;
	post_order(Tree[n].l);
	post_order(Tree[n].r);
	printf("%c", n);
}

int main()
{
	input();
	pre_order('A');
	printf("\n");
	in_order('A');
	printf("\n");
	post_order('A');
	printf("\n");
	return 0;
}