프로그래머스 인공지능 데브코스 3기 1주차 Day3(1)

이진 트리의 한 종류로 이진 탐색 트리(Binary Search Tree)의 insert() 메서드를 구현한 시점에서 순회(Traversal)중 깊이 우선 순회(depth first traversal)을 확인해보겠다.

 

이진 트리의 깊이 우선 순회(depth first traversal)에는 세 종류가 있다.

 

1. 전위 순회(pre-order traversal)

2. 중위 순회(in-order traversal)

3. 후위 순회(post-order traversal)

 

루트 노드를 방문하는 순서에 따라서 나눠진다.

 

강의에서 다룬 형태와는 다른 이진 트리를 만들어 보았다.

그림에서 보이는 숫자는 해당 노드의 data를 의미하고 알파벳은 key를 의미한다. 

insert를 하는 과정에서 노드의 data를 기준으로 이진 탐색 트리 형태로 만들게 된다. 

 

각 순회에 방문 순서를 손으로 적어보았다. 

 

구현된 코드로 확인해보자. 두근 두근🧐

 

우선 첫 번째 그림에서와 같이 key를 6으로 하는 노드를 루트 노드로 하면서 각 노드들을 삽입한다.

 

트리의 순회 결과를 살펴보면 내가 손으로 예산했던 결과와 100% 일치한다.

오예!!!💪🏻💪🏻💪🏻