🌲graph(그래프)

/*
 *  - Undirected Graph (무방향그래프)
 *  - Adjacency list implementation (인접리스트 이용)
 */
class Graph {
  constructor() {
    /*
     *  ex)
     *    nodes = {
     *      0: [ 1, 2 ],
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }
     */
    this.nodes = {};
  }

  // 그래프에 노드를 추가하는 메소드
  addNode(node) {
    this.nodes[node] = this.nodes[node] || [];
  }

  // 해당노드가 들어있는지 유무 리턴
  contains(node) { 
    return node in this.nodes;
  }
 
  // 그래프에서 노드 삭제하는 메소드
  removeNode(node) {
    // 1. delete 해당 노드
    // 2. 그래프의 노드들을 각각 가져와서
      // 2-1. 각 노드들의 간선에 지운 노드가 있는경우, splice 로 삭제
  }

  // 간선 존재유무 확인하는 메소드
  hasEdge(fromNode, toNode) {
    //1. fromNode 노드와 toNode 노드에 간선이 있는 경우만 확인
      // 1-1. includes 를 이용하여 둘다 서로를 포함하고 있는 경우 true리턴
    
    // 2. 1이 실행되지 않으면
    return false;
  }

  // 간선을 추가하는 메소드
  addEdge(fromNode, toNode) {
    // 1. fromNode에 push 로 간선추가
    // 2. toNode에 push 로 간선추가
  }

  // 간선을 제거하는 메소드
  removeEdge(fromNode, toNode) {
    // 1. splice로 fromNode 노드안에 있는 toNode로 향하는 간선 제거
    // 2. splice로 toNode 노드안에 있는 fromNode로 향하는 간선 제거de), 1)
  }
}

module.exports = Graph;

🌲Tree(트리)

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  
  // 트리노드에 노드를 추가하는 메소드
  insertNode(value) {
    let node = new TreeNode(value);
    // 1. 트리노드의 자식에 새 노드를 추가합니다.
  }

  // 트리에 해당노드가 존재하는지 확인하는 메소드
  contains(value) {
    // 1. if 현재 값이 입력된 값과 같으면 true 리턴 (재귀의 기초)

    // 2. for 문으로 루트노드의 각각의 자식요소 재귀함수 호출
      // 2-1. if 재귀함수리턴값이 true가 되면 true 리턴으로 for문 종료

    // 3. 여기까지 온다면 해당노드가 없음 -> return false;
  }
}

module.exports = TreeNode;

