SUNY Geneseo Department of Computer Science

Tree Definitions

Return to List of Lectures

Misc

Return exam 2

Questions?

Tree Introduction

Chapter 13 to but not including Section 13.3.2

• Examples of trees
  • Playoff tree
  • Family tree
• Parts of trees
  • Root = most important part, reference for rest
  • Nodes = branches
  • Leaves = furthest nodes from root
• Properties
  • Root has no parent
  • All other nodes have exactly 1 parent
  • No loops (aka cycles)
  • Height = number of levels of nodes in tree
• Uses of trees
  • Decision trees to eliminate possibilities until only correct one is left
• Binary trees: every node has up to 2 children
• Ordered trees
  • How to prove a tree ordered
  • Class invariant: if a is root, then b < a is in tree iff b in left subtree of a, b > a in tree iff b in right subtree

Treating trees recursively

• Define "tree" recursively
  • A tree is...
    • Empty, or
    • Node (root) with children which are trees; root and all children are disjoint
  • Generic recursive tree algorithm

            genericTreeAlgorithm( tree )
                if tree is not empty
                    process root
                    for each child
                        genericTreeAlgorithm( child )
                else
                    do base case and return

• Define "binary tree" recursively
  • A binary tree is...
    • Empty, or
    • Node (root) with 2 children which are binary trees; root and all children are disjoint
• Define "ordered binary tree" (aka "binary search tree") recursively
  • An ordered binary tree is either
    • Empty, or
    • A node with 2 children which are ordered binary trees, all elements in left subtree ≤ element in root and all elements in right subtree > element in root

How could you represent a binary tree in a programming language?

    class BinaryTree<E> {
        private E root;
        private BinaryTree<E> left, right;
        ....
    }

Lab

Hand out Lab 10

Next

Building and searching ordered binary trees

Read Sections 13.3.3 and 13.3.4