트리 순회

트리 순회

트리 순회 : 트리의 모든 노드를 방문하는 순서 (트리 구조에 들어 있는 자료에 접근을 위함)

선형 구조는 각 자료가 순서를 가지지만 비선형 구조는 정해진 순서가 없음

트리 순회에는 DFS(깊이 우선 탐색) 과 BFS(너비 우선 탐색) 2가지 종류가 있음

DFS(깊이 우선 탐색)의 종류

전위 순회 : 루트 방문 > 왼쪽 서브 트리 순회 > 오른쪽 서브 트리 순회 중위 순회 : 왼쪽 서브 트리 순회 > 루트 방문 > 오르쪽 서브 트리 순회 후위 순회 : 왼쪽 서브 트리 순회 > 오르쪽 서브 트리 순회 > 루트 방문

루트 방문 순서에 따라서 순회 방법이 나누어 지는 것을 볼 수 있다.

# 전위 순회 def preorder(tree) : result = [] result.append(tree.index) #루트노드 if tree.left != None : result = result + preorder(tree.left) if tree.right != None : result = result + preorder(tree.right) return result # 중위 순회 def inorder(tree) : result = [] if tree.left != None : result = result + inorder(tree.left) result.append(tree.index) #루트노드 if tree.right != None : result = result + inorder(tree.right) return result #후위 순회 def postorder(tree): if tree.left != None : result = result + postorder(tree.left) if tree.right != None : result = result + postorder(tree.right) result.append(tree.index) #루트노드 return result

DFS 는 재귀적으로 동작하며 루트노드 방문 순서만 차이가 있음

BFS(너비 우선 탐색)

현재 정점과 이웃한 정점일수록 먼저 방문해야 함

from queue import Queue def BFS(tree): result = [] q = Queue() q.put(tree) while not q.empty(): cur = q.get() if cur == None : continue result.append(cur.index) q.put(cur.left) q.put(cur.right) return result

자료를 먼저 넣어준 순서대로 결과 값에 넣어주어야 하기 때문에 queue 구조를 사용한다.

큐 자료의 트리의 리프노드까지 반복한다 현재 노드를 뽑아와 결과값에 넣어주고 다시 큐에는 자신의 왼쪽 자식 노드, 오른쪽 자식 노드를 순서대로 넣어주어서 너비 우선적으로 값들을 뽑아 올 수 있게 된다.

코딩테스트의 단골 문제라는데 이해는 되지만 아직 응용을 어떻게 해야할 지 감이 안잡힌다..

from http://comgiri.tistory.com/24 by ccl(A) rewrite - 2021-09-25 17:26:25