Tree traversal(1) with JS

• 단일 연결 리스트
• 이중 연결 리스트
• 스택 & 큐 (배열로 하는 방법은 숙지했음! linked list로 구현해 보기)
• 이진 검색 트리
• 트리 순회 (bfs,dfs)
• 이진 힙
• 해시 테이블 (사용해 봤지만 복습)
• 그래프, 그래프 순회
• 다익스트라 알고리즘
• 동적 프로그래밍

---

트리 순회 소개

트리를 순회하는데는 두 가지 방식이 있다.

 

• 너비 우선 (BFS)

• 깊이 우선 (DFS)
  • preorder, inorder, postorder

preorder

postorder

inorder

BFS 너비우선탐색

- use Queue(Array & list) : FIFO(first in first out)

• 아래코드를 보면 1~7번까지 순서로 이동한다.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BFS {
  constructor() {
    this.root = null;
  }
  insert(value) {
    var newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let traverse = this.root;
      while (true) {
        if (traverse.value === value) return undefined;
        if (traverse.value > value) {
          if (traverse.left === null) {
            traverse.left = newNode;
            return this;
          }
          traverse = traverse.left;
        } else {
          if (traverse.right === null) {
            traverse.right = newNode;
            return this;
          }
          traverse = traverse.right;
        }
      }
    }
  }
  BFS() {
    var data = [];
    var queue = [];
    var node = this.root;
    queue.push(node);

    while (queue.length) {
      node = queue.shift();
      data.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return data;
  }
}

let bfs = new BFS();
bfs.insert(10);
bfs.insert(6);
bfs.insert(3);
bfs.insert(8);
bfs.insert(15);
bfs.insert(20);
let data = bfs.BFS();
console.log(data);