Module 10 - Binary Trees
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
3*(x + 5*y)
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/ ). I have created a sample of a Binary Tree that you can use for an example at https://jsfiddle.net/reaglin/9kbk4jb5/
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.
So output should be (if I enter 1,1)
Input X : [ 1 ]
Input Y: [ 1 ]
X = 1, Y=1, Output = 18
Note: The lectures on Binary Trees at All Course Lectures cover this topic in depth.
Quiz
Do 2 quizzes
http://geeksquiz.com/data-structure/binary-trees/
http://geeksquiz.com/data-structure/binary-search-trees/
Previous: Module 9 - Indexes
Next: Module 11 - Graphs
Comments (0)
You don't have permission to comment on this page.