Assignment 12 – Binary Trees

Objective

Demonstrate the ability to program more complex data structures

Supports learning outcome 1 and 3

1. Describe both complex and simple data structures.
3. Implement data structures and algorithms in computer code.

Introduction

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. Trees are covered in Topic – Tree Data Structures

Assignment

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

x*(3 + 2*y)  
(note this changes every semester)

Hint: there are plenty of javascript code examples of creating a binary tree (http://www.nczonline.net/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/ ).

You will then fill it in and execute by traversing the tree with given values (input by user – you need a GUI to input X and Y), and output a result.

Note: The lectures on Binary Trees at All Course Lectures  cover this topic in depth.

All COP3530 Assignments

Sample Code for Binary Tree

You can use the following code for your assignment. This representation of a tree defines a leaf (no branches from node) and a node (branches from the tree). You can express the equation by defining leaves and nodes. A good example is 1 + 2 where you would define

var leaf1 = new leaf(1); // create a leaf with value of 1
var leaf2 = new leaf(2); // create a leaf with value of 2
var root= new node(“+”, leaf1, leaf2); // the root node will be +
values=[]; // Holds current value
var result = root.traverse(values); //

function leaf(value) {
  this.value = value
}

function node(key, left, right) {
  this.key = key
  this.left = left
  this.right = right
}

leaf.prototype.traverse = function(values) {
  if (isNaN(this.value)) {
    return values[this.value]
  }
  return this.value
}

node.prototype.traverse = function(values) {
  var left = this.left.traverse(values)
  var right = this.right.traverse(values)
  var key = this.key
  if (key == '+') {
    return left + right
  }
  if (key == "-") {
    return left - right
  }
  if (key == '*') {
    return left * right
  }
  if (key == '/') {
    return left / right
  }
  return 0
}