SUNY Geneseo Department of Computer Science

Introduction to Trees

Previous Lecture

Misc

Hand out Lab 10

Questions?

Timing Fast Operations

e.g., how long does it take to compute the length of a list?

See section 9.3 in text

Developed a Program that does such timing

Inherent +/- 1 count error in discrete time measurements

Introduction to Trees

Reading summary -- Sections 13.1 and 13.2

• Binary trees
• Data structure more complex than lists
• Real world examples
• Names for parts -- come from real trees or genealogy, e.g.
  • Root, Leaf
  • Parent, Child
• Trees in CS
  • File structures
  • Decision trees
  • etc.
• Structure
  • 1 root
  • 1 parent per node
  • Recursive: 2 children with root makes another tree
  • Tree can be empty
  • No cycles
• Proof about heights?
  • Height of tree is greater than height of either subtree

Formal definition of "binary tree"

• Empty
• Or an object and two other (disjoint) trees

Binary tree messages?

• Tree getLeft()
• Tree getRight()
• Object getRoot()
• boolean isEmpty()
• int height()
• addTree( Object )
• remove( Object )

Binary Tree Algorithms

Print all the items in a binary tree

    // In some subclass of BinaryTree
    void print() {
        if this.isEmpty()
            do nothing
        else
            print this.getRoot()
            this.getLeft().print()
            this.getRight().print()

Next

Trees and searching

Read Sections 13.3.1 and 13.3.2

Next Lecture