| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Module 10 - Binary Trees

Page history last edited by Dr. Ron Eaglin 7 years, 8 months ago

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.