Binary Trees

Tree (of all sorts) are used throughout programming. You should become familiar with the types of trees and you will do a little bit of the use of trees. 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 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

by Neil Daley

HTML

<h1>
Binary Tree
</h1>

Tree (of all sorts) are used throughout programming.<br/>
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.<br/><br/>

<table>
 <b>
  <tr>
    <td>3 * (</td> 
    <td id="x">x</td>
    <td>+ 5 *</td>
    <td id="y">y</td>
    <td>) = </td>
    <td id="output">?</td>
  </tr>
 </b>
</table>

<!--
<table>
 <b>
  <tr>
    <td><h1><b>3 * (</b></h1></td> 
    <td id="x"><h1><b>x</b></h1></td>
    <td><h1><b>+ 5 *</b></h1></td>
    <td id="y"><h1><b>y</b></h1></td>
    <td><h1><b>) = </b></h1></td>
    <td id="output"><h1><b>?</b></h1></td>
  </tr>
 </b>
</table> -->

<div>
  <input type="text" id="inputx" placeholder="x value" onkeypress="handle(event)">
  <input type="text" id="inputy" placeholder="y value" onkeypress="handle(event)">
</div><br/>

<input type="button" value="Calculate" id="bt1" onClick="limitInput();" style="color:white; background-color:blue" /><br/><br/>

<div id="a"></div>
<div id="b"></div>
<div id="c"></div>

JavaScript

var a = 0;
var b = 0;

function handle(e) {
  var key = e.keyCode || e.which;
  if (key == 13) {
    limitInput();
  }
}

  // Node takes a value; left and right
  var Node = function(v, l, r) {
    this.value = v;
    this.left = l;
    this.right = r;
  }
  
  // calculates the given left and right values with a given operator and returns result
  function calculate(left, right, op) {
    if (op == '+') {
      return parseInt(left) + parseInt(right);
    } else if (op == '-') {
      return parseInt(left) - parseInt(right);
    } else if (op == '*') {
      return parseInt(left) * parseInt(right);
    } else {
      return parseInt(left) + parseInt(right);
    }
  }
  
  // integer check
  function isInteger(number) {
    return (number % 1 === 0);
  }
  
  // Recursive function for binary tree
  function evaluate(n) {
  
    // if node exists
    if (n) {
    
      // if node is a number; return it
      if (isInteger(n)) {
        return n;
      } else {
      
        //  calculate left and right values recursive
        var left = evaluate(n.left);
        var right = evaluate(n.right);
        var op = n.value;
        
        // return operator performed on the left and right values
        return calculate(left, right, op);
   	  }
    }
  }
  
  // limit user input
function limitInput() {
  var x = document.getElementById("inputx").value;
  var y = document.getElementById("inputy").value;  
  if (x === '') {
    alert("Enter an integer for x");
  }
  if (y === '') {
    alert("Enter an integer for y");
  }
  else if (!isInteger(x) || !isInteger(y)) {
      alert("Enter integers only. You entered: " + x + " for x & " + y + " for y");
    }else {
      var binaryTree = new Node('*', 3, new Node('+', new Node('*', 5, y), x));
      document.getElementById("x").innerHTML = x;
      document.getElementById("y").innerHTML = y;
      document.getElementById("output").innerHTML = evaluate(binaryTree).toString();
      var c =...