Homework SourseThis is a JSFiddle assignment and must be completed at jsfid
This is a JSFiddle assignment and must be completed at jsfiddle.net and include both the HTML and Java sections
A common use for trees is the Expression Tree. This is a specific case of a binary tree. When you write an equation, the computer stores the equation in a tree - which stores both the operations and the expression order.
We will give an example 2 - 3 * 4 + 5
The expression tree for this is;
If we traverse the tree using left - first traversal - the first dead end node is 2, then traverse back up to - and down to * and then down again to 3, then up to * and back down to 4 - so the traversal order without intermediate points is
2, 3, 4, *, - 5, +
The logical execution order is
3, 4, * = result
2, result, - = result
result, 5, + = result
or if you were to put it in logical order 2 - 3*4 + 5 , our original equation. For this assignment you will create a binary tree representation of the equation
So output should be (if I enter 1,1)
Input X : [ 1 ]
Input Y: [ 1 ]
X = 1, Y=1, Output = 18
2 ( 4 5 3Solution
Javascript:
var binaryTree = function () {
this.root = null;
var binaryTreeNode = function (content) {
this.left = null;
this.right = null;
this.content = content;
};
this.createEquationTree = function() {
this.root = null;
var tempNode;
tempNode = this.add(\"3\");
tempNode = this.addLeft(tempNode,\"*\");
tempNode = this.addLeft(tempNode,\"+\");
this.addRight(tempNode,\"X\");
tempNode = this.addLeft(tempNode,\"*\");
this.addLeft(tempNode,\"5\");
this.addRight(tempNode,\"Y\");
};
this.traverse = function (process) {
function inOrder(node) {
if (node) {
if (node.left !== null) {
inOrder(node.left);
}
process.call(this, node);
if (node.right !== null) {
inOrder(node.right);
}
}
}
//start with the root
inOrder(this.root);
};
this.addLeft = function (node, value) {
var newNode = new binaryTreeNode(value);
node.left = newNode;
return newNode;
}
this.addRight = function (node, value) {
var newNode = new binaryTreeNode(value);
node.right = newNode;
return newNode;
}
this.add = function (value) {
var newNode = new binaryTreeNode(value);
if (this.root == null) {
this.root = newNode;
console.log(\"added \'\" + value + \"\' at root \");
return newNode; //this.root;
}
current = this.root;
while (current !== null) {
console.log(current.content);
if (value < current.content) {
if (current.left === null) {
current.left = newNode;
console.log(\"add \'\" + value + \"\' at left of \" + current.content);
break;
} else {
current = current.left;
}
} else if (value > current.content) {
if (current.right === null) {
current.right = newNode;
console.log(\"add \'\" + value + \"\' at right of \" + current.content);
break;
} else {
current = current.right;
}
} else {
break;
}
}
}
this.contains = function (value) {
var node = this.root;
ll.traverse(function (node) {
if (node.content == value) return node;
});
return null;
};
this.toArray = function () {
var newArray = [];
var node = this.root;
ll.traverse(function (node) {
newArray.push(node.content);
});
return newArray;
};
};
binaryTree.prototype.length = function () {
var length = 0;
var node = this.root;
ll.traverse(function (node) {
console.log( length + \" -- \" + node.content);
length++;
});
return length;
};
binaryTree.prototype.lengthLongVersion = function () {
current = this.root;
var size = 0;
var leftsize = 0;
var rightsize = 0;
if (current === null) return size;
size++;
while (current !== null) {
if (current !== this.root) {
size += 1;
console.log(current.content);
}
if (current.left !== null) leftsize++;
current = current.left;
}
current = this.root;
while (current !== null) {
if (current !== this.root) {
size += 1;
console.log(current.content);
}
if (current.right !== null) rightsize++;
current = current.right;
}
console.log(\"left: \" + leftsize);
console.log(\"right: \" + rightsize);
return size;
};
binaryTree.prototype.calculate = function () {
this.createEquationTree();
var node = this.root;
var theNumbers = [];
var theOperators = [];
ll.traverse(function (node) {
if (node.content == \"X\") {
console.log(\'x\');
node.content = $(\'#xx\').val();
}
if (node.content == \"Y\") {
console.log(\'y\');
node.content = $(\'#yy\').val();
}
switch(node.content) {
case \"*\":
theOperators.push(node.content);
break;
case \"+\":
theOperators.push(node.content);
break;
default:
theNumbers.push(parseFloat(node.content));
break;
}
});
for (var i=0;i<theOperators.length;i++){
console.log(theOperators[i]);
}
for (var i=0;i<theNumbers.length;i++){
console.log(theNumbers[i]);
}
var ind=0;
var n1,n2;
for (var i=0;i<theOperators.length;i++){
switch (theOperators[i]) {
case \"*\":
n1=theNumbers[ind];ind++;
n2=theNumbers[ind];ind++;
theNumbers[--ind] = n1 * n2 ;
console.log(n1);
console.log(\"*\");
console.log(n2);
break;
case \"+\":
n1=theNumbers[ind];ind++;
n2=theNumbers[ind];ind++;
theNumbers[--ind] = n1 + n2 ;
console.log(n1);
console.log(\"+\");
console.log(n2);
break;
case \"-\":
n1=theNumbers[ind];ind++;
n2=theNumbers[ind];ind++;
theNumbers[--ind] = n1 - n2 ;
console.log(n1);
console.log(\"-\");
console.log(n2);
break;
case \"/\":
n1=theNumbers[ind];ind++;
n2=theNumbers[ind];ind++;
theNumbers[--ind] = n1 / n2 ;
console.log(n1);
console.log(\"/\");
console.log(n2);
break;
case \"^\":
n1=theNumbers[ind];ind++;
n2=theNumbers[ind];ind++;
theNumbers[--ind] = n1 ^ n2 ;
console.log(n1);
console.log(\"^\");
console.log(n2);
break;
}
}
console.log(theNumbers[ind]);
//(3*(x + 5*y))
document.getElementById(\"output\").innerHTML = \"( 3 * (\" + $(\'#xx\').val() + \" + 5 * \" + $(\'#yy\').val() + \")) = \" + theNumbers[ind];
};
binaryTree.prototype.toString = function () {
var asString = \"\";
var node = this.root;
ll.traverse(function (node) {
asString += node.content + \" \";
});
return asString;
};
$(\"#add\").click(function () {
ll.add($(\'#userValue\').val());
console.log(\"the tree in left-first order: \" + ll.toString());
});
$(\"#calc\").click(function () {
ll.calculate();
});
var ll=new binaryTree();
Html:
<div id=\"theE\" name=\"theE\" ></div>
X:<input type=\"number\" id=\"xx\" value=1 />
Y:<input type=\"number\" id=\"yy\" value=1 />
<br />
