[자료구조] 트리(Tree)란 - Heee's Development Blog
각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.
정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 수 있다.
정점이 N개인 포화 또는 완전 이진트리의 높이는 $logN$ 이다.
높이가 h인 포화 이진 트리는 $2^h-1$ 의 정점을 가진다.
일반적인 이진 트리를 사용하는 경우는 많지 않다.
주로 다음과 같은 경우에 응용된다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(newValue) {
const newNode = new Node(newValue);
if (this.head === null) {
this.head = this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size += 1;
}
dequeue() {
const value = this.head.value;
this.head = this.head.next;
this.size -= 1;
return value;
}
peek() {
return this.head.value;
}
}
class Tree{
constructor(node) {
this.root = node;
}
display() {
const queue = new Queue();
queue.enqueue(this.root);
while (queue.size) {
const currentNode = queue.dequeue();
console.log(currentNode.value);
if (currentNode.left) queue.enqueue(currentNode.left);
if (currentNode.right) queue.enqueue(currentNode.right);
}
}
}
const tree = new Tree(new Node(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);
console.log(tree.display());