Trees Study Guide

Definitions and Variations

Definitions

tree - collection of nodes that is either empty, or consists of a root node with 0 or more non-empty subtrees connected to the root by a directed edge

node - element of a tree that stores data and has a directed edge connecting it to a parent (unless it is the root node) and one or more children

parent - the node above a given node that is referred to directly

child - the node below a given node that is referred to directly

root - top-level root in tree, only node with no parent

siblings - two nodes that share a parent

internal - a node with one or more children

external/leaf - a node with no children

descendant - a node is a descendant of another node if it is a child of that node or a child of its children

ancestor - a node is an ancestor of another node if it is a parent of that node or its parent

abstract class - clas that is intended to be implemented and lacks implementation details

concrete class - actually implements details of the class

depth of node p - number of ancestors of p, excluding p (depth of root is 0)

Recursive definition of depth: if p is root, 0; otherwise, 1 + depth of parent

height of node - number (max) of nodes to get to a leaf

Recursive definition of height: if p is a leaf, height is 0; otherwise, max( 1 + depth(child)) for child in children

binary tree - ordered tree with left or right children

proper binary tree - each node has 0 or 2 children

full binary tree - same thing as proper

level numbering - utilized for array-based binary tree storage

traversal - way of accessing each node

preorder traversal - traversal in which ROOT node is visited FIRST

postorder traversal - traversal in which CHILDREN nodes are visited FIRST

breadth-first traversal - traversal that visits all nodes of depth d before visiting any nodes of depth d+1

in-order traversal - traversal in which LEFT children are visited, then NODE is visited, then RIGHT children are visited

binary search tree - binary tree in which left node value > this node value > right node value

Euler tour - walks around the entire tree, moving left, visiting each node twice (pre-traversal and post-traversal)

template method pattern - describes a generic computation method that can be specialized for certain steps or parts

ADTs and Interfaces

Tree navigation and node methods:

• root - get root node
• is root(p) - check if this node is root node
• parent(p) - get parent of p
• numChildren(p) - number of children of p
• children(p) - iterator over p's children
• isLeaf(p) - check if node is leaf

Tree construction methods:

• add root
• add left/right/child
• replace
• delete
• attach

Tree utility/general methods:

• size
• empty
• clone
• clear
• equals

Binary tree methods:

• left
• right
• sibling

Implementations

Tree Position/Node class:

• parent
• left/right/container for children
• protected attributes - accessible to parent or exposed via get/set
• get/set for element
• get/set for parent
• get/set for children

Tree class:

• root
• size
• make position (protected)
• validate (protected)

Strategy:

• public methods call private recursive methods
• insert/remove/contains have public/private versions
• traversal methods all private