null
. Other
types of tree structure exist, differing mainly in the amount of data and
number of node pointers maintained by each node.
Trees in computer science are a bit like family trees, in that they are
usually drawn `upside down'. Thus, we will refer to the node at the `top'
of the tree as the root node, and those at the `bottom' (i.e. those
that do not point to any other nodes) as leaf nodes. Any node that
is not a leaf node is by definition and interior node of the tree.
In the diagram above, the node containing the value 19
is the
root node, the nodes 19
and 10
are interior
nodes and the nodes 3
and 42
are the leaves.
Since any tree node be be treated as the root node of a smaller
tree, we can talk about the left and right subtrees of a
node N
; that is, the trees whose root nodes are pointed to by
the left and right hand node pointers of N
.
This notation is reflected by the Java implementation of the tree
structure given below:
1 /** 2 * A simple binary tree class, storing integers 3 */ 4 public class BinaryTree { 5 6 /** The data item in this node */ 7 protected int data; 8 9 /** The left-hand subtree (LHS) */ 10 protected BinaryTree left; 11 12 /** The right-hand subtree (RHS) */ 13 protected BinaryTree right; 14 15 16 /** Create a tree */ 17 public BinaryTree(int data) { 18 this.data = data; 19 left = null; 20 right = null; 21 } 22 23 24 /** Get the data in the root node */ 25 public int data() { 26 return data; 27 } 28 29 /** Get the LHS */ 30 public BinaryTree left() { 31 return left; 32 } 33 34 /** Get the RHS */ 35 public BinaryTree right() { 36 return right; 37 } 38 }Each instance of the class
BinaryTree
forms the root of a
binary tree, with its left and right subtrees pointed to by the instance
variables left
and right
respectively. The code
below shows how you might construct the tree in Figure 1 using the
BinaryTree
class:
1 public class TreeTest { 2 3 public static void main(String args[]) { 4 BinaryTree tree = new BinaryTree(19); 5 tree.left = new BinaryTree(10); 6 tree.right = new BinaryTree(42); 7 tree.left.left = new BinaryTree(3); 8 } 9 }This is all very well, but it doesn't immediately seem to be much use; after all, we could store the same data just as easily in a list or an array. Look more closely at the tree in Figure 1 though, and you will notice that whichever node you choose, the values stored in its left subtree are always less than the value stored in the node itself, while the values in the right subtree are always greater than the node value. Very convenient, but again, what use is it? Consider the problem of searching for a particular data value stored in the tree: if you know nothing about the arrangement of nodes in the tree, you might have to examine every node of the tree before finding the sought value, or concluding that it was not present. This is an O(N) search, similar to searching an unordered list. If however, the tree is arranged according to the scheme described above, we can make the search much more efficient. Say we are looking for the value
3
. We begin by examining
the root node, and noticing that 3 is less than 19. Therefore, if the
value 3 is in the tree anywhere, it must lie within the left
subtree of the root node (recall that all values in the left subtree are
less than the value of their parent). So the search proceeds to the root
of the left subtree, in this case the node containing the value
10
. 3 is less than 10, so again we follow the left hand
pointer, and this time find the node we are looking for. This search
required a total of three comparisons between node values, rather than the
four that might have been needed for a brute-force search. In fact, the
number of comparisons needed for a search of this kind depends
height of the tree rather than the absolute number of nodes, where
the height is the length of the longest path from the root node to a leaf
node, plus one. For larger trees, the difference will be much greater and
the searches consequently much more efficient. Note that you can achieve
the same degree of speedup when searching an ordered list -- your
Introduction to Algorithms notes should have much more to say on this
topic.
BinaryTree
above, with
additional methods for searching and adding new nodes to the tree.
1 /** 2 * A simple binary tree class, storing instances of OrderedObject. 3 */ 4 public class BinaryTree { 5 6 /** The data item in this node */ 7 protected OrderedObject data; 8 9 /** The left-hand subtree (LHS) */ 10 protected BinaryTree left; 11 12 /** The right-hand subtree (RHS) */ 13 protected BinaryTree right; 14 15 16 /** Create a new empty tree */ 17 public BinaryTree() { 18 data = null; 19 left = null; 20 right = null; 21 } 22 23 24 /** Get the data in the root node */ 25 public OrderedObject data() { 26 return data; 27 } 28 29 /** Get the LHS */ 30 public BinaryTree left() { 31 return left; 32 } 33 34 /** Get the RHS */ 35 public BinaryTree right() { 36 return right; 37 } 38 39 40 /** 41 * Insert a new data item into the tree. This will fill an empty (data == 42 * null) node if it finds one, otherwise a new node is created. The data is 43 * always inserted in sorted order, using compareTo(). 44 * Throws a TreeException if a matching object is already present. 45 */ 46 public void insert(OrderedObject newData) throws TreeException, OrderedObjectException { 47 if (data != null) { 48 int a = newData.compareTo(data); 49 if (a < 0) { 50 if (left == null) { 51 left = new BinaryTree(); 52 } 53 left.insert(newData); 54 } 55 else if (a > 0) { 56 if (right == null) { 57 right = new BinaryTree(); 58 } 59 right.insert(newData); 60 } 61 else { 62 throw new TreeException("Object "+newData+" is already in the tree!"); 63 } 64 } 65 else { 66 data = newData; 67 } 68 } 69 70 /** 71 * Find a data item matching target in the tree. Returns a subtree with the 72 * matching item as its root, or null if no match was found. 73 */ 74 public BinaryTree find(OrderedObject target) throws TreeException, OrderedObjectException { 75 if (data != null) { 76 int a = target.compareTo(data); 77 if (a < 0) { 78 return (left == null) ? null : left.find(target); 79 } 80 else if (a > 0) { 81 return (right == null) ? null : right.find(target); 82 } 83 else { 84 return this; 85 } 86 } 87 else { 88 return null; 89 } 90 } 91 92 93 /** Generate a printable representation of the root node of the tree. */ 94 public String toString() { 95 if (data != null) { 96 return data.toString(); 97 } 98 else { 99 return null; 100 } 101 } 102 }Before we examine the algorithms used by the
insert
and
find
methods, let's take a closer look at the data stored by
this class. The tree searching algorithm is based around the idea of one
data item being `greater than' or `less than' another. These concepts are
pretty easy to understand if we are just dealing with integers, but what
if we want the tree to store data of some complex type, such as student
records? How can we determine the ordering of such objects? In Java, and
other object-oriented languages, the usual solution is to have the data
objects implement a method that compares the object with another of the
same type, and returns some indication of which object is `greater'. For
example, the compareTo
methods from the built-in
String
class or the Person
class from Lab
16.
We also want our trees to be generic; this is, we should be able to
construct a tree holding any type of ordered data without changing the
implementation of the binary tree class itself. To achieve both of these
goals using Java, the first step is to define an interface class,
declaring the methods that we want all tree data objects to
implements. Remember that an interface only supplies method headers; the
bodies of the methods must be provided by the class(es) that implement the
interface.
1 /** 2 * Allows a class to define an ordering on its instances. 3 */ 4 public interface OrderedObject { 5 6 /** 7 * Compare the value of this object with the value of other. Returns: 8 * -1 if this object's value is 'less than' other's value 9 * 0 if the two object's values are equal (equals() would return true) 10 * 1 if this object's value is 'greater than' other's value 11 * Throws an OrderedObjectException if the values cannot be compared. 12 */ 13 int compareTo(OrderedObject other) throws OrderedObjectException; 14 }Every class that implements this interface must provide a
compareTo
method with the specified arguments and return
type. In object-oriented terms, every instance if a class that implements
OrderedObject
is-a OrderedObject
and is
therefore suitable as a data object type for the BinaryTree
class. The OrderedString
class below shows a simple example
of this interface in action:
1 /** 2 * Transforms a String into an OrderedObject. 3 */ 4 class OrderedString implements OrderedObject { 5 6 // The actual string data 7 private String str; 8 9 10 /** Create a new OrderedString encapsulating the given String */ 11 public OrderedString(String value) { 12 str = value; 13 } 14 15 16 /** Implement the method from the OrderedObject interface */ 17 public int compareTo(OrderedObject other) throws OrderedObjectException { 18 if (other instanceof OrderedString) { 19 return str.compareTo(((OrderedString)other).str); 20 } 21 else { 22 throw new OrderedObjectException("Illegal comparison"); 23 } 24 } 25 26 27 /** Produce a printable representation of this object */ 28 public String toString() { 29 return str; 30 } 31 }Instances of the
OrderedString
class act as `wrappers' around
ordinary String
objects, and implement the required method
from the OrderedObject
interface. You might think that since
String
already has a suitable compareTo
method
-- line 19 above simply calls this existing method to perform the
comparison -- we would have been better off to just extend the
String
class rather than storing the String
as
an instance variable. Well, you're right, it would have been much more
elegant to do it this way. However, the built in String
class is declared to be a final
class, meaning that it cannot
be extended. An oversight on the part of the Java designers?
While this technique for creating ordered object classes is convenient and
reasonably elegant, it is not without its drawbacks. The
compareTo
method must explicitly check that the
other
argument is in fact an instance of
OrderedString
and not some other type of
OrderedObject
. (Something to think about: why can we not
just declare the method to take an OrderedString
parameter?) Even with this check in place, it is still possible to
construct a tree from a mixture of different OrderedObject
implementations; searches or insertions on such a tree might then
mysteriously fail. To work around this problem, we can extend the
BinaryTree
class itself to accept only
OrderedString
objects:
1 /** 2 * A tree that enforces the use of OrderedStrings. 3 */ 4 public class StringTree extends BinaryTree { 5 6 /** Insert an OrderedString into the tree */ 7 public void insert(OrderedString newData) throws TreeException { 8 try { 9 super.insert(newData); 10 } 11 catch (OrderedObjectException e) { } 12 } 13 14 /** Don't allow a non-OrderedString to be inserted */ 15 public void insert(OrderedObject newData) throws TreeException { 16 throw new TreeException("Attempt to insert a non-OrderedString"); 17 } 18 19 20 /** Look for the given OrderedString */ 21 public BinaryTree find(OrderedString target) throws TreeException { 22 try { 23 return super.find(target); 24 } 25 catch (OrderedObjectException e) { return null; } 26 } 27 28 /** Don't allow searches for non-OrderedStrings */ 29 public BinaryTree find(OrderedObject target) throws TreeException { 30 throw new TreeException("Attempt to search for a non-OrderedString"); 31 } 32 }We will now return to discussing the algorithm for inserting new nodes into the tree. The
insert
method as implemented in lines
46-68 of BinaryTree.java
is recursive. There are two base
cases that cause the recursion to terminate:
data
field is
null
). In this case, the new data is placed in the root
node of the tree. As we shall see later, such an `empty' node will
only occur at a suitable point in the tree.
compareTo
) as the data we are inserting. This
implementation requires that data items be unique, so in this case we
throw a TreeException
and the insertion fails.
newData
, again as determined
by compareTo
. The method then makes a recursive call to
insert
, passing the right or left subtree respectively as the
root of the tree to insert into. If the target subtree does not yet exist
(the subtree reference is null
), a new, empty tree is created
and attached to the current root node. Since such a node will contain no
data, the recursive call will stop at the first base case above and insert
the data at that point.
For example, assume we have just created a new BinaryTree
object, resulting in the structure seen in Figure 2:
BinaryTree tree = new BinaryTree();
19
, wrapped inside
an OrderedInteger
object, into the tree:
tree.insert(new OrderedInteger(19));The
insert
method will immediately find that the root node of
the tree contains no data, and will insert the data value there, giving
the new structure shown in Figure 3:
10
:
tree.insert(new OrderedInteger(10));This time, the root of the tree is occupied, so the method must recursively call
insert
on either its left or right subtree.
The value to be inserted (10
) is less than the value in the
root (19
), so it must be placed in the left subtree.
However, that subtree does not yet exist, so it must be created (Figure
4):
insert
will have the newly
created left hand subtree as its root node. Since the node is empty, the
new value can immediately be inserted (Figure 5):
find
method is structurally very similar to
insert
, using the same recursive algorithm to locate the
required data, if it exists. Of course, both methods could easily be
rewritten in a purely iterative way without any recursive calls (you may
want to try doing this). Also, the same basic algorithms could be used
equally well to perform inserts and searches on an ordered linked list
structure; this case the left and right `subtrees' would be represented by
the left and right halves of the list.
19, 10, 3, 42
3, 10, 42, 19
3, 10, 19, 42The
TreeTest
class given below includes methods to traverse a
tree using each of these orderings.
1 import java.util.Enumeration; 2 3 class TreeTest { 4 5 public static void main(String[] args) { 6 BinaryTree tree = new BinaryTree(); 7 8 try { 9 // Insert A-Z in some random order 10 java.util.Vector v = new java.util.Vector(); 11 for (char c = 'A'; c <= 'Z'; c++) { 12 v.addElement(new Character(c)); 13 } 14 while (v.size() > 0) { 15 int r = (int)Math.round(Math.random() * (v.size()-1)); 16 tree.insert(new OrderedString(v.elementAt(r).toString())); 17 v.removeElementAt(r); 18 } 19 printPreOrder(tree); 20 System.out.println(); 21 } 22 catch (Exception e) { 23 System.out.println(e); 24 } 25 } 26 27 28 public static void printPreOrder(BinaryTree tree) { 29 if (tree.data() != null) { 30 System.out.print(tree.data()+" "); 31 } 32 if (tree.left() != null) { 33 printPreOrder(tree.left()); 34 } 35 if (tree.right() != null) { 36 printPreOrder(tree.right()); 37 } 38 } 39 40 public static void printPostOrder(BinaryTree tree) { 41 if (tree.left() != null) { 42 printPostOrder(tree.left()); 43 } 44 if (tree.right() != null) { 45 printPostOrder(tree.right()); 46 } 47 if (tree.data() != null) { 48 System.out.print(tree.data()+" "); 49 } 50 } 51 52 public static void printInOrder(BinaryTree tree) { 53 if (tree.left() != null) { 54 printInOrder(tree.left()); 55 } 56 if (tree.data() != null) { 57 System.out.print(tree.data()+" "); 58 } 59 if (tree.right() != null) { 60 printInOrder(tree.right()); 61 } 62 } 63 }Why would you choose one traversal method over another? Clearly an in-order traversal is appropriate when you want to retrieve the tree data in sorted order. However, consider the case where the tree contents are to be stored in a file, then later reloaded into a new tree structure. If in-order traversal was used to write the file, the data ends up being pre-sorted when the time comes to load it back in again. Consider for a moment what the tree structure will look like if the data to be inserted is already sorted...essentially the tree degrades into a linked list, neatly eliminating any advantage from using the tree! In this situation, you want the data to be unsorted, so a pre- or post-order traversal would be used when writing the file.
delete
method
to the basic binary tree, illustrating one of the many ways this can be
achieved. The new method makes use of an additional private method which
takes a third parameter. This parent
argument gives the
parent node of the tree
parameter. It is initialised to
null
by the main delete
method, since we have no
way of knowing whether or not the tree has a parent node.
1 /** 2 * An extended binary tree, able to delete nodes as well (Wow!) 3 */ 4 public class DeletingBinaryTree extends IteratingBinaryTree { 5 6 /** Delete a node matching oldData */ 7 public boolean delete(OrderedObject oldData) throws TreeException, OrderedObjectException { 8 return delete(this, null, oldData); 9 } 10 11 // A far-too-complex subroutine to do the real work! 12 private boolean delete(BinaryTree tree, BinaryTree parent, OrderedObject oldData) throws TreeException, OrderedObjectException { 13 if (tree.data != null) { 14 int a = oldData.compareTo(tree.data); 15 if (a < 0) { 16 return (tree.left == null) ? false : delete(tree.left, tree, oldData); 17 } 18 else if (a > 0) { 19 return (tree.right == null) ? false : delete(tree.right, tree, oldData); 20 } 21 else { 22 // found it, now delete it 23 if (tree.left == null && tree.right == null) { 24 // Leaf node 25 if (parent != null) { 26 // If we have a parent we can just snip the node off 27 if (parent.left == tree) { 28 parent.left = null; 29 } 30 else { 31 parent.right = null; 32 } 33 } 34 else { 35 // Otherwise we get left with an empty node 36 tree.data = null; 37 } 38 } 39 else if (tree.left == null) { 40 // Replace the node with its right-hand child 41 tree.data = tree.right.data; 42 tree.left = tree.right.left; 43 tree.right = tree.right.right; 44 } 45 else if (tree.right == null) { 46 // Replace the node with its left-hand child 47 tree.data = tree.left.data; 48 tree.right = tree.left.right; 49 tree.left = tree.left.left; 50 } 51 else { 52 // Find the largest node on the LHS 53 BinaryTree max = tree.left; 54 while (max.right != null) { 55 max = max.right; 56 } 57 // Move LHS up to root, attach old RHS to max 58 max.right = tree.right; 59 tree.data = tree.left.data; 60 tree.right = tree.left.right; 61 tree.left = tree.left.left; 62 } 63 return true; 64 } 65 } 66 else { 67 return false; 68 } 69 } 70 }The private
delete
method uses the familiar recursive
searching technique to locate the node to be deleted. Not that the
parent
parameter is updated each time a new recursive call is
made. Eventually, the target node will be found, or the search will reach
the leaves of the tree and return false
.
Once the node has been found, we must disconnect it from the tree
structure. This operation is handled as four separate cases, based on the
number and location of the node's children.
null
. If the parent is unknown, the
node cannot be disconnected, but we can set its data
member
to null
, turning it into an empty node that may be reused by
a subsequent insert operation. Figure 9 shows the result of deleting the
node containing value 100
from the tree in Figure 6:
10
from the tree in Figure 6:
19
from the tree of Figure 6:
19
). This is not really a problem though, since we are about
to delete the target node. At this point the problem will look exactly
like case 2 above, where the target node has only a left subtree. This,
we simply replace the target with its new left subtree, and the deletion
is complete:
DeletingTree
class contains a
subtle bug. It it worthwhile trying to figure out what this bug is, and
to develop a solution for it. (Hint: consider what could happen after a
'case 1' deletion has left an empty node in the tree, and the empty node's
parent is then deleted).
TreeTest
program is that you do
not need to know anything about the internal structure of the tree, list,
etc that you are traversing -- the iterator object will keep track of all
these details for you.
The iterators used by the IteratingBinaryTree
are based
around the Java Enumeration
interface, which essentially
provides a general framework for building iterator objects. An instance
of Enumeration
must provide two methods:
boolean hasMoreElements()
returns true
iff
there are elements that have yet to be traversed.
Object nextElement()
returns the next object in the
traversal. Note that this object is of class Object
and
must be cast to an appropriate type.
Enumeration
might offer
additional methods, eg. to 'rewind' the traversal back to the first
element. Many Java classes, such as Vector
and
Hashtable
provide methods to obtain an
Enumeration
object over their elements. In general an
Enumeration
will be used in a loop such as:
Enumeration e = someObject.elements(); while (e.hasMoreElements()) { someClass next = (someClass)e.nextElement(); System.out.println(next); }The
IteratingBinaryTree
class contains four inner classes
that implement the iterators for the tree. The most important of these is
the TreeIterator
class. This declares a Vector
object (Java's built-in linked list class) that will hold the elements of
the tree in traversal order, and implements the Enumeration
methods that will return these elements on at a time, in the order they
occur in the vector. It is up to the subclasses of
TreeIterator
to fill in the contents of the vector.
Three subclasses of TreeIterator
are provided, to perform
pre-, post- and in-order traversals of the tree. Each of these performs
the traversal in the usual way and places the tree data into the vector in
the order that the nodes were traversed. Thus, the user will be able to
retrieve the tree data in the same order using the
nextElement()
method of the iterator. The
IteratingBinaryTree
class itself hass three new methods to
create and return the three kinds of iterator. Note that all of these
iterator classes take a copy of the tree contents, so any additions
or deletions made to the tree should not affect any active iterators. Is
this always true? In particular, is there any way that a deletion (using
the algorithm presented above) could affect the contents of a tree
iterator? (Hint: is the data really copied, or just aliased?)
1 import java.util.Enumeration; 2 import java.util.Vector; 3 import java.util.NoSuchElementException; 4 5 6 /** 7 * A simple binary tree class, storing instances of OrderedObject. 8 */ 9 public class IteratingBinaryTree extends BinaryTree{ 10 11 // A basic iterator over a vector of objects 12 private class TreeIterator implements Enumeration { 13 private Vector data; 14 private int current; 15 16 TreeIterator() { 17 data = new Vector(); 18 current = 0; 19 } 20 21 public boolean hasMoreElements() { 22 return (current < data.size()); 23 } 24 25 public Object nextElement() { 26 if (hasMoreElements()) { 27 return data.elementAt(current++); 28 } 29 else { 30 throw new NoSuchElementException(); 31 } 32 } 33 } 34 35 // An iterator containing the tree data in pre-order 36 private class PreOrderIterator extends TreeIterator { 37 38 PreOrderIterator(BinaryTree tree) { 39 init(tree); 40 } 41 42 private void init(BinaryTree tree) { 43 if (tree.data() != null) { 44 this.data.addElement(tree.data()); 45 } 46 if (tree.left() != null) { 47 init(tree.left()); 48 } 49 if (tree.right() != null) { 50 init(tree.right()); 51 } 52 } 53 } 54 55 // An iterator containing the tree data in post-order 56 private class PostOrderIterator extends TreeIterator { 57 58 PostOrderIterator(BinaryTree tree) { 59 init(tree); 60 } 61 62 private void init(BinaryTree tree) { 63 if (tree.left() != null) { 64 init(tree.left()); 65 } 66 if (tree.right() != null) { 67 init(tree.right()); 68 } 69 if (tree.data() != null) { 70 this.data.addElement(tree.data()); 71 } 72 } 73 } 74 75 // An iterator containing the tree data in order 76 private class InOrderIterator extends TreeIterator { 77 78 InOrderIterator(BinaryTree tree) { 79 init(tree); 80 } 81 82 private void init(BinaryTree tree) { 83 if (tree.left() != null) { 84 init(tree.left()); 85 } 86 if (tree.data() != null) { 87 this.data.addElement(tree.data()); 88 } 89 if (tree.right() != null) { 90 init(tree.right()); 91 } 92 } 93 } 94 95 96 /** Return a pre-order iterator for this tree */ 97 public Enumeration iteratePreOrder() { 98 return new PreOrderIterator(this); 99 } 100 101 /** Return a post-order iterator for this tree */ 102 public Enumeration iteratePostOrder() { 103 return new PostOrderIterator(this); 104 } 105 106 /** Return an in-order iterator for this tree */ 107 public Enumeration iterateInOrder() { 108 return new InOrderIterator(this); 109 } 110 }The program
TreeTest2
below is a simple demonstration of the
iterator classes in use. You shoud modify this to experiment with the
pre- and post-order iterators as well.
1 import java.util.Enumeration; 2 3 class TreeTest2 { 4 5 public static void main(String[] args) { 6 IteratingBinaryTree tree = new IteratingBinaryTree(); 7 8 try { 9 // Insert A-Z in some random order 10 java.util.Vector v = new java.util.Vector(); 11 for (char c = 'A'; c <= 'Z'; c++) { 12 v.addElement(new Character(c)); 13 } 14 while (v.size() > 0) { 15 int r = (int)Math.round(Math.random() * (v.size()-1)); 16 tree.insert(new OrderedString(v.elementAt(r).toString())); 17 v.removeElementAt(r); 18 } 19 Enumeration enum = tree.iterateInOrder(); 20 while (enum.hasMoreElements()) { 21 System.out.print(enum.nextElement()+" "); 22 } 23 System.out.println(); 24 } 25 catch (Exception e) { 26 System.out.println(e); 27 } 28 } 29 }
These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.
Last modified: 30 September 1999