İkili ağaç (Binary Tree), her düğümün sol çocuk ve sağ çocuk olarak adlandırılan en fazla iki çocuğa sahip olduğu bir ağaç veri yapısıdır. Binary Search Tree'nin ikili ağaçtan temel farkı düğümlerde saklanan verilerin sıralı bir şekilde tutulmasıdır. Bunun sayesinde ağaç üzerinde arama yapılmasına olanak sağlar. Binary Search Tree'de eklenen veriler her zaman düğümde yer alan değerden küçük ise sol tarafa, aksi taktirde (büyükse) düğümün sağ tarafına eklenmelidir.
Javascript Binary Search Tree Kodu
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
let newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
} else {
let tempNode = this.root;
while (true) {
if (value < tempNode.value) {
if (tempNode.left === null) {
tempNode.left = newNode;
break;
}
tempNode = tempNode.left;
} else {
if (tempNode.right === null) {
tempNode.right = newNode;
break;
}
tempNode = tempNode.right;
}
}
}
}
find(value) {
if (this.root == null) return null;
let tempNode = this.root;
while (tempNode !== null) {
if (value < tempNode.value) {
tempNode = tempNode.left;
} else if (value > tempNode.value) {
tempNode = tempNode.right
} else {
break;
}
}
return tempNode;
}
inOnder(node, arr = []) {
if (node !== null) {
if (node.left !== null) this.inOnder(node.left, arr);
arr.push(node.value);
if (node.right !== null) this.inOnder(node.right, arr);
}
return arr;
}
preOnder(node, arr = []) {
if (node !== null) {
arr.push(node.value);
if (node.left !== null) this.inOnder(node.left, arr);
if (node.right !== null) this.inOnder(node.right, arr);
}
return arr;
}
postOnder(node, arr = []) {
if (node !== null) {
if (node.left !== null) this.inOnder(node.left, arr);
if (node.right !== null) this.inOnder(node.right, arr);
arr.push(node.value);
}
return arr;
}
}
Yukarıda yer alan Binary Search Tree Javascript kodunda ekleme, arama ve verileri sıralı bir şekilde ekrana basmanıza yarayacak fonksiyonlara yer verilmiştir.
Örnek Kod
let btree = new BinarySearchTree();
btree.insert(5);
btree.insert(12);
btree.insert(11);
btree.insert(55);
btree.insert(1);
btree.insert(5555);
btree.insert(3);
console.log(btree.find(5))