본문 바로가기
자료구조

[JS] 트리 순회

by 아촌 2022. 12. 18.

 

1.너비우선탐색 BFS

BFS() {
    let node = this.root;
    let data = [];
    let queue = [];

    queue.push(node);
    //queue에 노드가 있는 동안 루프를 돈다.
    while (queue.length) {
      node = queue.shift();
      //dequeue된 노드 값을 data에 추가
      data.push(node.val);
      //왼쪽있으면 왼쪽도 넣고 오른쪽있으면 오른쪽도 넣고
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return data;
  }

 

2. 깊이우선탐색 DFS

왼쪽으로 트리 수직방향으로 쭉 내려가서 탐색하는 방법

 

깊이우선탐색에는 세 가지 방법이 있다. 모두 재귀를 사용하며, 이 세 가지 방법의 각각의 코드들은 재귀의 헬퍼함수 내에서 data.push(node.value); 한 줄의 위치만 다르고 나머지는 동일한다.

 

 

PreOrder(전위순회)

 

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

 

InOrder(중위순회)

 

DFSInOrder() {
    let data = [];
    function traverse(node) {
      if (node.left) traverse(node.left);
      data.push(node.val);
      if (node.right) traverse(node.right);
    }
    traverse(this.root);
    return data;
  }

PostOrder(후위순회)

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

 

 

DFS와 BFS 시간복잡도는 같다. 하지만 공간복잡도 때문에 골라야한다.

가로로 넓은 트리일 경우 DFS

세로로 아주 깊은 트리일 경우 BFS

'자료구조' 카테고리의 다른 글

[JS] 해시테이블  (1) 2022.12.22
[JS] 이진 힙  (0) 2022.12.21
[JS] 트리와 이진 탐색 트리  (0) 2022.12.17
[JS] 스택(stack)과 큐(Queue)  (0) 2022.12.17
[JS]이중연결리스트 Doubly Linked Lists  (0) 2022.12.16