Tree 구현을 위한 기본적인 코드를 작성해보고, Tree 자료구조의 특성을 이해해보았다.
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node가 된다.
this.value = value;
this.children = []; // 자식노드들도 객체형태인데 이 노드들을 담을 배열
}
// 노드를 삽입하는 메소드
insertNode(value) {
const childNode = new Tree(value); //인스턴스 객체(=자식노드) 생성
this.children.push(childNode); //자식노드를 푸시
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메소드
contains(value) {
if (this.value === value) {
return true;
}
// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
else{
for(let i=0; i<this.children.length; i++){
const childNode = this.children[i];
if (childNode.contains(value)) { //자식노드들이 value를
return true;
}
}
}
// 전부 탐색했음에도 true가 나오지 않는다면 마지막엔 false 반환
return false;
}
}
사용 예시를 보면,,,
const rootNode = new Tree(null);
for(let i = 0; i <= 4; i++) {
if(rootNode.children[i]) {
rootNode.children[i].insertNode(i)
}
rootNode.insertNode(i);
}
rootNode; // 초반엔 rootNode에 자식 노드들이 한 개도 없으므로 rootNode = {value: null, children: Array(5)}
rootNode.contains(5); //false
rootNode.contains(1); //true
오늘 토이문제에서는 트리를 '클래스 컴포넌트'가 아니라 '함수 컴포넌트'로 구현한 것을 알 수 있었다. 두 방식에 문법적 차이가 조금 있다.
let Node = function (value) {
this.value = value;
this.children = [];
};
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};
먼저 tree의 형태가 어떻게 되어져 있는지, 그리고 탐색 순서가 어떻게 되는지를 확인해보기 위하여 아래와 같이 그려보았다
//BFS는 queue를 활용한다
//탐색의 대상이 되는 노드를 queue에 넣고
//그 queue에서 하나가 shift될 때
//그 shift되는 노드의 자식노드들을 한번 훑어서 빈배열에 담아주고(탐색을 완료했다는 표시와도 같은 것),
//탐색된 자식노드들을 queue에 모두 넣는다(자식노드들도 탐색해야 하므로)
let bfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let values = [node.value] //그 값이 들어가고
let queue = [node] //노드 자체가 들어간다
while(queue.length!==0){
let search = queue.shift(); //탐색 시작할 노드 하나 빼서
for(let i=0; i<search.children.length; i++){ //그 노드의 children 배열을 순회
values.push(search.children[i].value) //값은 values에 밀어넣고
queue.push(search.children[i]) //children노드는 또 탐색을 해주기 위해 queue에 넣어준다
}
}
return values;
};
탐색 순서가 어떻게 되는지를 확인해보기 위하여 아래와 같이 그려보았다
//탐색의 대상이 되는 루트 노드의 value를 values라는 배열에 넣고
//자식노드들을 하나하나 훑기 시작한다(for반복문)
//훑을 때 values에다가 그 자식노드의 value 값을 concat 해준다.(재귀함수 호출)
//자식노드가 더 이상 없을 때? 바깥 반복문에서 상위노드의 다음 자식노드를 탐색한다.
let dfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let values = [node.value] //최상단 노드를 방문도장 찍고
for(let i=0; i<node.children.length; i++){
values = values.concat(dfs(node.children[i]))
//자식노드들을 탐색할 때 재귀함수를 호출하여 하나하나 values에 concat 시킨다!
}
return values;
};