Computer Science 210
Data Structures
Fall 2020, Siena College
Lecture 21: Introduction to Tree Structures
Date: Tuesday, October 13, 2020
Agenda
- Announcements
- Problem Set 3: wrap it up tonight
- zyBook assignment 6 due Sunday
- Lab 6 due next week
- Don't forget to do the group work problems as well
- Watch for Problem Set 4, should be out tomorrow
- Some thoughts on finishing up Lab 6
- Introduction to tree structures
- concept and terminology
- a first binary tree implementation: expression trees
- 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