[자료구조] 이진트리순회 / BFS , DFS

Breadth-first Search( 너비우선 탐색 )

• 같은 레벨에 있는 노드들을 먼저 거쳐가야 한다.
• 자식노드를 보기전에 형제노드를 먼저 체크한다. (수평레벨 체크)

배열이나 리스트로 queue를 만들고 Push 생성 unshift 제거
큐를 만들어서 요소를 추적하고,
그 방문한 데이터의 리스트를 만들어 마지막에 출력

BFS 의사코드

1. 큐에 루트노드를 위치시킨다.
2. 큐에 무언가가 있으면 루프를 계속 돌린다.
   • 큐에서 dequeue( 배열 shift ) , 데이터의 리스트에 큐에서 꺼내온 값을 넣어줌.
   • 노드 왼쪽에 값이 있다면 큐에 넣어주기
   • 노드 오른쪽 값이 있다면 큐에 넣어준다.
3. 큐에 아무것도 없어 종료가 되면 방문한 데이터 리스트를 출력한다.

BFS 소스코드 (이진트리)

function bfs(bst){
    let queue=[bst.root]
    let visited=[]
    //자바스크립트는 빈배열 값을 true로 판단
    while(queue.length!==0){
        const node = queue.shift();
        visited.push(node.value);

        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
    }
    return visited;
}

위의 코드는 자식의 왼쪽 오른쪽 최대 2개의 노드를 가지는 이진트리일 때 이다.
만약 자식이 2개 이상일 경우 해당 부분은 변경해야한다.

---

Depth-first Search ( 깊이우선 탐색 ) / 전위 중위 후위

DFS 소스코드

  class BinarySearchTree{
      constructor(){
          this.root = null;
      }
      insert(value){
          let newNode = new Node(value);
  
          if(!this.root){ 
              this.root = newNode;
              return this 
          }
          
          let curNode = this.root;
          let count=0;
          while(curNode){
              if(value === curNode.value) return undefiend;
              if(value < curNode.value) {
                  if(curNode.left === null) {
                      curNode.left = newNode;
                      return this;
                  }
                  curNode = curNode.left
              }
              else {
                  if(curNode.right === null) {
                      curNode.right = newNode;
                      return this;
                  }
                  curNode = curNode.right
              }
          }
          return this;
      }
  
      find(value){
          if(!this.root) return false;
  
          let curNode = this.root;
          while(curNode){
  
              if(curNode.value===value) return true;
  
              if(value<curNode.value) curNode= curNode.left;
              else curNode = curNode.right;
              
          }
          return false   
      }
  
      dfs_pre(){
          let visited= [];
          let current = this.root;
  
          function traverse(node){
              visited.push(node.value);
              if(node.left) traverse(node.left);
              if(node.right) traverse(node.right);
          }
          traverse(current);
          return visited;
      }
      dfs_post(){
          let visited=[];
          let current = this.root;
  
          function traverse(node){
              
              if(node.left) traverse(node.left);
              if(node.right) traverse(node.right);
              visited.push(node.value);
          }
          traverse(current);
          return visited;
          
      }
  }
  
  class Node{
      constructor(value){
          this.value = value;
          this.left = null;
          this.right= null;
      }
      
  }
  

traverse 헬퍼함수에서 위치만 바꿔주면 전위, 중위, 후위가 된다.

• 전위순위 부모노드-왼쪽자식-오른쪽자식

  1. visited [] 나중에 출력시킬 데이터

     최상위 노드를 current 변수에 저장

  2. 헬퍼함수를 만든다.

     • 현재 노드에 저장된 값을 visited 배열에 push
     • 왼쪽 자식이있다면 왼쪽 자식을 넘겨 헬퍼 함수를 또 부른다.
     • 오른쪽 자식이 있다면 오른쪽 자식을 넘겨 헬퍼 함수를 부른다.

     function traverse(node){
         visited.push(node.value);
     		if(node.left) traverse(node.left);
         if(node.right) traverse(node.right);
     }

• 후위 왼쪽자식- 오른쪽자식-부모노드 전위와 동일하지만 할퍼함수에서 순서가 바뀐다. 왼쪽 헬퍼함수 , 오른쪽 헬퍼함수 현재노드 값 visited 배열에 저장

  function traverse(node){
      if(node.left) traverse(node.left);
      if(node.right) traverse(node.right);
      visited.push(node.value);
  }

• 중위 왼쪽 - 부모- 오른쪽

BFS, DFS 어느것을 선택?

• BFS는 큐가 나중에 비어지게 되긴 하지만 데이터를 저장함으로 공간복잡도가 DFS에 비해서 크다.
• 시간복잡도에서는 차이가없다. 왜냐면 100개 노드가 있다면 모드 방문해야하는 것은 동일하기 때문이다.
• 깊이보다 너비가 넓은 트리의 경우 DFS가 BFS보다 더 적은 공간을 점유한다.
  • 트리가 넓다면 너비우선은 큐를 저장하는데에 더 많은 공간을 사용한다.
• 깊이가 아주 긴 트리라면 DFS가 더 많은 공간을 차지하게 된다.