Created
July 4, 2016 07:24
-
-
Save ben8p/deedf1f8f4e1f52a1ab7fdec6615c3cb to your computer and use it in GitHub Desktop.
Binary tree in JS (Breadth first search, insort, insert)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** recursively search in the tree where the current value can be inserted */ | |
function find(value, node) { | |
if(node.value === undefined || node.value === value) { | |
return node; | |
} | |
if(node.value > value) { | |
return find(value, node.left); | |
} | |
return find(value, node.right); | |
} | |
/** traverse the tree with insort method */ | |
function inSort(node) { | |
var value = []; | |
if(node.left) { | |
value = value.concat(inSort(node.left)); | |
} | |
if(node.value !== undefined) { | |
value = value.concat([node]); | |
} | |
if(node.right) { | |
value = value.concat(inSort(node.right)); | |
} | |
return value; | |
} | |
/* create a tree from an array of values */ | |
function createTree(values, rootIndex) { | |
var root = { | |
left: {}, | |
right: {}, | |
value: values[rootIndex] | |
}; | |
values.forEach(function(value) { | |
var node = find(value, root); | |
if(value === node.value) { return; } | |
node.value = value; | |
node.left = {}; | |
node.right = {}; | |
}); | |
return root; | |
} | |
/* breadth first search */ | |
function BFS(tree) { | |
var levels = []; | |
function traverse(root, level) { | |
level = level || 0; | |
levels[level] = levels[level] || []; | |
var nextLevel = level + 1; | |
if(root.left) { | |
traverse(root.left, nextLevel); | |
} | |
if(root.value) { | |
if(!levels[level]) { debugger; } | |
levels[level].push(root.value); | |
} | |
if(root.right) { | |
traverse(root.right, nextLevel); | |
} | |
return levels; | |
} | |
return traverse(tree).join("\n"); | |
} | |
//values to put in the tree | |
var values = [88,97,56,41,27,16,95,54,28]; | |
//create tree | |
var tree = createTree(values, 0); | |
console.log('tree:', tree); | |
//insort tree traversing | |
var sorted = inSort(tree); | |
console.log('sorted:', sorted); | |
//recreate tree with median as starting point | |
var median = sorted[Math.round(sorted.length / 2)].value; | |
var treeMedian = createTree(values, values.indexOf(median)); | |
console.log('tree median (', median, '):', treeMedian); | |
//Breadth first search | |
console.log(BFS(treeMedian)); | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment