트리- 바킹독 유튜브

정의와 성질

그래프를 배운 후 트리를 다시 보면 간선과 정점으로 이루어진 자료구조로 그래프의 특별한 한 종류임을 알 수 있다.

기억해두면 좋은 정의는 아래와 같다.

• 트리는 무방향이면서 사이클이 없는 연결 그래프이다.
• 임의의 두 점을 연결하는 simple path(정점이 중복해서 나오지 않는 경로)가 유일한 그래프
• V개의 정점을 가지고 V-1개의 간선을 가지는 사이클이 없는 연결 그래프

트리에서는 임의의 노드를 루트로 만들 수 있다. → 무방향 그래프에서 하나의 노드를 선택하고 루트로 만들어서 트리 모양을 만들 수 있음

트리에서 BFS

그래프에서 사용하는 BFS와 매우 비슷하지만 BFS를 돌면서 자신의 자식노드만 큐에 넣어주면 된다. 이 말은 곧 자신과 이웃한 정점들에 대해 부모만 빼고 나머지를 전부 큐에 넣으면 됨을 의미하고 그렇기 때문에 visited 배열을 들고 갈 필요가 없이 부모가 누구인지만 저장해주면 된다.

코드예시

from collections import deque

graph = [] # 그래프가 만들어져 있다고 생각했을 때
parent = [] # 노드의 부모값을 저장해둘 배열

def bfs(root:int) -> None:
	queue = deque()
	queue.append(root)
	while queue:
		cur_node = queue.popleft()
		for next_node in graph[cur_node]:
			if parent[cur_node] == next_node: continue
			queue.append(next_node)
			parent[next_node] = cur_node

자식의 depth는 부모의 depth + 1임을 이용해 depth를 구할 수도 있다.

트리에서 DFS

dfs도 bfs와 마찬가지로 연결된 정점들은 1개만 부모이고 나머지는 전부 자식이라는 성질을 이용해 visited 배열을 쓰는 대신 부모 배열과 depth 배열을 채우면서 처리가 가능하다.

코드예시

graph = []
parent = []
depth = []
# 스택 코드
def dfs(root:int) -> None:
	stack = []
	stack.append(root)
	while stack:
		cur_node = stack.pop()
		for next_node in graph[cur_node]:
			if parent[cur_node] == next_node: continue
			stack.append(next_node)
			parent[next_node] = cur_node
			depth[next_node] = depth[cur_node] + 1

# 재귀 코드
def dfs(cur_node:int) -> None:
	for next_node in graph[cur_node]:
		if parent[cur_node] == next_node: continue
		parent[next_node] = cur_node
		depth[next_node] = depth[cur_node] +1
		dfs(next_node)

#단순 순회
def dfs(cur_node:int, par:int) -> None:
	for next_node in graph[cur_node]:
		if par == next_node: continue
		dfs(next_node, cur_node)
		

이진트리의 순회

• 순회방법
  • 레벨순회
    • 높이를 기준으로 순회한다.
    • 따라서 bfs를 통해서 순회가 가능하다.
  • 레벨순회를 제외한 전위, 중위, 후위 순회는 재귀로 구현할 수 있다.
  • 전위 순회
    • 현재정점을 방문한다
    • 왼쪽 전위순회를 한다
    • 오른쪽 전위 순회를 한다
    • 위 순서대로 진행하는 것이 전위 순회 (DFS와 방문순서가 동일하다.)
  • 중위 순회
    • 왼쪽 서브트리를 중위순회한다.
    • 현재정점을 방문한다
    • 오른쪽 서브트리를 중위순회한다.
    • 트리의 가장 왼쪽부터 방문하는 방법 이진탐색트리라면 자연스럽게 크기순으로 방문하게 됨
  • 후위순회
    • 왼쪽 서브트리를 후위 순회한다.
    • 오른쪽 서브트리를 후위 순회한다.
    • 현재 정점을 방문한다.

서로 다른 트리라고 하더라도 순회결과가 일치할 수 있다.

연습문제

boj-11725

• DFS

import sys
input = sys.stdin.readline
sys.setrecursionlimit(120000)
N = int(input())

parent = [0] * (N+1)
graph = [[ ] for _ in range(N+1)]

for _ in range(N-1):
    
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

def dfs(cur_node:int) -> None:
    for next_node in graph[cur_node]:
        if parent[cur_node] == next_node: continue
        parent[next_node] = cur_node
        dfs(next_node)
        
dfs(1)
for idx in range(2, N+1):
    print(parent[idx])

• BFS

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())

parent = [0] * (N+1)
graph = [[ ] for _ in range(N+1)]

for _ in range(N-1):
    
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

def bfs(root:int) -> None:
    queue = deque()
    queue.append(root)
    while queue:
        cur_node = queue.popleft()
        for next_node in graph[cur_node]:
            if parent[cur_node] == next_node: continue
            queue.append(next_node)
            parent[next_node] = cur_node

bfs(1)
for idx in range(2, N+1):
    print(parent[idx])

boj-1991

import sys
input = sys.stdin.readline

N = int(input().rstrip())
left = [0] * (N+1)
right = [0]* (N+1)

for _ in range(N):
    parent, left_child, right_child = input().rstrip().split()
    
    parent = ord(parent) - ord("A") +1
    if left_child != ".": left_child = ord(left_child) - ord("A") +1
    if right_child != ".": right_child = ord(right_child) - ord("A") +1
    
    left[parent] = left_child
    right[parent] = right_child
    
    
def pre_order(cur_node):
    cur_node_to_char = chr(cur_node + ord("A") -1)
    print(cur_node_to_char, end="")
    if left[cur_node] != ".": pre_order(left[cur_node])
    if right[cur_node] != ".": pre_order(right[cur_node])
        
def in_order(cur_node):
    cur_node_to_char = chr(cur_node + ord("A") -1)
    if left[cur_node] != ".": in_order(left[cur_node])
    print(cur_node_to_char, end="")
    if right[cur_node] != ".": in_order(right[cur_node])
        
def post_order(cur_node):
    cur_node_to_char = chr(cur_node + ord("A") -1)
    if left[cur_node] != ".": post_order(left[cur_node])
    if right[cur_node] != ".": post_order(right[cur_node])
    print(cur_node_to_char, end="")
pre_order(1)
print()
in_order(1)
print()
post_order(1)