Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Binary Search Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
- insert(value): 입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.
- contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
- preorder(callback): 전위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
- inorder(callback): 중위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
- postorder(callback): 후위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
value는 어떠한 값도 들어갈 수 있지만 현재 구현하는 Tree는 숫자로 제한합니다.
const rootNode = new BinarySearchTree(10);
rootNode.insert(7);
rootNode.insert(8);
rootNode.insert(12);
rootNode.insert(11);
rootNode.left.right.value; // 8
rootNode.right.left.value; //11
let arr = [];
rootNode.preorder((value) => arr.push(value * 2));
arr; // [20, 14, 16, 24, 22]
...
class BinarySearchTree {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
insert(value){
if(value < this.value){
if(this.left === null){
this.left = new BinarySearchTree(value);
} else {
this.left.insert(value);
}
} else if(value > this.value){
if(this.right === null){
this.right = new BinarySearchTree(value);
} else {
this.right.insert(value);
}
} else {
return false;
}
}
contains(value){
if(this.value === value){
return true;
}
if(value < this.value){
return !!(this.left && this.left.contains(value));
}
if(value > this.value){
return !!(this.right && this.right.contains(value));
}
return false;
}
// 전위 순회 (preorder);
preorder(callback){
callback(this.value);
if(this.left){
this.left.preorder(callback);
}
if(this.right){
this.right.preorder(callback);
}
}
// 중위 순회 (inorder)
inorder(callback){
if(this.left){
this.left.inorder(callback);
}
callback(this.value);
if(this.right){
this.right.inorder(callback);
}
}
// 후위 순회 (postorder);
postorder(callback){
if(this.left){
this.left.postorder(callback);
}
if(this.right){
this.right.postorder(callback);
}
callback(this.value);
}
}
특정값을 빠르게 찾을 수 있는 이진 탐색 트리입니다.
root(노드)에서 하위 노드로 계층 구조를 갖는 것을 트리라고 봅니다.
이진 탐색 트리에서는 root(노드)를 기준으로 작은 값(value)의 경우 왼쪽 하위 노드로, 큰 값(value)는 오른쪽 하위 노드가 됩니다. 이때 기준은 this.value입니다.