[Data Structures] 트리선회 (DFS & BFS)
자료구조 중, 트리의 각 노드를 한 번 씩 방문하는 것을 트리 순회(Tree traversal)라고 한다. 아래와 같은 트리 구조에서 방문했던 노드를 재방문 하지 않고 효율적으로 전체 순회를 하기 위해서는 체계적인 알고리즘이 필요하다.
가장 대표적인 것이 깊이우선탐색(DFS, Depth-first search)과 너비우선탐색(BFS, Breadth-first search)이다.
깊이우선탐색(DFS, Depth-first search)
명칭에서 알 수 있듯이, sibling 노드로 넘어가기 전에 본인 노드의 모든 가능성(depth)을 탐색하는 것이다.
이 방법이라면, 위의 순회는 F → B → A → D → C → E → G → I → H 순으로 진행된다. 즉, 트리노드를 방문해서 값을 확인하고, children이 있는지 확인 후, 있으면 child node 들도 똑같이 값을 확인하고, children 확인하고, 하는 식으로 계속 반복되는 리커젼이 된다.
각 노드를 순회하면서 filter함수 결과값을 리턴하는 DFS 함수를 생성한다고 하면, 아래와같이 구현할 수 있다.
반면, 너비우선 탐색은 다음 depth 순으로 순회하는 것이다. depth 1에 있는 모든 노드를 확인하고 depth 2로 넘어가는.
즉, 위의 순회는 F → B → G→ A →D → I → C→ E→ H 순으로 진행된다. 이번에는 각 노드에서 children 노드로 바로 넘어가는 것이 아니라, children node를 배열에 넣어 depth별 노드들의 값을 한번에 확인해야한다.
각 노드를 순회하면서 filter함수 결과값을 리턴하는 DFS 함수를 생성한다고 하면, 아래와같이 구현할 수 있다.
