DataStructure
BFS and DFS

Createhb21·2022년 02월 13일 01:02
어떤 트리에서든지 사용할 수 있는 트리 순회에 대해서 알아보겠습니다. 
즉, 어떻게 트리의 모든 노드를 한 번씩 돌 수 있을지에 대해서 알아봅니다.

기본적으로 순회하는 방법은 아주 많습니다만 가장 널리 사용되는 두 가지 전략을 알아봅니다.
하나는 BFS, 너비 우선 탐색이고 다른 하나는 DFS, 깊이 우선 탐색입니다.
아래로 내려가기 전에 같은 레벨에 있는 모든 노드들을 거쳐가는 것을 우선순위로 할 것인가 아니면 더 수직적인 방법으로 깊이 우선 방식을 택할 것인가의 차이입니다.

BFS
   BFS(너비 우선 탐색)을 먼저 알아보겠습니다.
기본적으로 트리를 가로질러서 작업을 합니다.

이를 어떻게 구현할 수 있을까요? 이를 코딩하려면 선입선출 구조인 큐(queue)를 사용해야 합니다.

BFS() { 	
    let node = this.root, 			
        data = [], 			
        queue = [];  	
        
    queue.push(node); 	
    while(queue.length) { 		
        node = queue.shift(); 		
        data.push(node.value); 		
        if(node.left) queue.push(node.left); 		
        if(node.right) queue.push(node.right); 	
    } 	
    return data; 
}



DFS
   이번에는 깊이 우선 탐색을 보겠습니다. 
DFS는 모든 노드를 방문하거나 순회할 때 형제 노드로 넘어가기 전에 수직으로 트리의 끝까지 내려갑니다.
깊이 우선 탐색에는 세 가지 종류가 있는데, 
pre-order, post-order, In-order 입니다.

DFSPreOrder() { 	
    let data = []; 	
    // let current = this.root; 	
    funciton traverse(node) { 		
        data.push(node.value); 		
        if(node.left) traverse(node.left); 			
        if(node.right) traverse(node.right); 	
    }  	
    traverse(this.root); 	
    return data; 
}


DFSPostOrder() { 	
    let data = []; 	
    funciton traverse(node) { 		
        if(node.left) traverse(node.left); 		
        if(node.right) traverse(node.right); 		
        data.push(node.value); 	
    }  	
    traverse(this.root); 	
    return data; 
}


DFSInOrder() { 	
    let data = []; 	
    funciton traverse(node) { 		
        node.left && traverse(node.left); 		
        data.push(node.value); 		
        node.right && traverse(node.right); 	
    }  	
    traverse(this.root); 	
    return data; 
}



BFS, DFS 사용하는 경우
   트리를 순회하는 방법들을 배우고 코딩도 해봤습니다.
둘 중에 어떤 것이 더 나은지, 어느 상황에 어떤 것을 사용해야 하는지를 알아보겠습니다.

너비 우선 탐색을 사용한다면, 일단 모든 노드를 저장하기 위해 큐를 사용한다는 걸 기억해야 합니다.
자식을 먼저 방문하는 것이 아닙니다.

깊이보다 너비가 넓은 트리의 경우에는 깊이 우선 탐색이 더 적은 공간을 점유합니다. 즉 지금 다루고 있는 얘기는 공간 복잡도에 대한 얘기입니다, 시간 복잡도는 둘이 동일하니 상관 없습니다.

트리 순회는 모든 노드를 한 번씩 방문하는 같은 양의 작업을 합니다.
단지 그 작업을 함에 있어서 얼마나 많은 공간을 사용하는지가 문제일 뿐입니다..!

만약에 트리가 아주 넓다면 너비 우선은 큐를 저장하는데 더 많은 공간을 사용하게 됩니다.
그렇지만 아주 깊고 긴 트리라면 깊이 우선이 더 많은 공간을 사용하게 됩니다.
# BFS# DFS# tree