sprint-data-structure-第3部首都コードと短い後期文章を方法別に整理する


🌲グラフィック
/*
 *  - 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 오른쪽자삭이 존재하면, 오른쪽자식 재귀함수 호출
    }
    まだ復帰していない実力と勉強が、こんなに自由自在に使えないのは悲しい.
    もっと勉強して、もっとマスターして、本当に短くてかっこいいコードを作った開発者になりたいです.
    こうして、1週間の資料構造学習を終了します.
    来周から资料构造を利用したアルゴリズムを勉强するそうで、楽しみです.
    ちょっと難しかったけどどこまで成長するのかわからず…!コードが面白すぎる