트리의 정의(Definition of Tree)
🎈 위 그림에서 볼 수 있듯, Tree는 최상위에 root를 가지며, 각 Node는 data와 children을 가지고 있다.
root는 최상위 위치이기 때문에, 그 위에는 어떤 것도 존재할 수 없다.
나무의 뿌리 또는 뿌리를 제외한 나무를 뒤집어 놓았다고 상상하면 된다.
Tree는 기본적으로 추가( add() ), 삭제( remove() ) 기능을 사용하여 다루는데, 이 method는 Node class가 갖도록 작성하겠으며,
Tree class 내에서는 탐색 기능인 traverseDF(), traverseBF() method를 작성해보겠다.
(DFS - Depth First Search, BFS - Breadth First Search)
JavaScript의 class를 이용하여 Tree를 만들어 보자.
Node class를 먼저 작성해보겠다.
😐 지금까지 해온 것처럼, 생성자(constructor)를 이용하여 기본 변수를 선언해준다.
this.data는 data를 저장하기 위한 변수, this.children은 아래 뿌리처럼 생겨날 새로운 노드를 위한 변수다.
add()는 아래 위치로 새로운 Node를 생성해준다. this.children이 배열(array)를 갖기 때문에 push를 이용해 간단히 추가해준다.
remove()는 입력 받은 값(data)과 똑같은 값(data) Node를 제거해준다.
Array.prototype.filter()를 이용해서 입력 받은 값(data)과 같지 않은 값(data)만 다시 this.children으로 재할당 해준다.
😐 앞에서 언급했던 것처럼, Tree는 Root를 반드시 가져야 한다. 따라서 생성자(constructor)를 이용해 root를 선언해준다.
먼저, traverseBF() flow 이미지를 보고 코드를 설명해 보겠다.
traverseBF()는 너비 우선 탐색이다.
root에서부터 시작하여 한 단계씩 아래 위치(층이라고 생각하면 쉽다)로 이동하여 Node를 탐색한다.
위의 이미지를 이용해 이해하면 조금 더 쉽다.
그림의 오른쪽에 Array처럼 배열을 만들어주고, 가장 먼저 this.root를 넣어준다.(Array는 탐색 순서)
그리고 while loop을 이용해 Tree를 모두 탐색하고 array가 빌(empty) 때까지 반복해주면 된다.
fn은 const letters = []; traverseBF(node => letters.push(node.data);)처럼 letters에 검색한 모든 data를 넣어주는
function이다.
arr에 children을 넣을 때, ES2015 Spread를 이용하면 편하지만, for ... of를 이용해도 된다.
다음은 traverseDF()다. 먼저, traverseDF flow 이미지를 보고, 코드를 설명해 보겠다.
TraverseDF()는 깊이 우선 탐색이다.
root에서부터 시작하여 가장 깊은 곳(가장 아래 단계)을 먼저 탐색하는 알고리즘이다.
그림에서처럼 20 -> 0 -> 12 -> -2 -> 1 ... 순서대로 깊이 위치해 있는 Node부터 탐색한다.
traverseBF()와 마찬가지로 Array를 만들어서 탐색한 Node를 순서대로 넣어준다.
20 이후에 0, 40, -15 를 갖는 Node가 Array에 들어가지만, 0의 자식 Node가 또 존재하므로, Array의 앞쪽에 Node를 넣어준다.
이 기능은 Array.prototype.unshift()를 이용해주면, Array의 가장 앞에 Node를 넣어줄 수 있다.
그리고 fn(node)를 이용해 모든 노드의 data를 letters에 저장해준다.
결과적으로,
traverseBF()의 letters에는 [ 20, 0, 40, -15, 12, -2, 1, -2 ] 가 들어가 있을 것이고,
traverseDF()의 letters에는 [ 20, 0, 12, -2, 1, 40, -15, 2 ] 가 들어가 있을 것이다.
위와 같이 Tree와 DFS, BFS를 작성해보았다.
다음 글에서는 Tree와 관련된 알고리즘(Level Width, Validate, Binary Search Tree)를 작성해보겠다.
Full Code
| class Node { |
| constructor(data) { |
| this.data = data; |
| this.children = []; |
| } |
| add(data) { |
| this.children.push(new Node(data)); |
| } |
| remove(data) { |
| this.children = this.children.filter(node => { |
| return node.data !== data; |
| }); |
| } |
| } |
| class Tree { |
| constructor() { |
| this.root = null; |
| } |
| traverseBF(fn) { |
| const arr = [this.root]; |
| while (arr.length) { |
| const node = arr.shift(); |
| arr.push(...node.children); |
| fn(node); |
| } |
| } |
| traverseDF(fn) { |
| const arr = [this.root]; |
| while (arr.length) { |
| const node = arr.shift(); |
| arr.unshift(...node.children); |
| fn(node); |
| } |
| } |
| } |
'JavaScript > Data Structure' 카테고리의 다른 글
| [Tree] Binary Search Tree(이진 탐색 트리) (0) | 2020.01.13 |
|---|---|
| [Tree] Level Width(트리 각 층의 너비(=개수) 알아내기) (0) | 2020.01.13 |
| [Linked List] From Last(마지막 Node에서 n번째 앞에 Node) (0) | 2020.01.09 |
| [Linked List] Check Linked List Circular(순환 Linked List 확인하기) (0) | 2020.01.09 |
| [Linked List] Find the Midpoint(Linked Lists의 중간 Node 찾기) (0) | 2020.01.09 |
