[자료구조] 트리 순회 (javascript로 구현하기)

트리순회

• 제너럴 트리의 모든 노드를 순회하는 알고리즘

 

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

• 트리의 너비가 넓을수록 공간복잡도에서 불리

 

깊이우선탐색(Breadth-First Search)

• 트리의 깊이가 깊을수록 공간복잡도에서 불리
• 세종류의 순회방식이있다. 모두다 한쪽 사이드를 전부 순회할 수 나머지 반대방향으로 간다는 것이 공통점

 

• 전위순회(Preorder)
  • 탐색순서대로 데이터를 저장한 경우 그 데이터를 기반으로 트리를 다시 만들기 편리함

전위순회가 유리한 상황 (배열 순서가 순회경로임)

 

• 후위순회(Postorder)
  • 필요한 자료형태에 따라 유리한 상황이 있을것(구체적인 예시는 잘 모르겠다...)

 

• 중위순회(inorder)
  • 탐색순서대로 데이터를 저장한 경우 탐색트리(이진탐색트리 등)의 정렬순서와 동일해 특정작업시 유리

중위순회가 유리한 상황(이진탐색트리) - 오름차순으로 순회함 ((배열 순서가 순회경로임)

 

구현

• 모든 트리는 이전에 구현한 이진탐색트리를 이용한다.
• BFS에서는 이전에 구현한 큐 자료형을 이용한다.
• DFS의 세 종류는 모두 재귀를 이용했으며 코드가 매우 유사하다(value에 접근하는 타이밍만 다름)

 

BFS

queue를 이용한 BFS의 구동방식

const { BST } = require("./tree.js");
const { Queue } = require("./queue.js");

class BSTWithTraversal extends BST {
  traverseBFS() {
    if (!this.root) return false;
    const queue = new Queue();
    const trace = [];

    queue.enqueue(this.root);
    while (queue.length > 0) {
      const { val: currentNode } = queue.dequeue();
      trace.push(currentNode.val);
      if (currentNode?.left) queue.enqueue(currentNode.left);
      if (currentNode?.right) queue.enqueue(currentNode.right);
    }
    console.log(trace);
    return trace;
  }
}

 

DFS - 전위순회

class BSTWithTraversal extends BST {
//... 메소드
  traversePreDFS() {
    const trace = [];
    const pushAndRetraverse = (node) => {
      trace.push(node.val);
      const { left, right } = node;
      if (left) pushAndRetraverse(left);
      if (right) pushAndRetraverse(right);
    };
    pushAndRetraverse(this.root);

    console.log(trace);
    return trace;
  }
//... 메소드
}

  

DFS - 후위순회

class BSTWithTraversal extends BST {
//... 메소드
  traversePostDFS() {
    const trace = [];
    const traverseAndPush = (node) => {
      const { left, right } = node;
      if (left) traverseAndPush(left);
      if (right) traverseAndPush(right);
      trace.push(node.val);
    };
    traverseAndPush(this.root);
    console.log(trace);
    return trace;
  }
//... 메소드
}

  

DFS - 중위순회

class BSTWithTraversal extends BST {
//... 메소드
  traverseInDFS() {
    const trace = [];
    const traverseAndPush = (node) => {
      const { left, right } = node;
      if (left) traverseAndPush(left);
      trace.push(node.val);
      if (right) traverseAndPush(right);
    };
    traverseAndPush(this.root);
    console.log(trace);
    return trace;
  }
//... 메소드
}