//! 1진트리
class Tree {
//tree의 constructor를 생성 : tree의 자식 노드들을 엘리먼트로 담을 children 배열로 선언
constructor(value) {
this.value = value
this.children = []
}
// 자식 노드 생성 메소드 구현 : new 키워드로 자식 노드를 생성 한 후, children 배열에 push
insertNode(value) {
const childNode = new Tree(value)
this.children.push(childNode)
}
// tree에서 value값을 탐색하기 위한 메소드 구현
contains(value) {
// 현재 노드의 value 값이 찾는 값과 일치한다면 true 반환
if (this.value === value) {
return true
}
// 자식 노드에서 value값을 탐색하기 위해 반복문과 재귀패턴 사용
for (let childNode of this.children) {
if (childNode.contains(value)) {
return true
}
}
// 조건에 해당하지 않으면 false 반환
return false
}
}
//! 작으면 왼쪽 크면 오른쪽으로 가는 이진 트리
class BinarySearchTree {
//BST의 constructor를 구현합니다.
constructor(value) {
this.value = value
this.left = null
this.right = null
}
// tree에 value를 추가합니다.
insert(value) {
// 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행합니다.
if (value < this.value) {
// this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
if (this.left === null) {
this.left = new BinarySearchTree(value)
}
// this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
else {
this.left.insert(value)
}
}
// 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행합니다.
else if (value > this.value) {
// this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가합니다.
if (this.right === null) {
this.right = new BinarySearchTree(value)
}
// this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용합니다.
else {
this.right.insert(value)
}
} else {
// 이미 value값을 포함하고 있습니다.
}
}
// tree의 value값을 탐색합니다.
contains(value) {
// 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
if (value === this.value) {
return true
}
// 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행합니다.
if (value < this.value) {
return !!(this.left && this.left.contains(value))
}
// 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행합니다.
if (value > this.value) {
return !!(this.right && this.right.contains(value))
}
}
//tree를 전위 순회 합니다.
preorder(callback) {
callback(this.value)
if (this.left) {
this.left.preorder(callback)
}
if (this.right) {
this.right.preorder(callback)
}
}
// tree를 중위 순회 합니다
inorder(callback) {
if (this.left) {
this.left.inorder(callback)
}
callback(this.value)
if (this.right) {
this.right.inorder(callback)
}
}
//tree를 후위 순회 합니다
postorder(callback) {
if (this.left) {
this.left.postorder(callback)
}
if (this.right) {
this.right.postorder(callback)
}
callback(this.value)
}
}
class Tree2 {
constructor(value, level = 0) {
this.value = value
this.left = null
this.right = null
this.level = level
}
insert(value, parent = {}, completedLevel) {
function findCurrentLevel(value) {
let result = 0
while (value > 1) {
result++
value = ~~(value / 2)
}
return result
}
let node = this
if (node.left === null) node.left = new Tree2(value, this.level + 1)
else if (node.right === null) node.right = new Tree2(value, this.level + 1)
else {
const now = this
if (Object.keys(parent).length > 0) {
if (node.right === null) this.insert(value, now)
else if (parent.right.right === null) parent.right.insert(value, parent)
else node.left.insert(value, now)
} else node.left.insert(value, now)
}
}
}
let tree2 = new Tree2(1)
tree2.insert(2)
tree2.insert(3)
tree2.insert(4)
tree2.insert(5)
tree2.insert(6)
tree2.insert(7)
tree2.insert(8)
tree2.insert(9)
tree2.insert(10)
tree2.insert(11)
tree2.insert(12)
// 위에서부터 가로 순서대로 1,2,3... 들어가는 트리를 만들어보려고 했는데 너무 복잡하다
// 현재 코드로는 11까지만 정상적으로 들어가는데
// 보안하려면 현재 값이 어느레벨인지, 해당 레벨의 뿌리를 2개씩 나눴을때 몇번째 덩어리에 속했는지를 파악해서
// 어느 부모까지 올라가야하는지 확인해야할것같다
// -> 부모가 왼쪽인지 오른쪽인지를 확인하면서 가면 될것같았는데 부모의 부모를 참조 못함
// -> 물론 노드에 부모 정보를 다 넣어주면 되지만 그러면 노드하나하나가 너무 무거워짐