CSE205
Concepts of Computer Science and
Data Structure
Chapter 16- Modified for CSE205- Fall 2008
Outline
•Tree Terminology
•Tree Traversals
•Strategies for Tree Implementations
•Binary Tree Implementation
Tree Terminology
•A tree is a non-linear structure in which elements are
organized into a hierarchy
•Tree is comprised of a set of nodes in which elements are
stored and edges connect one node to another
•Each node is located on a particular level
•There is only one root node in the tree
Tree Terminology
•Nodes at the lower level of a
tree are the children of nodes at
the previous level
•A node can have only one
parent, but may have multiple
children
•Nodes that have the same
parent are siblings
•The root is the only node
which has no parent
Tree Terminology
•A node that has no children is a leaf node
•A note that is not the root and has at least one child is an
internal node
•A subtree is a tree structure that makes up part of another
tree
•We can follow a path through a tree from parent to child,
starting at the root
•A node is an ancestor of another node if it is above it on
the path from the root.
Tree Terminology
•Nodes that can be reached
by following a path from a
particular node are the
descendants of that node
•The level of a node is the
length of the path from the
root to the node
A
B C
E
D
FG
Level
0
1
3
2
Tree Terminology
•The path length is determined by counting the number of
edges that must be followed to get from the root to the
node
•The height (or depth) of a tree is the length of the longest
path from the root to a leaf
Tree Classifications
•Trees can be classified in many ways
•One important criteria is the maximum number of
children any node in the tree may have
•This is sometimes referred to as the order of the tree
•General trees have no limit to the number of children a
node may have
•A tree that limits each node to no more than n children is
referred to as an n-ary tree
Tree Classifications
•Trees in which nodes may
have at most two children
are called binary trees
•A tree is considered to be
balanced if all of the
leaves of the tree are on
the same level or at least
within one level of each
other
Tree Classifications
•A balanced n-ary tree with m elements will have a height
of lognm
•A balanced binary tree with n nodes has a height of log2n
•An n-ary tree is full if all leaves of the tree are at the same
height and every non-leaf node has exactly n children
•A tree is complete if it is full, or full to the next-to-last
level with all leaves at the bottom level on the left side of
the tree
LJ
Some Complete Trees
Outline
•Tree Terminology
•Tree Traversals
•Strategies for Tree Implementations
•Binary Tree Implementation
Tree Traversals
•Because of the non-linear nature of a tree, traversing a
tree is generally more interesting than traversing a linear
structure
•The concept of “visiting” a node is somewhat vague and
left to the developer for the exact meaning
•A particular type of traversal simply dictates the order in
which the elements of a collection are assessed
Tree Traversals
•There are four basic ways to traverse a tree, all starting at
the root node
–Preorder: visit the root, then traverse the subtrees from left to
right
–Inorder: traverse the left subtree, then visit the root, then
traverse the right subtree
–Postorder: traverse the subtrees from left to right, then visit the
root
–Level-order: visit each node at each level of the tree from top
(root) to bottom and left to right
Traversal
Preorder
ABDHIEJMNCGPFGKL
Inorder;
HOIBEMJNAPCKGL
Postorder;
HIDMNJEBFRKLGCA
Levelorder
ABCDEFGHIJKLMN
Tree Traversals
Preorder Traversal
•Nodes are visited before any subtrees are visited
–Pseudo code:
Visit Node
Traverse (left-subtree)
Traverse (right-subtree)
Inorder Traversal
•Visit the root node in between the traversals of the left
and right subtrees
–Pseudo code:
Traverse (left-subtree)
Visit Node
Traverse (right-subtree)
Postorder Traversal
•Visit the root node after the traversals of the left and right
subtrees
–Pseudo code:
Traverse (left-subtree)
Traverse (right-subtree)
Visit Node
Level-Order Traversal
•Visit the nodes on each level, left to right, top to bottom
starting at the root
–Pseudo code:
Enqueue the root node of the
tree
While the queue is not empty
{
Dequeue node
Visit node
Enqueue left child of node
Enqueue right child of node
}
Outline
•Tree Terminology
•Tree Traversals
•Strategies for Tree Implementations
•Binary Tree Implementation
Strategies for Implementing Trees
•Array-based implementations are the less obvious choice,
but sometimes useful
•A more obvious choice is a linked structure
implementation
•We will discuss a linked approach
Linked Nodes
•Each tree node can be defined using a separate class –
similar to LinearNode or linked lists
•Nodes contain a reference to the data stored in the node,
and references for each of the possible children of the
node
–Binary tree: two references required – left and right children
–n-ary tree: n references required – one for each possible child
•Trees organized this way lend themselves to recursive
processing for many operations
Linked Nodes
•Each node can be thought of as the root of a subtree.
Outline
•Tree Terminology
•Tree Traversals
•Strategies for Tree Implementations
•Binary Tree Implementation
A Binary Tree Implementation
•A possible set of operations for a binary tree is shown in
the BinaryTree interface
•Note that BinaryTree has no methods to add a particular
element, or to remove a particular element from the tree
•Refined versions of binary tree (such as binary search
trees) will define those methods based on specific
characteristics
•BinaryTree is still useful in certain situations
Linked Binary Tree Implementation
Strategy
javafoundations.BinaryTree
//*******************************************************************
// BinaryTree.java Java Foundations
//
// Defines the interface to a binary tree collection.
//*******************************************************************
package javafoundations;
import java.util.Iterator;
public interface BinaryTree<T> extends Iterable<T>
{
// Returns the element stored in the root of the tree.
public T getRootElement();
// Returns the left subtree of the root.
public BinaryTree<T> getLeft();
// Returns the right subtree of the root.
public BinaryTree<T> getRight();
// Returns true if the binary tree contains an element that
// matches the specified element and false otherwise.
public boolean contains (T target);
(more…)
javafoundations.BinaryTree
// Returns a reference to the element in the tree matching
// the specified target.
public T find (T target);
// Returns true if the binary tree contains no elements, and
// false otherwise.
public boolean isEmpty();
// Returns the number of elements in this binary tree.
public int size();
// Returns the string representation of the binary tree.
public String toString();
// Returns a preorder traversal on the binary tree.
public Iterator<T> preorder();
// Returns an inorder traversal on the binary tree.
public Iterator<T> inorder();
// Returns a postorder traversal on the binary tree.
public Iterator<T> postorder();
// Performs a level-order traversal on the binary tree.
public Iterator<T> levelorder();
}
javafoundations.LinkedBinaryTree
//*******************************************************************
// LinkedBinaryTree.java Java Foundations
//
// Implements a binary tree using a linked representation.
//*******************************************************************
package javafoundations;
import java.util.Iterator;
import javafoundations.*;
import javafoundations.exceptions.*;
public class LinkedBinaryTree<T> implements BinaryTree<T>
{
protected BTNode<T> root;
//-----------------------------------------------------------------
// Creates an empty binary tree.
//-----------------------------------------------------------------
public LinkedBinaryTree()
{
root = null;
}
(more…)
javafoundations.LinkedBinaryTree
//-----------------------------------------------------------------
// Creates a binary tree with the specified element as its root.
//-----------------------------------------------------------------
public LinkedBinaryTree (T element)
{
root = new BTNode<T>(element);
}
//-----------------------------------------------------------------
// Creates a binary tree with the two specified subtrees.
//-----------------------------------------------------------------
public LinkedBinaryTree (T element, LinkedBinaryTree<T> left,
LinkedBinaryTree<T> right)
{
root = new BTNode<T>(element);
root.setLeft(left.root);
root.setRight(right.root);
}
//-----------------------------------------------------------------
// Returns the element stored in the root of the tree. Throws an
// EmptyCollectionException if the tree is empty.
//-----------------------------------------------------------------
public T getRootElement()
{
if (root == null)
throw new EmptyCollectionException ("Get root operation "
+ "failed. The tree is empty.");
return root.getElement();
}
(more…)
javafoundations.LinkedBinaryTree
//-----------------------------------------------------------------
// Returns the left subtree of the root of this tree.
//-----------------------------------------------------------------
public LinkedBinaryTree<T> getLeft()
{
if (root == null)
throw new EmptyCollectionException ("Get left operation "
+ "failed. The tree is empty.");
LinkedBinaryTree<T> result = new LinkedBinaryTree<T>();
result.root = root.getLeft();
return result;
}
//-----------------------------------------------------------------
// Returns the element in this binary tree that matches the
// specified target. Throws a ElementNotFoundException if the
// target is not found.
//-----------------------------------------------------------------
public T find (T target)
{
BTNode<T> node = null;
if (root != null)
node = root.find(target);
if (node == null)
throw new ElementNotFoundException("Find operation failed. "
+ "No such element in tree.");
return node.getElement();
}
(more…)
javafoundations.LinkedBinaryTree
//-----------------------------------------------------------------
// Returns the number of elements in this binary tree.
//-----------------------------------------------------------------
public int size()
{
int result = 0;
if (root != null)
result = root.count();
return result;
}
//-----------------------------------------------------------------
// Populates and returns an iterator containing the elements in
// this binary tree using an inorder traversal.
//-----------------------------------------------------------------
public Iterator<T> inorder()
{
ArrayIterator<T> iter = new ArrayIterator<T>();
if (root != null)
root.inorder (iter);
return iter;
}
(more…)
javafoundations.LinkedBinaryTree
//-----------------------------------------------------------------
// Populates and returns an iterator containing the elements in
// this binary tree using a levelorder traversal.
//-----------------------------------------------------------------
public Iterator<T> levelorder()
{
LinkedQueue<BTNode<T>> queue = new LinkedQueue<BTNode<T>>();
ArrayIterator<T> iter = new ArrayIterator<T>();
if (root != null)
{
queue.enqueue(root);
while (!queue.isEmpty())
{
BTNode<T> current = queue.dequeue();
iter.add (current.getElement());
if (current.getLeft() != null)
queue.enqueue(current.getLeft());
if (current.getRight() != null)
queue.enqueue(current.getRight());
}
}
return iter;
}
(more…)
javafoundations.LinkedBinaryTree
//-----------------------------------------------------------------
// Satisfies the Iterable interface using an inorder traversal.
//-----------------------------------------------------------------
public Iterator<T> iterator()
{
return inorder();
}
//-----------------------------------------------------------------
// The following methods are left as programming projects.
//-----------------------------------------------------------------
// public LinkedBinaryTree<T> getRight() { }
// public boolean contains (T target) { }
// public boolean isEmpty() { }
// public String toString() { }
// public Iterator<T> preorder() { }
// public Iterator<T> postorder() { }
}
javafoundations.BTNode
//*******************************************************************
// BTNode.java Java Foundations
//
// Represents a node in a binary tree with a left and right child.
// Therefore this class also represents the root of a subtree.
//*******************************************************************
package javafoundations;
public class BTNode<T>
{
protected T element;
protected BTNode<T> left, right;
//-----------------------------------------------------------------
// Creates a new tree node with the specified data.
//-----------------------------------------------------------------
public BTNode (T element)
{
this.element = element;
left = right = null;
}
(more…)
javafoundations.BTNode
//-----------------------------------------------------------------
// Returns the element stored in this node.
//-----------------------------------------------------------------
public T getElement()
{
return element;
}
//-----------------------------------------------------------------
// Sets the element stored in this node.
//-----------------------------------------------------------------
public void setElement (T element)
{
this.element = element;
}
//-----------------------------------------------------------------
// Returns the left subtree of this node.
//-----------------------------------------------------------------
public BTNode<T> getLeft()
{
return left;
}
(more…)
javafoundations.BTNode
//-----------------------------------------------------------------
// Sets the left child of this node.
//-----------------------------------------------------------------
public void setLeft (BTNode<T> left)
{
this.left = left;
}
//-----------------------------------------------------------------
// Returns the right subtree of this node.
//-----------------------------------------------------------------
public BTNode<T> getRight()
{
return right;
}
//-----------------------------------------------------------------
// Sets the right child of this node.
//-----------------------------------------------------------------
public void setRight (BTNode<T> right)
{
this.right = right;
}
(more…)
javafoundations.BTNode
//-----------------------------------------------------------------
// Returns the element in this subtree that matches the
// specified target. Returns null if the target is not found.
//-----------------------------------------------------------------
public BTNode<T> find (T target)
{
BTNode<T> result = null;
if (element.equals(target))
result = this;
else
{
if (left != null)
result = left.find(target);
if (result == null && right != null)
result = right.find(target);
}
return result;
}
(more…)
javafoundations.BTNode
//-----------------------------------------------------------------
// Returns the number of nodes in this subtree.
//-----------------------------------------------------------------
public int count()
{
int result = 1;
if (left != null)
result += left.count();
if (right != null)
result += right.count();
return result;
}
(more…)
javafoundations.BTNode
//-----------------------------------------------------------------
// Performs an inorder traversal on this subtree, updating the
// specified iterator.
//-----------------------------------------------------------------
public void inorder (ArrayIterator<T> iter)
{
if (left != null)
left.inorder (iter);
iter.add (element);
if (right != null)
right.inorder (iter);
}
//-----------------------------------------------------------------
// The following methods are left as programming projects.
//-----------------------------------------------------------------
// public void preorder (ArrayIterator<T> iter) { }
// public void postorder (ArrayIterator<T> iter) { }
}
