Computer Science 210
Data Structures
Fall 2017, Siena College
Lecture 28: Binary Trees
Date: Friday, November 17, 2017
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
- Binary Trees
- constructing a binary tree
- tree traversals
Tree Examples
Most trees have branches (except in Tucson):
Around here, our trees branch:
Lecture 28 Assignment
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
