💡Binary Tree
- 번역하면 이진트리
- 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리구조
- 자식 노드를 최대 2개만 가질 수 있으므로 두 자식 노드를 왼쪽 자식, 오른쪽 자식으로 구별해서 지칭한다.
📌종류
Full Binary Tree
- 번역하면 정이진트리
- 모든 노드가 2개 또는 0개의 자식을 갖는 이진트리
Complete Binary Tree
- 번역하면 완전이진트리
- 마지막 레벨을 제외한 모든 노드가 가득 차있으며, 마지막 레벨의 노드는 전부 차있지않더라도 왼쪽은 채워진 트리구조
Perfect Binary Tree
- 번역하면 포화이진트리
- 정이진트리이면서 완전이진트리인 경우로, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져있는 트리구조
💡Binary Search Tree
- 번역하면 이진탐색트리
- 모든 왼쪽자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 트리구조
📌BST 구현
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.inert(value);
}
}else{
}
}
contains(value) {
if(value === this.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));
}
}
preorder(callback) {
callback(this.value);
if(this.left) {
this.left.preorder(callback);
}
callback(this.value);
if(this.right) {
this.right.preorder(callback);
}
}
postorder(callback) {
if(this.left) {
this.left.postorder(callback);
}
if(this.right) {
this.right.postorder(callback);
}
callback(this.value);
}
}