트리 순회

1. 트리구조의 노드 탐색 기법, 트리 순회의 개념

- Node와 Edge로 구성된 트리 형태의 자료구조에서 모든 노드를 빠짐없이 한 번씩 방문하여 node를 탐색하는 방법

특징) 검색 성능 예측 가능, 깊이 우선 순회, 너비 우선 순회

 

2. 트리 순회의 유형 및 탐색 매커니즘

가. 트리 순회의 유형

구분	유형	탐색 순서
깊이 우선 순회(DFS)	pre-order	루트 -> 왼쪽 자식 -> 오른쪽 자식
	in-order	왼쪽 자식 -> 루트 -> 오른쪽 자식
	post-order	왼쪽 자식 -> 오른쪽 자식 -> 루트
너비 우선 순회(BFS)	level-order	루트부터 레벨별 왼쪽 -> 오른

 

나. 트리 순회 매커니즘

3. 코드 예제

preorder	inorder	postorder
def preorder(node):     if node:         print(node.value)         preorder(node.left)         preorder(node.right)	def inorder(node):     if node:         inorder(node.left)         print(node.value)         inorder(node.right)	def postorder(node):     if node:         postorder(node.left)         postorder(node.right)         print(node.value)