Computer Science 210

Data Structures

Fall 2018, Siena College

Agenda

- Announcements
- Two ongoing zyBook assignments in Chapter 16: Sections 1 and 2 for today, Sections 3-7 for Tuesday
- Problem Set 5 continues, due Monday afternoon
- Lab 8: Word Frequency Counting with Ordered Structures not due until after the break (but of course you'd like to wrap it up sooner)

- Quiz in class Monday
- short answers about linear structures, both implementation and usage
- there will be a variation of this question: list reasons why it is good to implement and use more restrictive structures

- Introduction to tree structures
- concept and terminology
- a first binary tree implementation

- A general-purpose binary tree
- Tree traversals

Tree Examples

Most trees have branches (except in Tucson):

Around here, our trees branch:

Terminology

- expression 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
- full tree
- complete tree
- perfect tree

Examples