DFS(깊이 우선 탐색)

oh_bom·2022년 12월 4일
0

알고리즘

목록 보기
1/4

DFS(Depth First Search): 깊이 우선 탐색

: 이름에서 살짝 알 수 있듯이 트리에서 루트를 최대한 깊숙이 들어가서 확인 한 후 다시 돌아가는 탐색 방법

알랑말랑 한다면 예시코드로 바로 가보자~


전위, 중위 ,후위 구현 코드!를 보기전에

전위, 중위 ,후위가 뭔지 먼저 알아보자!

전위: 부모 노드가 자식 노드들보다 먼저 맨 앞에
중위: 부모 노드가 좌우 자식 노드의 중간
후위: 부모 노드가 자식 노드들보다 더 늦게 마지막

기준이 부모 노드임을 기억하면 덜 헷갈린다.


Node 생성

tree 생성

전위 코드

: 부모 노드 출력 후 자식 노드 호출

중위 코드

왼쪽 자식 노드 출력 후 부모 노드 출력

후위 코드

왼쪽 오른쪽 자식 노드 모두 출력 후 마지막에 부모노드 출력

부분 집합을 출력하는 코드 예시

사실,,이해가 잘안되서 그림을 열심히 그리면서 했는데 한번 같이 올려볼게요,,

profile
목표는 감자탈출

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN