self assment tree.map 구현에 대하여....

트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

 

이건 이진트리의 구조를 일단 나타내본 것이다.

javascript로 트리를 구현해보자

트리를 구현할려면 트리가 연결되는 부분 즉 노드가 필요하다.

노드를 작성해보자.

  //트리에 대해서.. 트리는 자식이 있다..
  var Tree = function(value) {
    this.value = value;
    this.children = [];
  };
 

tree의 value 값과 그 밑에 자식은 children으로 배열 형식으로 만들었다.

그렇다면 밑에 자식을 추가하는 건 어떻게 구현해볼까... 앗.. prototype으로 구현해보면 어떨까?...

  Tree.prototype.addChild = function(child) {
    // your code here
    let node = new Tree(child);
    this.children.push(node);//지정한 this밑에 자식을 추가.
  };

node도 트리 노드 형태이므로 tree노드로 생성해주고.. 

기존 this -> 부모 tree 객체의 children에 자식 노드를 집에 넣는다.

 

그렇다면 제일 어려워 하는 callback 함수를 가져와서 ... 그것을 모든 트리에 적용시키는 map 메소드를 만들어보자

그렇다면 모든 트리를 검색해야 할것이다.. 

  //모든 값들을 callback 함수를 이용해서 변경하라..
  Tree.prototype.map = function(callback) {
    let treeCopy = new Tree(callback(this.value));
    treeCopy.children = recursion(treeCopy.children,this.children,callback);
    return treeCopy;
  };

여기서 가장 중요한 첫번째는 map함수는 기존의 트리를 바꾸면 안된다. 

그렇기 떄문에 새로운 부모노드의 트리를 생성한다. 물론 그 트리의 부모의 값도 callback함수를 적용해서 생성을 해야겠죠?

다음은.. 자식들이다 .  자식을 살펴볼려면 무엇을 해야할까 바로 탐색이다. 

recursion 재귀를 사용해서 자식을 보는 것이다. 

자식의 children 배열의 길이가 0보다 크면 탐색을 하면된다 . 그리고 탐색한 자식노드들의 value값을 callback 함수를 적용한다.

그리고 자식 노드의 자식을 또 재귀를 돌려 탐색을 한다.

  function recursion(copychild,child, callback){
    for(let i=0;i<child.length;i++){ //자식을 처음부터 끝까지
      if(child[i].value){ //자식에 값이 존재하면
        copychild.push(new Tree(callback(child[i].value)));
      }
      if(child[i].children.length!==0){ //자식의 자식값이 존재한다면...
        let children = child[i].children; //실수하지말자 이부분...
        copychild[i].children = recursion(copychild[i].children,children,callback);
      }
    }
    return copychild;
  }

copychild 부모노드 , child 기존tree의 자식 노드.children , callback -> 각 노드의 value 값에 적용할 함수

 child는 배열이므로 for문을 이용해서 돌린다.

 그리고 그 배열의 각 인덱스 값에 value 값이 있따면 그 값을 callback함수를 이용해서 노드를 생성해 집어넣는다.

 그리고 제일 어려운 부분일수도 있는 자식의 자식의 배열길이 값이 0이 아닐떄... (자식이있다는것)

 let children = child[i].children ; 으로 자식 값을 가지고 온다. //새롭게 할당하지 않으면 기존 자식노드에 할당이 되어서 변해버릴수 잇으니 할당을 했다.

 copychild[i].children = recursion(copychild[i].children,children,callback); 위에서 가져온 copychild[i]의 자식부분에 , 자식의 자식부분을 집어넣고 ,callback 함수를 넘겨 준다. 또 다시 리커젼을 돌리면서 값들이 각노드의 자식에 값이 들어갈 것이다.

copychild로 각 노드마다 자식이 다 검색되면 거기에 맞게 들어가고 ... 맨위의 recursion이 있을거고 그밑에 자식 리커션이있다.

자식은 자식별로 변경이되며 그렇게 부모로 다 모이게된다.