CS115 Lecture 8: Week 8 / Module 8: Binary Trees

• School: University of Waterloo
• Department: Computer Science
• Course: CS115
• Professor: Victoria Sakhnini

Document Summary

Understand data de nitions for binary arithmetic expressions and binary search trees. Understand how the templates are derived from the data de nitions, and how to use the templates to write functions that consume those types of data. Understand the de nition of a binary search tree, and how it can be generalized to hold additional data. Be able to write functions that consume binary search trees. Be able to develop and use templates for other binary trees. Baexp: made up of numbers joined by binary operations ( * , + , / , - ) Each expression can be de ned in terms of even smaller expressions. A baexp is either a number or a (baexp op baexp) ((2 * 6) + (20 / 2)) * (5 - 3) can be represented by a tree: Evaluate left to right and do not move onto the next side" until the rst side" is done.