TIL Day 22.

트리 Tree

이진 트리: 자식 노드를 최대 2개 가질 수 있는 트리

순회 방법에는 전위 순회 중위 순회 후위 순회 가 있음

힙은 완전 이진 트리!

키 값이 가장 큰 노드나 가장 작은 노드를 찾기 위해서.

예제 문제

SWEA 5174. subtree

# 트리의 일부를 서브 트리라고 한다. 주어진 이진 트리에서 노드 N를 루트로 하는 서브 트리에 속한 노드의 개수를 알아내는 프로그램을 만드시오.

스쿼드 공부방

트리 순회 문제 (백준 1991번)

# 튜터님 풀이 

N = int(input()) # 노드의 개수

graph = {} #딕셔너리로 풀어준다

for i in range(N):
	a, b, c = map(str, input().split())
    graph[a] = [b, c] #a를 key로 두고 b와 c를 value 로 넣어줌

def preorder(cur): #cur를 현재 보고 있는 노드
	# 왼쪽 자식 노드 graph[cur][0], 오른쪽 자식 노드 graph[cur][1]
    # 루트
    print(cur, end='')
    #왼쪽 자식
    if graph[cur][0] != '.':
    	preorder(graph[cur][0]) # 재귀를 타준다
    #오른쪽 자식
    if graph[cur][1] != '.':
    	preorder(graph[cur][1]) # 재귀
        
def inorder(cur): #cur를 현재 보고 있는 노드
    #왼쪽 자식
    if graph[cur][0] != '.':
    	inorder(graph[cur][0]) # 재귀를 타준다
    # 루트
    print(cur, end='')
    #오른쪽 자식
    if graph[cur][1] != '.':
    	inorder(graph[cur][1]) # 재귀
        
def postorder(cur): #cur를 현재 보고 있는 노드
	
    #왼쪽 자식
    if graph[cur][0] != '.':
    	postorder(graph[cur][0]) # 재귀를 타준다
    #오른쪽 자식
    if graph[cur][1] != '.':
    	postorder(graph[cur][1]) # 재귀
    # 루트
    print(cur, end='')
    
# A가 루트 노드. 출력
preorder('A')
print() #개행
inorder('A')
print() #개행
postorder('A')

트리의 부모 찾기 (백준 11725번)

# 튜터님 풀이
N = int(input())
graph = [ [] for i in range(N+1)] #인접 리스트
parent = [0 for i in range(N+1)] #각 노드의 부모 노드를 저장

for i in range(N-1):
	a, b = map(str, input().split())
    graph[a].append(b
    graph[b].append(a) #양방향 연결을 위해 각 노드를 인덱스로 두고 연결점을 붙여줌
    
def dfs(cur):

	for nxt in graph[cur]:
    	if parent[nxt] == 0: #방문하지 않은 노드만 재귀
    		parent[nxt] = cur # nxt 의 부모는 cur
        	dfs(nxt) # 재귀를 타서 탐색
            

dfs(1)
for i in range(2, len(parent)):
	print(parent[i])

Today I Thought

튜터님의 설명을 들으면 어떻게 된 건지는 알겠는데 내가 구현하는 게 너무 어렵다.. 설명만 듣고 다시 풀어보려고 하니까 아예 시작을 못해서 이제는 튜터님 풀이를 한 번 적어보고 잊어버릴 때까지(..ㅋㅋㅋㅋ) 시간을 좀 둔 후에 다시 풀어보는 걸로. 그러면 적어도 알고리즘적으로 어떤 단계를 거쳐야 하는 지는 알게 되니까 조금 더 수월하게 풀 수 있을 것 같다.
재귀 함수를 다시 한 번 보아야겠다.