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.
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
}