Binary Tree Traversal, DFS, BFS

[ Binary Tree Traversal ]

트리를 순회하는 방법을 "Binary Tree Traversal"이라고 한다. 어떻게 하면 트리의 맨 아래에 있는 가지를 전부 둘러보면서 조회를 할 수 있을까를 방법론으로 만든 것이다. 방법은 3가지가 있다. InOrder, PreOrder 그리고 PostOrder이다.

 

InOrder는 (LVR : Left, Root, Right)라고 하며 왼쪽, 가운데 그리고 오른쪽을 차례대로 순회한다.  PreOrder는 (VLR : Root, Left, Right)라고 하며 가운데, 왼쪽 그리고 오른쪽을 차례대로 순회한다. 마지막으로 PostOrder는 (LRV : Left, Right, Root)라고 하며 왼쪽, 오른쪽 그리고 가운데를 차례대로 순회한다.

 

(1) InOrder는 Left, Root, Right이고 순서는 4 > 2 > 5 > 1 > 3 이다. 즉 맨 왼쪽의 끝 가지부터 진행하고 가운데 그리고 오른쪽을 조회한다.

(2) PreOrder는 Root, Left, Right이고 순서는 1 > 2 > 4 > 5 > 3이다. 즉 자기 사진부터 시작하고 왼쪽으로 뻗는다. 가지가 있는 면 자기 자신을 먼저 조회하고 왼쪽으로 내려간다. 다시 자기 자신을 조회하고  더 왼쪽에 가지가 없으면 가운데로 올라와 오른쪽을 순회한다.

(3) PostOrder는 Left, Right, Root이고 순서는 4 > 5 > 2 > 3 > 1 이다. 즉 맨 왼쪽의 끝 가지를 진행하고 중간을 지나 오른쪽을 조회 후 가운데를 조회한다.

 

 

 

[ DFS와 BFS의 차이 ]

DFS는 Depth-First Search 라고 하며 깊이를 우선하는 탐색 방법이다. Binary Tree Traversal에서 사용한 InOrder, PreOrder, PostOrder가 DFS의 근간으로 보면 된다. 하지만 DFS가 기본으로 사용하는 로직은  Binary Tree Traversal과 다른 모습이다. 

 

BFS는 Breadth-First Search 라고 하면 넓이를 우선하는 탐색 방법이다. BFS의 방식은 먼저 Root 자기 자신을 탐색하고 바로 다음 자식을 순회한다. 그 후 자식의 자식을 방문하는 방식의 Top Down 레벨 하강 형식으로 보면 된다.

 

 

[ DFS ] 

DFS는 기본적으로 스택(Stack)을 사용해서 구현하는데 시작 노드를 넣고 자식 노드를 하나씩 넣는데 한번 넣었던 자식은 다시 넣지 않는다. DFS가 움직이는 것을 예제로 확인해 본다.

Stack은 POP하면서 가장 위에 있는 값을 뺀다. 

(1) 0을 스택에 넣고 POP 하여 뺀다. 이때 자식인 1을 Stack에 넣는다.

(2) 1을 스택에서 POP하고 자식인 2와 3을 넣는다.

(3) 3이 스택의 가장 최신이니 3을 POP 한다. 그리고 자식인 2, 4, 5를 추가하는데 2는 이미 한번 넣었으므로 패스한다.

(4) 5가 스택의 가장 최신이니 5를 POP한다. 그리고 자식인 6, 7을 추가한다.

(6) 7이 스택의 가장 최신이니 7을 POP한다. 그리고 자식이 없으므로 패스한다.

(7) 6이 스택의 가장 최신이니 6을 POP한다. 그리고 자식인 8을 추가한다.

(8) 8이 스택의 가장 최신이니 8을 POP한다.POP 한다. 그리고 스택에 남아있는 4, 2를 순서대로 POP 한다.

 

 

[ BFS ]

BFS는 큐(Queue)를 사용해서 구현한다. 시작 노드를 넣고 자식 노드를 하나씩 넣는데 한번 넣었던 자식은 다시 넣지 않는다. DFS가 움직이는 것을 예제로 확인해 본다.

큐(Queue)는 Out 할 때 가장 밑에 있는 값을 먼저 뺀다.

(0) 0을 Out 하고 자식은 1을 큐에 넣는다.

(1) 1을 Out하고 자식인 자식인 2와 3을 넣는다.

(2) 2를 Out하고 자식인 4를 넣는다.

(3) 4를 Out 하고 자식을 확인하니 이미 다 큐에 넣어진 상태로 패스한다.

(5) 5를 Out하고 자식인 6과 7을 넣는다.

(6) 6을 Out하고 자식인 8을 넣는다.

(7) 7을 Out하고 자식을 확인하니 하위에는 자식이 없어서 패스한다.

(8) 8을 Out하고 자식을 확인하니 하위에는 자식이 없어서 패스한다.