SUNY Geneseo Department of Computer Science

Introduction to Trees

Previous Lecture

Questions?

Etiquette for changing others code?

• Make sure original author gets credit
  • (and you do too)
  • History sections
• Correct what needs it

Trees

Sections 13.1 and 13.2

• Tree is like list, but can split into 2 parts at each element
• General structure consists of
  • Root (most important single point)
  • Nodes (junctions of branches)
  • Leaves (ends of branches, subset of nodes)
  • Branches (connect nodes)
• Every tree has exactly 1 root
• Every node has exactly 1 parent
• No node is own descendant
• No 2 nodes have same subset / child
• Height, paths, path-length
  • Level of a node is its height
• Cycles - can't have them

Formal definition of "binary tree"

• Hierarchy
• Tree is a node and two other disjoint trees
• or empty

Common binary tree messages

• Object getRoot()
• boolean isEmpty()
• Tree getLeft()
• Tree getRight()
• insert( Object )
• find( Object )
• delete( Object )

Algorithm to print each element in a binary tree

    // In some subclass of Tree...
    printTree()
        if ! this.isEmpty()
            print this.getRoot()
            this.getLeft().printTree()
            this.getRight.printTree()
        else
            print "empty"

Next

Ordered trees

Read Section 13.3 through 13.3.4

Next Lecture