+
2
|
list
|
skin
|
login
|
editor
α-wwwiki
::
BST
user:none
(2686 bytes)
{h1 binary search tree} {center {show {@ src="http://epsilonwiki.free.fr/data/Tree_roots.jpg" height="400" width="900" title="Trees and roots"}}} {p Javascript function's and object's properties give clean tools for BST code. Init (once) BST, edit the sequences of integers below, and sort them :} {input {@ id="input_1" type="text" style="width:580px;" value="5 1 10 3 9 2"} } {pre {@ id="output_1"}???} {input {@ id="input_2" type="text" style="width:580px;" value="100 50 40 35 123 -1"} } {pre {@ id="output_2"}???} First {input {@ type="submit" value="init BST" onclick="°° var js = document.createElement('script'); var input = getId('code').innerHTML; js.innerHTML = decode_html_entities(input); // < ,> document.head.appendChild( js ); this.value = 'OK, BST inited !'; this.disabled='disabled'; °°"}} then {input {@ type="submit" value="Sort" onclick="°° var bst1 = new BST; bst1.read( getId('input_1').value ); getId('output_1').innerHTML = bst1.display(); var bst2 = new BST; bst2.read( getId('input_2').value ); getId('output_2').innerHTML = bst2.display(); °°"}} the sequences. _h3 code {pre {@ id="code"}°° BST = function () { var root = null; // define our private variables // 1) NODE CREATION var node = function () { // node constructor var node = { value: null, left: null, right: null }; return node; }; // 2) ROOT CREATION root = new node(); root.left = new node(); root.right = new node(); // 3) NODE INSERTION IN A TREE var insert = function (value, curNode) { // if curNode isn't defined, set it to root curNode = curNode || root; if (curNode.value === null) { // empty spot has been found, so insert here! curNode.value = value; curNode.left = new node(); curNode.right = new node(); } else // if value is less than curNode left else right insert (value, value < curNode.value ? curNode.left : curNode.right); }; // 4) TREE WALK IN ORDER var str = ''; var walk = function (curNode) { // set default parameter for curNode to root curNode = curNode || root; if (curNode.value !== null) { walk (curNode.left); str += curNode.value + ' | '; walk (curNode.right); } }; // 5) INPUT READING var read = function (str) { var tab = str.split( / /g ); for (var i=0; i< tab.length; i++) insert( parseInt(tab[i]) ); }; // 6) OUTPUT DISPLAY IN ORDER var display = function() { walk(); return str; }; // 7) declare public functions return { read:read, display:display }; }; // end BST °°}