모든 트리에서 사용 가능
BFS vs DFS
- 시간 복잡도는 같은 ( 모든 노드들을 한번 씩 방문하기에)
DFS의 공간 복잡도 ↑ 노드가 깊고 길때(일자로 쭉 이어진 트리)
BFS의 공간 복잡도 ↑ 노드가 엄청나게 많을 때 (데이터의 양이 방대할 때)
너비 우선 탐색[Breadth-first Search] →
자식 요소를 보기전에 먼저 형제 노드를 다 보는 것 ( 같은 층에 있는 노드들을 먼저 확인함 ) [수평]
Queue (FIFO)를 사용해서 노드들을 확인하고 dequeue하면서 탐색을 하고 확인된 노드들은 따로 저장해둔다
2~4번의 과정을 보게되면 6,15가 추가되고 6이 선입선출이라서 먼저 빠지게 된 후 15가 빠지기전에 6에 자식노드가 추가 된 것을 확인할 수 있다 (작업을 진행할 큐를 예약걸어두고 수평노드가 끝나면 다음 작업으로 넘어감)
10
6 15
3 8 20
1. queue:[10]
->
searched:[10]
2. queue:[6,15]
->
searched:[10,6]
3.queue:[15,3,8]
->
searched:[10,6]
4. queue:[3,8,20]
->
searched:[10,6,15]BFS(){
var
data=[],
queue=[],
node=this.root
queue.push(node)
while(queue.length){
node = queue.shift()
data.push(node)
if(node.left) queue.push(node.left)
if(node.right) queue.push(node.right)
}
return data
}
깊이 우선 탐색[Depth-first Search] ↓
InOrder (중위)
*리스트를 받아서 데이터베이스에 넣어야 한다던가 순서대로 작업을 해야할 때
left-root-right
[3,6,8,10,15,20]
DFSin(){
var data=[]
var current=this.root
function helper(node){
//node.left && helper(node.left) 이런방식도 가능(True or False)
if(node.left) helper(node.left)
data.push(node.value)
if(node.right) helper(node.right)
}
helper(current)
return data
}
PreOrder (전위)
*데이터베이스나 파일에 담아두었다가 나중에 연쇄 구조로 다시 만들어 날 때 도움이 된다
root-left-right
[10,6,3,8,15,20]
- 방문한 노드들의 값을 담을 변수를 생성후 저장
- current라는 변수에 root를 저장해라
- helper 함수 생성 ( 값들을 담아둘 변수에 node의 값을 push해라)
만약 노드가 왼쪽 프로퍼티를 가지고 있다면 helper 함수를 왼쪽에다 호출, 오른쪽에 경우에도 마찬가지
- current 변수에 helper 함수를 호출하라
- return
DFSpre(){
var data=[]
var current=this.root
function helper(node){
data.push(node.value)
if(node.left) helper(node.left)
if(node.right) helper(node.right)
}
helper(current)
return data
}PostOrder (후위)
*
left-right-root
[3,8,6,20,15,10]
DFSpost(){
var data=[]
var current=this.root
function helper(node){
if(node.left) helper(node.left)
if(node.right) helper(node.right)
data.push(node.value)
}
helper(current)
return data
}