<!DOCTYPE html>
<html>
<head>
<link data-require="jasmine@2.2.1" data-semver="2.2.1" rel="stylesheet" href="http://cdnjs.cloudflare.com/ajax/libs/jasmine/2.2.1/jasmine.css" />
<script data-require="jasmine@2.2.1" data-semver="2.2.1" src="http://cdnjs.cloudflare.com/ajax/libs/jasmine/2.2.1/jasmine.js"></script>
<script data-require="jasmine@2.2.1" data-semver="2.2.1" src="http://cdnjs.cloudflare.com/ajax/libs/jasmine/2.2.1/jasmine-html.js"></script>
<script data-require="jasmine@2.2.1" data-semver="2.2.1" src="http://cdnjs.cloudflare.com/ajax/libs/jasmine/2.2.1/boot.js"></script>
<script src="binary-tree.js"></script>
</head>
<body>
<h1>Binary tree data structure in JavaScript</h1>
<p>Example from <a
href="http://www.i-programmer.info/programming/javascript/1899-javascript-data-structures-the-binary-tree.html"
target="_blank">I Programmer</a> with Jasmine tests added.
</p>
<script src="binary-tree-tests.js"></script>
</body>
</html>
// Binary tree data structure example courtesy I Programmer
// http://www.i-programmer.info/programming/javascript/1899-javascript-data-structures-the-binary-tree.html
// A binary tree is a tree structure where each node (except for the terminal nodes)
// has exactly two children. You can specify an element on the tree with two
// indices: the level (how far down) and the node number (how far to the right).
// This example uses a storage mapping function to increase search performance.
// I'm given to understand it only works for trees with a fixed branching factor
// and no missing nodes.
// example: 0
// / \
// 0 1
// / \ / \
// 0 1 2 3
//
// Storage location 0 1 2 3 4 5 6
// level 0 | 1 | 2
// node 0 | 0 1 | 0 1 2 3
function BinaryTree() {
// for node-based navigation
this.level = 0; // current level we're on
this.node = 0; // current node we're on
// shift-based formula works only on a binary tree.
// 1<<k is 2^k
// so location = node + 2^level - 1
// "binary tree Storage Management Function"
this.btSMF = function(level, node) {
return node + (1<<level) - 1;
}
// I think this is the easier-to-grok equivalent with Math.pow...
this.btSMFPow = function(level, node) {
return node + Math.pow(2, level) - 1;
}
// where we keep 'em
this.Nodes = new Array();
// get a node using the bit-shift
// if level isn't supplied, return value of the current node
this.getNode = function(level, node) {
if (level === undefined) {
return this.Nodes[this.btSMF(this.level, this.node)];
} else {
return this.Nodes[this.btSMF(level, node)];
}
}
// set a node using the bit-shift
// if level argument is supplied use it, otherwise use current location level
this.setNode = function(value, level, node) {
if (level === undefined) {
this.Nodes[this.btSMF(this.level, this.node)] = value;
} else {
this.Nodes[this.btSMF(level, node)] = value;
}
}
// get a node using the Math.pow alternative
// didn't implement node position effects in this version
this.getNodePow = function(level, node) {
return this.Nodes[this.btSMF(level, node)];
}
// set a node using the Math.pow alternative
// didn't implement node position effects in this version
this.setNodePow = function(value, level, node) {
this.Nodes[this.btSMFPow(level, node)] = value;
}
// set the current position to the root: tree.root()
// set the value at the root: tree.root(100)
// get the value at the root: rootvalue = tree.root()
// this one uses the bitshifted SMF
this.root = function(value) {
this.level = 0;
this.node = 0;
// if a value was supplied, set it
if (value !== undefined) {
this.Nodes[this.btSMF(this.level, this.node)] = value; // level 0, node 0
}
// return the root node value
return this.Nodes[this.btSMF(this.level, this.node)];
}
// alternate version of root using Math.pow, just to double-check
this.rootPow = function(value) {
this.level = 0;
this.node = 0;
if (value !== undefined) {
this.Nodes[this.btSMFPow(this.level, this.node)] = value;
}
return this.Nodes[this.btSMFPow(this.level, this.node)];
}
// get the left child of a parent: tree.leftChild()
// set the left child of a parent: tree.leftChild(6);
this.leftChild = function(value) {
this.level++;
this.node = this.node * 2; // see diagram above
if (value !== undefined) {
this.Nodes[this.btSMF(this.level, this.node)] = value;
}
return this.Nodes[this.btSMF(this.level, this.node)];
}
// same but for right child
this.rightChild = function(value) {
this.level++;
this.node = this.node * 2 + 1; // see diagram above
if (value !== undefined) {
this.Nodes[this.btSMF(this.level, this.node)] = value;
}
return this.Nodes[this.btSMF(this.level, this.node)];
}
// get the parent of the current node
this.parent = function(value) {
this.level--;
this.node = this.node >> 1; // alternatively, Math.floor(this.node / 2) prolly
if (value !== undefined) {
this.Nodes[this.btSMF(this.level, this.node)] = value;
}
return this.Nodes[this.btSMF(this.level, this.node)];
}
// recursively traverse the tree in an inner function
this.traverse = function() {
var that = this, // reference to the tree
stack = new Array(); // store traversal results
// recursive inner function that immediately executes from current node position
(innerTraverse = function() {
// push current node value onto the stack
stack.push(that.getNode());
// if it has a left child, go there and traverse, then come back
if (that.leftChild() !== undefined) {
innerTraverse();
}
that.parent();
// if it has a right child, go there and traverse, then come back
if (that.rightChild() !== undefined) {
innerTraverse();
}
that.parent();
})();
// done recursing, return our array
return stack;
}
}
// Jasmine tests for JavaScript binary tree
describe('should be able to perform binary tree operations', function() {
var tree;
// These tests use shift-based node operation methods as in the I Programmer example
describe('should operate correctly using the shift-based methods', function() {
beforeEach(function() {
tree = new BinaryTree();
// setNode(value, level, node)
tree.setNode(1, 0, 0); // level 0
tree.setNode(2, 1, 0); // level 1
tree.setNode(3, 1, 1);
tree.setNode(4, 2, 0); // level 2
tree.setNode(5, 2, 1);
tree.setNode(6, 2, 2);
tree.setNode(7, 2, 3);
});
afterEach(function() {
tree = null;
});
it('should be able to set and get nodes using the shift-based SMF methods', function() {
// getNode(level, node)
expect(tree.getNode(1, 1)).toEqual(3);
expect(tree.getNode(2, 2)).toEqual(6);
});
it('should be able to get and set node values based on the current level and node', function() {
// test the alternate paths in get and set when level is omitted
tree.level = 2;
tree.node = 1;
expect(tree.getNode()).toEqual(5); // uses current level & node
expect(tree.getNode(2,1)).toEqual(5); // uses specified level & node
expect(tree.getNode(2,0)).toEqual(4); // make sure the neighbors are fine
expect(tree.getNode(2,2)).toEqual(6);
// set value of current node without specifying level or node
tree.setNode(73);
expect(tree.getNode()).toEqual(73); // current value
expect(tree.getNode(2,1)).toEqual(73); // specify level & node
expect(tree.getNode(2,0)).toEqual(4); // make sure the neighbors are fine
expect(tree.getNode(2,2)).toEqual(6);
});
it('should be able to do root node stuff using the shift-based SMF method', function() {
expect(tree.root()).toEqual(1);
expect(tree.root(100)).toEqual(100);
tree.root(50);
expect(tree.getNode(0,0)).toEqual(50);
});
it('should be able to perform operations on the left child of a node', function() {
// set current node to the root node
tree.root();
expect(tree.leftChild()).toEqual(2);
expect(tree.getNode(1,0)).toEqual(2);
expect(tree.level).toEqual(1);
expect(tree.node).toEqual(0);
tree.root();
tree.leftChild(99);
expect(tree.getNode(1,0)).toEqual(99);
expect(tree.level).toEqual(1);
expect(tree.node).toEqual(0);
});
it('should be able to perform operations on the right child of a node', function() {
// set current node to the root node
tree.root();
expect(tree.rightChild()).toEqual(3);
expect(tree.getNode(1,1)).toEqual(3);
expect(tree.level).toEqual(1);
expect(tree.node).toEqual(1);
tree.root();
tree.rightChild(99);
expect(tree.getNode(1,1)).toEqual(99);
expect(tree.level).toEqual(1);
expect(tree.node).toEqual(1);
});
it('should be able to perform simple traversal sequences', function() {
// test simple traversal
var testedValue = tree.root(); // root node
expect(tree.level).toEqual(0);
expect(tree.node).toEqual(0);
expect(testedValue).toEqual(1);
testedValue = tree.leftChild(); // left child of root node
expect(tree.level).toEqual(1);
expect(tree.node).toEqual(0);
expect(testedValue).toEqual(2);
testedValue = tree.rightChild(); // right child of the above node
expect(tree.level).toEqual(2);
expect(tree.node).toEqual(1);
expect(testedValue).toEqual(5);
testedValue = tree.parent();
expect(tree.level).toEqual(1);
expect(tree.node).toEqual(0);
expect(testedValue).toEqual(2);
});
it('should be able to traverse the tree', function() {
var traverseValue;
tree.root();
traverseValue = tree.traverse();
// values come in odd orders because of traversal, check to make sure all are there
expect(traverseValue).toContain(1);
expect(traverseValue).toContain(2);
expect(traverseValue).toContain(3);
expect(traverseValue).toContain(4);
expect(traverseValue).toContain(5);
expect(traverseValue).toContain(6);
expect(traverseValue).toContain(7);
expect(traverseValue.length).toEqual(7);
});
}); // shift-based tests
// These tests use the Math.pow variants to get and set nodes
// I didn't do every possible op this way, was just curious
describe('should operate correctly using Math.pow-based methods', function() {
beforeEach(function() {
tree = new BinaryTree();
// setNodePow(value, level, node)
tree.setNodePow(1, 0, 0);
tree.setNodePow(2, 1, 0);
tree.setNodePow(3, 1, 1);
tree.setNodePow(4, 2, 0);
tree.setNodePow(5, 2, 1);
tree.setNodePow(6, 2, 2);
tree.setNodePow(7, 2, 3);
});
afterEach(function() {
tree = null;
});
it('should be able to set and get nodes using the Math.pow methods', function() {
// getNodePow(level, node)
expect(tree.getNodePow(1, 1)).toEqual(3);
expect(tree.getNodePow(2, 2)).toEqual(6);
});
it('should be able to do root node stuff using the Math.pow SMF method', function() {
expect(tree.rootPow()).toEqual(1);
expect(tree.rootPow(100)).toEqual(100);
tree.rootPow(50);
expect(tree.getNodePow(0,0)).toEqual(50);
});
});
});