Computer Science 210
Data Structures
Fall 2019, Siena College
Lecture 21: Trees
Date: Friday, October 25, 2019
Agenda
- Announcements
- Most recent zyBook Assignment was due last night, the next is due Halloween night
- Lab 6 due at the start of your labs next week
- Problem Set 4 groups should be formed and repositories created: slow and steady progress with frequent commits and pushes is the way to go
- Introduction to tree structures
- concept and terminology
- a first binary tree implementation
- A general-purpose binary tree
- Tree traversals
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