Computer Science 210
Data Structures

Fall 2018, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

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

• BinaryExprTree
• BinaryExpressionTree