들어가며...

최근하는일!

• 자바스크립트 자료구조/알고리즘 공부 in 데브코스

• 개인프로젝트 진행...

• 스터디 조성 및 진행

• 기업 모의 입사 지원서 작성

  그러므로 오늘은... 짧게 til 적는다!

트리

트리는 그래프의 종류인데, 그래프처럼 정점과 간선으로 이루어져 있고, 부모 노드와 자식노드의 관계가 지어져 있다. 그리고 임의의 두 노드 사이의 경로는 "단 하나"이다. 즉, 경로가 반드시 존재한다.

다음 그림에서 보는 것 처럼, 맨 위에 A부분에 해당하는 노드를 루트라고 하고, 맨 아래에 있는 자식들을 가지지 않은 노드들을 리프노드라고 부른다.

그리고 트리를 그림과 같이 봤을 때, 같은 부모로부터 갈라진 노드들을 형제노드라고 하고, 같은 형제노드들이 있는 층을 레벨이라고 한다.

순회방법

이제 트리구조를 만들었으니 이를 써먹어야 할 차례이다. 트리는 잘만 이용하면 원하는 자료에 쉽게 접근할 수 있는데, 그러기 전에 먼저, 트리에 있는 데이터를 조회하는 순서를 익히면 좋다.

다음과 같은 순서로 데이터를 탐색할 수 있다!

전위순회

루트->왼쪽자식->오른쪽자식 순서
ex) 1->2->4->5->3

중위순회

왼쪽자식->루트->오른쪽자식 순서
ex) 4->2->5->1->3

후위순회

왼쪽자식->오른쪽자식->루트 순서
ex) 4->5->2->3->1

레벨순회

맨위의 레벨부터 왼쪽에서 오른쪽으로 탐색
ex) 1->2->3->4->5

구현

자바스크립트로 구현한 노드는 큐를 이용해서 구현 할 수 있다.

class Queue {
  constructor() {
    this.items = [];
    this.front = 0;
    this.back = 0;
  }
  enqueue(item) {
    this.items[this.back++] = item;
    return this.items[this.back - 1];
  }
  dequeue() {
    const item = this.items[this.front];
    delete this.items[this.front++];
    return item;
  }
  peek() {
    return this.items[this.front];
  }
  isEmpty() {
    return this.front === this.back;
  }
  size() {
    return this.back - this.front;
  }
}

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

class Tree {
  constructor(node) {
    this.root = node;
  }
  levelOrder() {
    const queue = new Queue();
    queue.enqueue(this.root);
    while (queue.size()) {
      const node = queue.dequeue();
      print(node);
      if (node.left) queue.enqueue(node.left);
      if (node.right) queue.enqueue(node.right);
    }
  }
  preOrder(node, callback) {
    if (node === null) {
      return;
    }
    callback(node, callback);
    this.preOrder(node.left, callback);
    this.preOrder(node.right, callback);
  }
  inOrder(node, callback) {
    if (node === null) {
      return;
    }
    this.inOrder(node.left, callback);
    callback(node, callback);
    this.inOrder(node.right, callback);
  }
  postOrder(node, callback) {
    if (node === null) {
      return;
    }
    this.postOrder(node.left, callback);
    this.postOrder(node.right, callback);
    callback(node, callback);
  }
}
function print(node) {
  process.stdout.write(`${node.value} -> `);
}
const tree = new Tree(new Node(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);

tree.preOrder(tree.root, print);
console.log("end");
tree.inOrder(tree.root, print);
console.log("end");
tree.postOrder(tree.root, print);
console.log("end");
tree.levelOrder();
console.log("end");

아쉬운대로 이거라도...

이미지 출처

https://www.geeksforgeeks.org/