🌲binarySearchTree (이진탐색트리)

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  
  // 이진탐색트리에 노드를 추가하는 메소드
  insert(value) {
    let newNode = new BinarySearchTreeNode(value)
    
    const find = function (node) {
    // 1. if 새로만들려는 노드값 < 루트 노드값 이면, 루트 왼쪽자식을 확인
      // 1-1. 루트 왼쪽자식이 없는 경우, 루트 왼쪽자식자리에 새 노드를 위치시킴
      // 1-2. 루트 왼쪽자식이 있는 경우, 왼쪽자식을 재귀함수에 돌림

    //2. if 새로만들려는 노드값 > 루트 노드값 이면, 루트 오른쪽자식을 확인
      //2-1. 루트 오른쪽자식이 없는 경우, 루트 오른쪽자식자리에 새 노드를 위치시킴
      //2-2. 루트 오른쪽자식이 있는 경우, 오른쪽자식을 재귀함수에 돌림
    }
    
    // 0. 루트를 find 함수에 집어넣음
    find(this)
  }
  
  // 이진탐색트리에 해당노드 존재하는지 확인하는 메소드
  contains(value) {
    
    const check = function (node) {
      // 1. 재귀의 기초 : 루트 노드값이 입력받은 value와 일치하면 true 리턴
      if (node.value === value) {
        return true;
      }
      // 2. 모든 값을 확인하기위해 변수에 false 넣는 방식으로 진행
      // 이 과정을 안하면, 한번 자식으로 빠졌을때 다음 부모를 확인하지 못함
      let result = false;
      
      // 3. if 루트노드값 < 입력받은 value 이면, 오른쪽 자식 확인
        // 3-1. 오른쪽 자식이 있는 경우, 오른쪽 자식을 재귀함수에 돌려서 result 에 할당
        // 3-2. result 값이 false가 아닌 경우, true 로 리턴
      
      // 4. if 루트노드값 > 입력받은 value 이면, 왼쪽 자식 확인
        // 4-1. 오른쪽 자식이 있는 경우, 오른쪽 자식을 재귀함수에 돌려서 result 에 할당
      // 4-2. result 값이 false가 아닌 경우, true 로 리턴
      
      // 5. 다 확인했는데도 result 값이 false 를 유지하고 있으면, 해당노드 없다는 뜻임
      return false;
      }
    
    // 0. 루트를 check 함수에 집어넣고 리턴
    return check(this)
  }

  // 이진탐색트리를 중위순회하는 메소드
  inorder(callback) {
    // callback = 노드값들 받아서 배열에 차곡차곡 push하는 함수
    
    const sort = function (node) {
      // 1. left 자식이 없으면 현재 value callback함수에 넣기
        // 1-2. right 자식이 있으면, right 자식을 재귀함수 호출

      // 2. left 자식이 있으면 left 자식 재귀함수 호출
        // 2-1. 2까지 완료하면, 더이상 쓸 value 없으니 null 로 바꿔서 더이상 조회안하게 삭제
        //2-2. 삭제가 진행되고 남은 부분을 다시 재귀함수에 돌림
    } 
    // 0. 루트를 sort 함수에 집어넣기
    sort(this)
  }
}

module.exports = BinarySearchTreeNode;

• 치명적인 단점 : inorder 메소드에서 삭제하는 부분으로 인해, 루트노드가 변경이 된다.

즉, 한번 inorder 메소드를 사용하면, 거의 절반의 노드가 날아간다.
삭제하지 않고 다음 부모를 확인하는 과정으로 가게 하는 방법을 모르겠다.

이 부분은 추후에 더 공부를 하고, 다시와서 수정해봐야겠다.
스프린트 테스트는 통과했지만, 굉장히 찜찜하다.

+깊은복사로 주소값을 끊어내고 복사하는 것에 성공했다.

const copiedObj = JSON.parse(JSON.stringify(this))

를 이용해서 풀어냈는데, 원래 1초만에 완료하던걸 4초나 걸린다^^;;
일단 객체깊은복사참고링크 를 보고 가장쉬운 방법으로 했고.
1번의 방법으로 하니까, 오류가 뜬다 ㅠ 오류를 잡아내기엔 시간이 걸릴거같아서
이건 다음으로 미뤄둬야겠다.

BST inorder 메소드 코드수정

와.. 재귀함수를 정말 간단하게 사용하는 방법을 배웠다.
혁신적이다. 재귀사랑해 ㅠㅠ

inorder(callback) {
  // 1. if 왼쪽자식이 존재하면, 왼쪽자식 재귀함수 호출
  // 2. callback(this.value)
  // 3. if 오른쪽자삭이 존재하면, 오른쪽자식 재귀함수 호출
}

아직 재귀에 대한 실력과 공부가 짧아서, 너를 이렇게 자유자재로 사용할 수 없었음이 너무 슬프다.
더 많이 배우고, 익혀서 진짜 짧고 멋진 코드를 만들어내는 개발자가 되고싶다.
휴 이렇게, 일주일간의 자료구조 공부를 마무리한다.
다음주부터는 자료구조를 이용한 알고리즘 공부를 시작한다는데, 정말 기대된다.
어렵기도 하겠지만, 또 얼만큼 성장할지..! 코딩 너무 재미있다.