트리 순회

모든 트리에서 사용 가능

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  
}