Computer Science 210

Data Structures

Fall 2017, Siena College

Agenda

- Announcements
- Exam 3 will be during lab meetings, Wednesday, November 29
- same format as first two: a few lab practical tasks then some written questions
- topics covered up to binary trees (our new topic today), with a focus on the last few topics/labs
- expect a practice test out Monday
- hopefully a review session Tuesday, 11/28

- We will go over the Lecture 26 Assignment on Monday
- Lab 7: Iterators and More Lists is now on the late clock, and we will go over some of the more difficult methods on Monday
- Programming Project 4: P.S.: It's Just a Stack due Tuesday afternoon
- Lab 8: A Little Stack Practice - everyone's done or at least very close, due Tuesday in case you're not
- Trees
- motivation
- terminology

- Binary Trees
- constructing a binary tree
- tree traversals

Tree Examples

Most trees have branches (except in Tucson):

Around here, our trees branch:

Due at the start of class, Monday, November 27.

Please submit answers to these questions by the start of class. zyBook activities should be done right in your zyBook. We will discuss these questions at the start of class, so no late submissions can be accepted.

Read and complete all activities in your zyBook in Chapter 16. Sections 8, 9, and 10. This is worth 20 lecture assignment points.

Terminology

- trees
- expression tree
- complete tree
- full tree
- empty tree
- tree node
- root node
- subtree
- edge
- children
- leaves/leaf nodes
- interior nodes
- parent
- forest of trees
- simple path
- path length
- height of a node
- height of the tree
- depth of a node
- degree of a node
- level of a node
- binary tree
- left/right subtrees
- tree traversals
- preorder traversal
- in-order traversal
- postorder traversal
- level-order traversal

Examples