class BinaryTree {
constructor (node = null) {
this.node = node
}
*preorder () {
if (this.node) {
yield this;
yield* this.node.left.preorder();
yield* this.node.right.preorder();
}
}
*inorder () {
if (this.node) {
yield* this.node.left.inorder();
yield this;
yield* this.node.right.inorder();
}
}
*postorder () {
if (this.node) {
yield* this.node.left.postorder();
yield* this.node.right.postorder();
yield this;
}
}
}
class BinaryTreeNode {
constructor (entry,left,right) {
[this.entry,this.left,this.right] = [entry,left,right]
}
toString() {
if (this.entry instanceof String) return this.entry;
return this.entry.toString()
}
}
function BT (...args) {
if (args.length == 0) return new BinaryTree ()
return new BinaryTree(new BinaryTreeNode(...args))
}
bt = BT("A",BT("B",BT(),BT()),BT("C",BT(),BT()))
draw(bt)
bt2 = BT("A", BT("B", BT("D", BT(), BT()), BT()), BT("C", BT(), BT()))
draw(bt2)
[...bt2.inorder()].map(tree => tree.node.entry)
[...bt2.preorder()].map(tree => tree.node.entry)
[...bt2.postorder()].map(tree => tree.node.entry)
class Entry {
constructor (key,value = null) {
[this.key,this.value] = [key,value]
}
toString () {
if (this.value) return `${this.key} (${this.value})`
return `${this.key}`
}
}
class BinarySearchTree extends BinaryTree {
constructor (...args) {
super(...args);
}
find (key) {
if (!this.node) return this;
else if (this.node.entry.key < key) return this.node.right.find(key);
else if (this.node.entry.key > key) return this.node.left.find(key);
else return this;
}
insert (entry) {
let t = this.find (entry.key);
if (t.node) throw `This key already in tree: ${entry.key}`;
t.node = new BinaryTreeNode (entry, new BinarySearchTree(),
new BinarySearchTree())
return t
}
leftmost () {
if (!this.node.left.node) return this;
return this.node.left.leftmost();
}
delete(key = this.node.entry.key) {
let t = this.find (key);
if (!t.node) throw `This key does not exist in the tree: ${key}`;
if (!t.node.left.node && !t.node.right.node) {
t.node = null;
}
else if (!t.node.left.node) {
t.node = t.node.right.node
}
else if (!t.node.right.node) {
t.node = t.node.left.node
}
else {
let l = t.node.right.leftmost();
t.node.entry = l.node.entry;
l.delete()
}
}
clone() {
if (!this.node) return new BinarySearchTree();
return new BinarySearchTree (new BinaryTreeNode (this.node.entry,
this.node.left.clone(),
this.node.right.clone()))
}
}
// A função vai criar um objeto da classe "BinarySearchTree" com inicialmente com apenas um nó nulo e para cada elemento do array que vamos passar como argumento da função (entries) formado por [key, value], vamos inserir nessa árvore um objeto da classe "Entry" com essa chave e valor
function BST(entries) {
let t = new BinarySearchTree();
for (let [k,v] of entries) t.insert(new Entry(k,v))
return t
}
t = BST([[13,"A"],[14,"B"],[3,"C"],[16,"D"],[2,"E"],[9,"F"],[1,"G"],[4,"H"],[11,"L"],[6,"I"],[5,"J"],[7,"K"]])
draw(t)
q = {
let q = t.clone();
q.delete(2);
return q;
}
draw(q)
z = {
let z = t.clone();
z.delete(1);
return z;
}
draw(z)
draw = (tree) => dot`${graphViz(tree)}`
dot = require("@observablehq/graphviz@0.2")
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
