This is a JSFiddle assignment and must be completed at jsfiddle.net and include
ID: 3777896 • Letter: T
Question
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 3Explanation / Answer
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 />
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.