<Udemy 트리 순회> TIL-65

  오늘은 트리를 순회하는 방법에 대해서 공부했다. 앞서 이진 검색 트리에 대해서 공부했었는데 이진 검색 트리만을 위한 검색 방법이 아닌 트리형태의 자료 구조들을 전부 순회할 수 있는 대표적인 방법들에 대해서 공부했다. 오늘 공부하는 것은 개념적으로는 크게 어렵지 않았으나, 코드를 이해하는데 시간이 꽤 걸렸다. bfs방식은 루트 노드부터 시작해서 같은 레벨에 존재하는 모든 노드들을 먼저 순회한 후 또 다시 그 아래에 위치하는 노드들을 검색하는 방식이고 dfs방식은 루트 노드부터 시작해서 자식 노드로 또 그 노드의 자식 노드로 순회를 이어가면서 탐색하는 방법이다. dfs방식에는 다시 전위, 후위, 중위 방식으로 나뉠 수 있는데 순회한 노드를 마지막에 반환 할 배열에 언제 저장하느냐에 따라 달라지게 된다. 사실 아직 전위, 후위, 중위방식의 차이점에 대해서는 크게 모르겠다. 하지만 bfs와 dfs에 대한 차이점은 명확하게 알 수 있었다. 트리로 데이터를 저장하더라도 깊이가 깊게 트리가 만들어 진다면 재귀 방식을 활용하는 dfs보다 큐를 활용하는 bfs를 통해서 검색하는 것이 좋고 반대로 데이터가 넓게 퍼져서 트리가 형성되었다면 bfs보다는 dfs를 활용해서 데이터를 검색하는 것이 효율적일 것이라는 생각이 들었다.

 

2022.08.16 - [언어 공부 및 정리/자바스크립트 알고리즘 & 자료구조[Udemy강의]] - 17 트리 순회

17 트리 순회