SUNY Geneseo Department of Computer Science

Introduction to Trees

Previous Lecture

Questions?

insertValue turns empty tree into non-empty

    Tree t1 = new Tree()
    t1.addItem(...)
    ....
    Tree t2 = t1.left()
    t1.insertValue( x )

Stack Wrap-Up

One example of why stacks are so important

Recursion, e.g.,

    printParens( int n ) 
        if n > 0
            print "("
            printParens( n-1 )
            print ")"

Trace some invocations in "printParens(3)"

• printParens(3) = printParens, n=3
  • calls printParens, n=2
  • calls printParens, n=1

LIFO is exactly how methods call and return

Introduction to Trees

Read sections 13.1, 13.2, 13.4

("Unary tree" = list)

Examples of trees in real life

• Sports tournament
• Family tree
• Corporate organization
• Outlines (don't look like the others, but have paths, etc)

Parts of trees

• Root
• Branches
• Nodes
• Twig
• Leaf

Properties

• Only one root
• No cycles
  • "Graph"

• Only one parent for each node

Trees in CS

• File structures: directories/folders
• Decision trees ???
  • Kind of a searching structure for many lists?
  • Like taxonomic trees
  • Like interactive stories with questions that lead you to different endings
    • (These could be general graphs)
  • Way of modelling complex conditionals
  • Nested yes-no decision structures
  • Like 20 questions

            if answer1 = "yes"
                ask question 2
                if answer2 = "yes"
                    ask question 3
                    ....
                else
                    ask question 3a
                    if answer 3a = yes
                        ....

        askQuestions()
            print this.question
            read answer
            if answer = yes
                this.left().askQuestions()
            else
                this.right().askQuestions()

If-then-else as trees?

• Yes
• Control structure in all forms is a tree

    main() {
        x = 1
        for ( i= 1; i < 10 ; i++ ) {
            z = 17
            if i < 5
                y = 3
                x = x +1
            else
                print "hello"
            q = 9
        }  
    }

Trees as data structures

Trees are recursively defined

• Tree is object + two smaller trees
• or empty

Ordered tree class

• Messages
  • addNode
  • insertValue
• What is "Comparable"
  • Analogous to Object
  • Comparable = superclass (not quite true, "interface" really) of all objects that have <
  • x.compareTo(y)
    • returns <0 if x < y
    • returns 0 if x = y
    • returns >0 if x > y

Some Tree Algorithms

Mini-Assignment:

Count the nodes in a tree

    // In a subclass of OrderedTree
    int countNodes()
        ...

Next Lecture