javascript - Issues with a recursive function when trying to create a BST using Pseudoclassical Inheritance -
so i'm trying create binary search tree using pseudoclassical inheritance. accepts array, sorts it, uses middle value starting point, , inserts remaining values array bst. guess i'm trying best utilize functional programming (correct me if i'm wrong please) using reuseable methods , because bst insert method needs recursive.
i've pointed out code errors out. believe takes 3 initial value, believe 1 (the next value in array) gets inserted, believe number 2 error occurs when says "typeerror: this.left.insert not function". can point out i'm doing wrong? why won't insert method call this.left?
var noduplicatesbst = function(array) { var temparr = arguments[0].sort(function(a, b) { return a-b; }); var middle = math.floor(((temparr.length - 1) / 2)); var sliced = temparr.splice(middle, 1); this.createbst(sliced[0]); // insert rest of temparr bst (var = 0; < temparr.length; i++) { this.insert(temparr[i]); } }; noduplicatesbst.prototype.createbst = function(number) { this.value = number; this.left = null; this.right = null; }; noduplicatesbst.prototype.insert = function(number) { if (number < this.value) { if (this.left === null) { this.left = new this.createbst(number); } else { // ------------code below not work!, lined 77 probably. typeerror: this.left.insert not function---------------------- this.left.insert(number); } } else if (number > this.value) { if (this.right === null) { this.right = new this.createbst(number); } else { this.right.insert(number); } } else { // nothing } }; var testbst = new noduplicatesbst([2,3,4,5,1]); console.log("the testbst:", testbst);
that's not written in functional way, take , try go thru tutorial learn more functional programming in js: http://reactivex.io/learnrx/
and original question why see "typeerror: this.left.insert not function"
. check comments in code:
var noduplicatesbst = function(arr) { var middle, left = [], center, right = []; if (!array.isarray(arr) || arr.length == 0) { return this; } if (arr.length == 1) { center = arr[0]; } else { middle = math.floor((arr.length / 2)); center = arr[middle]; left = arr.slice(0, middle); right = arr.slice(middle + 1, arr.length); console.log('left:', left); console.log('middle:', center); console.log('right:', right); } this.createbst(center); // insert left , right parts bst if (left.length > 0) { this.insert(left); } if (right.length > 0) { this.insert(right); } }; noduplicatesbst.prototype.createbst = function(number) { this.value = number; this.left = null; this.right = null; }; noduplicatesbst.prototype.insert = function(arr) { if (arr.length > 0) { //array sorted , took middle element, can compare first element if (arr[0] < this.value) { /** here use createbst constructor, creates new element, left , right values, break prototypal inheritance chain, that's why don't have access insert function */ // this.left = new this.createbst(number); // it's better pass part of array build tree further this.left = new noduplicatesbst(arr); } else { this.right = new noduplicatesbst(arr); //the same above } } }; var arr = [2, 3, 4, 5, 1]; var temparr = arr.reduce(function (noduplicatesarr, current) { //remove duplicates if (noduplicatesarr.indexof(current) === -1) { noduplicatesarr.push(current); } return noduplicatesarr; }, []).sort(function(a, b) { return - b; }); var testbst = new noduplicatesbst(temparr); console.log("the testbst:", testbst);
for prototypal chain inheritance check: https://developer.mozilla.org/en/docs/web/javascript/inheritance_and_the_prototype_chain
btw. changed code accept arrays instead of numbers, build bst
Comments
Post a Comment