Chapter [ Graph / Tree / BST ]

[ Graph ]

3. class 키워드로 Graph 구현

// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)
class GraphWithAdjacencyMatrix {
  //graph의 constructor를 구현합니다.
  constructor() {
    this.matrix = [];
  }
  //vertex를 추가합니다.
  addVertex() {
    const currentLength = this.matrix.length;
    for (let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0);
    }
    this.matrix.push(new Array(currentLength + 1).fill(0));
  }
  //vertex를 탐색합니다.
  //this.matrix에 vertex가 존재한다면 true를 리턴하고, 반대의 경우라면 false를 리턴합니다.
  contains(vertex) {
    if(vertex < this.matrix.length){
      return true
    }
     return false
  }
  //vertex와 vertex를 이어주는 edge를 추가합니다.
  addEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 1로 바꿔줘서 edge로 연결이 되어 있음을 표시합니다.
    this.matrix[from][to] = 1;
  }
  // from vertex와 to vertex 사이에 edge를 가지고 있는지 여부를 판단합니다.
  hasEdge(from, to) {
    //TODO: 두 버텍스 사이에 간선이 있는지 확인합니다.
    if(this.matrix[from][to] === 1){
      return true
    }
    return false	
	}
  // from vertex와 to vertex 사이에 관련이 없다면, edge를 제거 합니다.
  removeEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 0으로 바꿔줘서 관련이 없음을 표시합니다.
    this.matrix[from][to] = 0;
  }
}

[ Tree ]

3. class 키워드로 Tree 구현

class Tree {
  //tree의 constructor를 구현합니다.
  //tree의 자식 노드들을 children으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정합니다.
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  //tree의 자식 노드를 생성 한 후에, 노드의 children에 push해 줍니다.
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
  // tree에서 value값을 탐색합니다.
  // 현재 노드의 value 값이 찾는 값과 일치한다면 return합니다.
  contains(value) {
    if (this.value === value) {
      return true;
    }
    // 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색합니다.
    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
    return false;
  }
}

[ BST ]

3. class 키워드로 BST 구현

class BinarySearchTree {
  //BST의 constructor를 구현합니다.
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  // tree에 value를 추가합니다.
  insert(value) {
    // 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행합니다.
    if (value < this.value) {
      // this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
      if (this.left === null) {
        this.left = new BinarySearchTree(value);
      }
      // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
      else {
        this.left.insert(value);
      }
    }
    // 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행합니다.
    else if (value > this.value) {
      // this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
      if (this.right === null) {
        this.right = new BinarySearchTree(value);
      }
      // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
      else {
        this.right.insert(value);
      }
    } else {
      // 이미 value값을 포함하고 있습니다.
    }
  }
  // tree의 value값을 탐색합니다.
  contains(value) {
    // 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
    if (value === this.value) {
      return true;
    }
    // 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행합니다.
    if (value < this.value) {
      return !!(this.left && this.left.contains(value));
    }
    // 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행합니다.
    if (value > this.value) {
      return !!(this.right && this.right.contains(value));
    }
  }
  //tree를 전위 순회 합니다.
  preorder(callback) {
    callback(this.value);
    if (this.left) {
      this.left.preorder(callback);
    }
    if (this.right) {
      this.right.preorder(callback);
    }
  }
  // tree를 중위 순회 합니다
  inorder(callback) {
    if (this.left) {
      this.left.inorder(callback);
    }
    callback(this.value);
    if (this.right) {
      this.right.inorder(callback);
    }
  }
  //tree를 후위 순회 합니다
  postorder(callback) {
    if (this.left) {
      this.left.postorder(callback);
    }
    if (this.right) {
      this.right.postorder(callback);
    }
    callback(this.value);
  }
}