1

17

Data Structures

© 1992-2007 Pearson Education, Inc. All rights reserved.

 2

Much that I bound, I could not free;

Much that I freed returned to me.
— Lee Wilson Dodd

‘Will you walk a little faster?’ said a whiting to a snail,

‘There’s a porpoise close behind us, and he’s treading on my
tail.’
— Lewis Carroll

There is always room at the top.

— Daniel Webster

Push on—keep moving.

— Thomas Morton

I’ll turn over a new leaf.

— Miguel de Cervantes

© 1992-2007 Pearson Education, Inc. All rights reserved.

 3

OBJECTIVES
In this chapter you will learn:
▪ To form linked data structures using references, self-
referential classes and recursion.
▪ The type-wrapper classes that enable programs to
process primitive data values as objects.
▪ To use autoboxing to convert a primitive value to an
object of the corresponding type-wrapper class.
▪ To use auto-unboxing to convert an object of a type-
wrapper class to a primitive value.
▪ To create and manipulate dynamic data structures,
such as linked lists, queues, stacks and binary trees.
▪ Various important applications of linked data structures.
▪ How to create reusable data structures with classes,
inheritance and composition.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 4

17.1 Introduction
17.2 Type-Wrapper Classes for Primitive Types
17.3 Autoboxing and Auto-Unboxing
17.4 Self-Referential Classes
17.5 Dynamic Memory Allocation
17.6 Linked Lists
17.7 Stacks
17.8 Queues
17.9 Trees
17.10 Wrap-Up

© 1992-2007 Pearson Education, Inc. All rights reserved.

 5

17.1 Introduction

• Dynamic data structures

– Linear data structures
• Linked lists
• Stacks
• Queues
– Binary trees

© 1992-2007 Pearson Education, Inc. All rights reserved.

 6

17.2 Type-Wrapper Classes for Primitive

Types
• Type-wrapper classes
– In package java.lang
– Enable programmers to manipulate primitive-type values
as objects
– Boolean, Byte, Character, Double, Float,
Integer, Long and Short

© 1992-2007 Pearson Education, Inc. All rights reserved.

 7

17.3 Autoboxing and Auto-Unboxing

• Boxing conversion
– Converts a value of a primitive type to an object of the
corresponding type-wrapper class
• Unboxing conversion
– Converts an object of a type-wrapper class to a value of the
corresponding primitive type
• Java automatically performs these conversions
(starting with Java SE 5)
– Called autoboxing and auto-unboxing

© 1992-2007 Pearson Education, Inc. All rights reserved.

 8

17.4 Self-Referential Classes

• Self-referential class
– Contains an instance variable that refers to another object
of the same class type
• That instance variable is called a link
– A null reference indicates that the link does not refer to
another object
• Illustrated by a backslash in diagrams

© 1992-2007 Pearson Education, Inc. All rights reserved.

 9

Fig. 17.1 | Self-referential-class objects linked together.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 10

17.5 Dynamic Memory Allocation

• Dynamic memory allocation

– The ability for a program to obtain more memory space at
execution time to hold new nodes and to release space no
longer needed
• Java performs automatic garbage collection of objects that
are no longer referenced in a program
– Node nodeToAdd = new Node( 10 );
• Allocates the memory to store a Node object and returns a
reference to the object, which is assigned to nodeToAdd
• Throws an OutOfMemoryError if insufficient memory is
available

© 1992-2007 Pearson Education, Inc. All rights reserved.

 11

17.6 Linked Lists

• Linked list
– Linear collection of nodes
• Self-referential-class objects connected by reference links
• Can contain data of any type
– A program typically accesses a linked list via a reference to
the first node in the list
• A program accesses each subsequent node via the link
reference stored in the previous node
– Are dynamic
• The length of a list can increase or decrease as necessary
• Become full only when the system has insufficient memory to
satisfy dynamic storage allocation requests

© 1992-2007 Pearson Education, Inc. All rights reserved.

 12

Performance Tip 17.1

An array can be declared to contain more

elements than the number of items expected,
but this wastes memory. Linked lists provide
better memory utilization in these situations.
Linked lists allow the program to adapt to
storage needs at runtime.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 13

Performance Tip 17.2

Insertion into a linked list is fast—only two

references have to be modified (after locating
the insertion point). All existing node objects
remain at their current locations in memory.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 14

Performance Tip 17.3

Insertion and deletion in a sorted array can be

time consuming—all the elements following
the inserted or deleted element must be
shifted appropriately.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 15

17.6 Linked Lists (Cont.)

• Singly linked list

– Each node contains one reference to the next node in the
list
• Doubly linked list
– Each node contains a reference to the next node in the list
and a reference to the previous node in the list
– java.util’s LinkedList class is a doubly linked list
implementation

© 1992-2007 Pearson Education, Inc. All rights reserved.

 16

Performance Tip 17.4

Normally, the elements of an array are

contiguous in memory. This allows immediate
access to any array element, because its
address can be calculated directly as its offset
from the beginning of the array. Linked lists
do not afford such immediate access to their
elements—an element can be accessed only by
traversing the list from the front (or from the
back in a doubly linked list).

© 1992-2007 Pearson Education, Inc. All rights reserved.

 17

Fig. 17.2 | Linked list graphical representation.

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.3: List.java 18
2 // ListNode and List class definitions.
3 package com.deitel.jhtp6.ch17;
4
5 // class to represent one node in a list
6 class ListNode
7 {
8 // package access members; List can access these directly
9 Object data;
Field data can refer to any object
10 ListNode nextNode;
11
12 // constructor creates a ListNode that refers to object
Stores a reference to the next
13 ListNode( Object object ) ListNode object in the linked list
14 {
15 this( object, null );
16 } // end ListNode one-argument constructor
17
18 // constructor creates ListNode that refers to
19 // Object and to next ListNode
20 ListNode( Object object, ListNode node )
21 {
22 data = object;
23 nextNode = node;
24 } // end ListNode two-argument constructor
25

© 1992-2007 Pearson Education, Inc. All rights reserved.

26 // return reference to data in node 19
27 Object getObject()
28 {
29 return data; // return Object in this node
30 } // end method getObject
31
32 // return reference to next node in list
33 ListNode getNext()
34 {
35 return nextNode; // get next node
36 } // end method getNext
37 } // end class ListNode
38
References to the first and last
39 // class List definition
ListNodes in a List
40 public class List
41 {
42 private ListNode firstNode;
43 private ListNode lastNode;
44 private String name; // string like "list" used in printing
45
46 // constructor creates empty List with "list" as the name
47 public List()
48 {
49 this( "list" ); Call one-argument constructor
50 } // end List no-argument constructor
51

© 1992-2007 Pearson Education, Inc. All rights reserved.

52 // constructor creates an empty List with a name 20
53 public List( String listName )
54 { Initialize both references to null
55 name = listName;
56 firstNode = lastNode = null;
57 } // end List one-argument constructor
58
59 // insert Object at front of List
60 public void insertAtFront( Object insertItem )
61 {
62 if ( isEmpty() ) // firstNode and lastNode refer to same object
63 firstNode = lastNode = new ListNode( insertItem );
64 else // firstNode refers to new node
65 firstNode = new ListNode( insertItem, firstNode );
66 } // end method insertAtFront
67
68 // insert Object at end of List
69 public void insertAtBack( Object insertItem )
70 {
71 if ( isEmpty() ) // firstNode and lastNode refer to same Object
72 firstNode = lastNode = new ListNode( insertItem );
73 else // lastNode's nextNode refers to new node
74 lastNode = lastNode.nextNode = new ListNode( insertItem );
75 } // end method insertAtBack
76

© 1992-2007 Pearson Education, Inc. All rights reserved.

77 // remove first node from List 21
78 public Object removeFromFront() throws EmptyListException
79 {
80 if ( isEmpty() ) // throw exception if List is empty
81 throw new EmptyListException( name );
82
83 Object removedItem = firstNode.data; // retrieve data being removed
84
85 // update references firstNode and lastNode
86 if ( firstNode == lastNode )
87 firstNode = lastNode = null;
88 else
89 firstNode = firstNode.nextNode;
90
91 return removedItem; // return removed node data
92 } // end method removeFromFront
93
94 // remove last node from List
95 public Object removeFromBack() throws EmptyListException
96 {
97 if ( isEmpty() ) // throw exception if List is empty
98 throw new EmptyListException( name );
99
100 Object removedItem = lastNode.data; // retrieve data being removed
101

© 1992-2007 Pearson Education, Inc. All rights reserved.

102 // update references firstNode and lastNode 22
103 if ( firstNode == lastNode )
104 firstNode = lastNode = null;
105 else // locate new last node
106 {
107 ListNode current = firstNode;
108
109 // loop while current node does not refer to lastNode
110 while ( current.nextNode != lastNode )
111 current = current.nextNode;
112
113 lastNode = current; // current is new lastNode
114 current.nextNode = null;
115 } // end else
116
117 return removedItem; // return removed node data
118 } // end method removeFromBack
119
Predicate method that determines
120 // determine whether list is empty
121 public boolean isEmpty()
whether the list is empty
122 {
123 return firstNode == null; // return true if List is empty
124 } // end method isEmpty
125

© 1992-2007 Pearson Education, Inc. All rights reserved.

126 // output List contents 23
127 public void print()
128 { Display the list’s contents
129 if ( isEmpty() )
130 {
131 System.out.printf( "Empty %s\n", name );
132 return;
133 } // end if
134 Display a message indicating
135 System.out.printf( "The %s is: ", name ); that the list is empty
136 ListNode current = firstNode;
137
138 // while not at end of list, output current node's data
139 while ( current != null ) Output a string representation
140 { of current.data
141 System.out.printf( "%s ", current.data );
142 current = current.nextNode;
143 } // end while
144
145 System.out.println( "\n" );
146 } // end method print Move to the next node in the list
147 } // end class List

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.4: EmptyListException.java 24
2 // Class EmptyListException definition.
3 package com.deitel.jhtp6.ch17;
4
5 public class EmptyListException extends RuntimeException
6 {
7 // no-argument constructor
8 public EmptyListException()
9 {
10 this( "List" ); // call other EmptyListException constructor
11 } // end EmptyListException no-argument constructor
12
13 // one-argument constructor
14 public EmptyListException( String name )
15 {
16 super( name + " is empty" ); // call superclass constructor
17 } // end EmptyListException one-argument constructor
18 } // end class EmptyListException

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.5: ListTest.java 25
2 // ListTest class to demonstrate List capabilities.
3 import com.deitel.jhtp6.ch17.List;
4 import com.deitel.jhtp6.ch17.EmptyListException;
5
6 public class ListTest
7 {
8 public static void main( String args[] )
9 {
10 List list = new List(); // create the List container
11
12 // insert integers in list
13 list.insertAtFront( -1 ); Insert objects at the beginning of the list
14 list.print(); using method insertAtFront
15 list.insertAtFront( 0 );
16 list.print();
17 list.insertAtBack( 1 );
18 list.print(); Insert objects at the end of the list
19 list.insertAtBack( 5 ); using method insertAtBack
20 list.print();
21

JVM autoboxes each literal

value in an Integer object

© 1992-2007 Pearson Education, Inc. All rights reserved.

22 // remove objects from list; print after each removal 26
23 try
24 {
25 Object removedObject = list.removeFromFront(); Deletes objects from the front of the list
26 System.out.printf( "%s removed\n", removedObject ); using method removeFromFront
27 list.print();
28
29 removedObject = list.removeFromFront();
30 System.out.printf( "%s removed\n", removedObject );
31 list.print();
32
33 removedObject = list.removeFromBack(); Delete objects from the end of the list
34 System.out.printf( "%s removed\n", removedObject ); using method removeFromBack
35 list.print();
36
Call List method print to
37 removedObject = list.removeFromBack();
38 System.out.printf( "%s removed\n", removedObject ); display the current list contents
39 list.print();
40 } // end try
41 catch ( EmptyListException emptyListException )
42 {
43 emptyListException.printStackTrace();
Exception handler for EmptyListException
44 } // end catch
45 } // end main
46 } // end class ListTest

© 1992-2007 Pearson Education, Inc. All rights reserved.

 27
The list is: -1

The list is: 0 -1

The list is: 0 -1 1

The list is: 0 -1 1 5

0 removed
The list is: -1 1 5

-1 removed
The list is: 1 5

5 removed
The list is: 1

1 removed
Empty list

© 1992-2007 Pearson Education, Inc. All rights reserved.

 28

17.6 Linked Lists (Cont.)

• Method insertAtFront’s steps
– Call isEmpty to determine whether the list is empty
– If the list is empty, assign firstNode and lastNode to
the new ListNode that was initialized with insertItem
• The ListNode constructor call sets data to refer to the
insertItem passed as an argument and sets reference
nextNode to null
– If the list is not empty, set firstNode to a new
ListNode object and initialize that object with
insertItem and firstNode
• The ListNode constructor call sets data to refer to the
insertItem passed as an argument and sets reference
nextNode to the ListNode passed as argument, which
previously was the first node
© 1992-2007 Pearson Education, Inc. All rights reserved.
 29

Fig. 17.6 | Graphical representation of operation insertAtFront.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 30

17.6 Linked Lists (Cont.)

• Method insertAtBack’s steps
– Call isEmpty to determine whether the list is empty
– If the list is empty, assign firstNode and lastNode to
the new ListNode that was initialized with insertItem
• The ListNode constructor call sets data to refer to the
insertItem passed as an argument and sets reference
nextNode to null
– If the list is not empty, assign to lastNode and
lastNode.nextNode the reference to the new
ListNode that was initialized with insertItem
• The ListNode constructor sets data to refer to the
insertItem passed as an argument and sets reference
nextNode to null

© 1992-2007 Pearson Education, Inc. All rights reserved.

 31

Fig. 17.7 | Graphical representation of operation insertAtBack.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 32

17.6 Linked Lists (Cont.)

• Method removeFromFront’s steps
– Throw an EmptyListException if the list is empty
– Assign firstNode.data to reference removedItem
– If firstNode and lastNode refer to the same object, set
firstNode and lastNode to null
– If the list has more than one node, assign the value of
firstNode.nextNode to firstNode
– Return the removedItem reference

© 1992-2007 Pearson Education, Inc. All rights reserved.

 33

Fig. 17.8 | Graphical representation of operation removeFromFront.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 34

17.6 Linked Lists (Cont.)

• Method removeFromBack’s steps
– Throws an EmptyListException if the list is empty
– Assign lastNode.data to removedItem
– If the firstNode and lastNode refer to the same
object, set firstNode and lastNode to null
– If the list has more than one node, create the ListNode
reference current and assign it firstNode
– “Walk the list” with current until it references the node
before the last node
• The while loop assigns current.nextNode to current
as long as current.nextNode is not lastNode

© 1992-2007 Pearson Education, Inc. All rights reserved.

 35

17.6 Linked Lists (Cont.)

– Assign current to lastNode
– Set current.nextNode to null
– Return the removedItem reference

© 1992-2007 Pearson Education, Inc. All rights reserved.

 36

Fig. 17.9 | Graphical representation of operation removeFromBack.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 37

17.7 Stacks

• Stacks
– Last-in, first-out (LIFO) data structure
• Method push adds a new node to the top of the stack
• Method pop removes a node from the top of the stack and
returns the data from the popped node
– Program execution stack
• Holds the return addresses of calling methods
• Also contains the local variables for called methods
– Used by the compiler to evaluate arithmetic expressions

© 1992-2007 Pearson Education, Inc. All rights reserved.

 38

17.7 Stacks (Cont.)

• Stack class that inherits from List
– Stack methods push, pop, isEmpty and print are
performed by inherited methods insertAtFront,
removeFromFront, isEmpty and print
• push calls insertAtFront
• pop calls removeFromFront
• isEmpty and print can be called as inherited
– Other List methods are also inherited
• Including methods that should not be in the stack class’s
public interface

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.10: StackInheritance.java 39
2 // Derived from class List.
3 package com.deitel.jhtp6.ch17;
4
Class StackInheritance
5 public class StackInheritance extends List extends class List
6 {
7 // no-argument constructor
8 public StackInheritance()
9 {
10 super( "stack" );
11 } // end StackInheritance no-argument constructor
12
13 // add object to stack
14 public void push( Object object ) Method push calls inherited
15 { method insertAtFront
16 insertAtFront( object );
17 } // end method push
18
19 // remove object from stack
20 public Object pop() throws EmptyListException
21 {
22 return removeFromFront(); Method pop calls inherited method
23 } // end method pop removeFromFront
24 } // end class StackInheritance

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.11: StackInheritanceTest.java 40
2 // Class StackInheritanceTest.
3 import com.deitel.jhtp6.ch17.StackInheritance;
4 import com.deitel.jhtp6.ch17.EmptyListException;
5
6 public class StackInheritanceTest
7 {
8 public static void main( String args[] )
9 {
10 StackInheritance stack = new StackInheritance();
11
12 // use push method Create a StackInheritenace object
13 stack.push( -1 );
14 stack.print();
15 stack.push( 0 );
16 stack.print();
17 stack.push( 1 );
18 stack.print();
19 stack.push( 5 ); Push integers onto the stack
20 stack.print();
21

© 1992-2007 Pearson Education, Inc. All rights reserved.

22 // remove items from stack 41
23 try
24 {
25 Object removedObject = null; Pop the objects from the stack
26 in an infinite while loop
27 while ( true )
28 {
29 removedObject = stack.pop(); // use pop method
30 System.out.printf( "%s popped\n", removedObject );
31 stack.print();
32 } // end while
33 } // end try Implicitly call inherited
34 catch ( EmptyListException emptyListException ) method print
35 {
36 emptyListException.printStackTrace();
37 } // end catch
38 } // end main
39 } // end class StackInheritanceTest Display the exception’s stack trace

© 1992-2007 Pearson Education, Inc. All rights reserved.

 42
The stack is: -1

The stack is: 0 -1

The stack is: 1 0 -1

The stack is: 5 1 0 -1

5 popped
The stack is: 1 0 -1

1 popped
The stack is: 0 -1

0 popped
The stack is: -1

-1 popped
Empty stack
com.deitel.jhtp6.ch17.EmptyListException: stack is empty
at com.deitel.jhtp6.ch17.List.removeFromFront(List.java:81)
at com.deitel.jhtp6.ch17.StackInheritance.pop(StackInheritance.java:22)
at StackInheritanceTest.main(StackInheritanceTest.java:29)

© 1992-2007 Pearson Education, Inc. All rights reserved.

 43

17.7 Stacks (Cont.)

• Stack class that contains a reference to a List
– Enables us to hide the List methods that should not be in
our stack’s public interface
– Each stack method invoked delegates the call to the
appropriate List method
• method push delegates to List method insertAtFront
• method pop delegates to List method removeFromFront
• method isEmpty delegates to List method isEmpty
• method print delegates to List method print

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.12: StackComposition.java 44
2 // Class StackComposition definition with composed List object.
3 package com.deitel.jhtp6.ch17;
Outline
4
5 public class StackComposition
6 {
private List reference StackComposition
7 private List stackList;
.java
8
9 // no-argument constructor
10 public StackComposition()
(1 of 2)
11 {
12 stackList = new List( "stack" );
13 } // end StackComposition no-argument constructor
14
15 // add object to stack
16 public void push( Object object )
17 { push method delegates call to List
18 stackList.insertAtFront( object ); method insertAtFront
19 } // end method push
20

© 1992-2007 Pearson Education, Inc. All rights reserved.

21 // remove object from stack 45
22 public Object pop() throws EmptyListException
23 {
24 return stackList.removeFromFront(); Method pop delegates call to List
25 } // end method pop
method removeFromFront
26
27 // determine if stack is empty
28 public boolean isEmpty()
29 {
Method isEmpty delegates call to
30 return stackList.isEmpty();
31 } // end method isEmpty
List method isEmpty
32
33 // output stack contents
34 public void print()
35 {
36 stackList.print(); Method print delegates call to
37 } // end method print List method print
38 } // end class StackComposition

© 1992-2007 Pearson Education, Inc. All rights reserved.

 46

17.8 Queues

• Queue
– Similar to a checkout line in a supermarket
– First-in, first-out (FIFO) data structure
• Enqueue inserts nodes at the tail (or end)
• Dequeue removes nodes from the head (or front)
– Used to support print spooling
• A spooler program manages the queue of printing jobs

© 1992-2007 Pearson Education, Inc. All rights reserved.

 47

17.8 Queues (Cont.)

• Queue class that contains a reference to a List
– Method enqueue calls List method insertAtBack
– Method dequeue calls List method
removeFromFront
– Method isEmpty calls List method isEmpty
– Method print calls List method print

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.13: Queue.java 48
2 // Class Queue.
3 package com.deitel.jhtp6.ch17;
4
5 public class Queue
An object of class List
6 {
7 private List queueList;
8
9 // no-argument constructor
10 public Queue()
11 {
12 queueList = new List( "queue" );
13 } // end Queue no-argument constructor
14
15 // add object to queue
16 public void enqueue( Object object )
Method enqueue calls List
17 {
18 queueList.insertAtBack( object );
method insertAtBack
19 } // end method enqueue
20

© 1992-2007 Pearson Education, Inc. All rights reserved.

21 // remove object from queue 49
22 public Object dequeue() throws EmptyListException
23 {
24 return queueList.removeFromFront(); Method dequeue calls List
25 } // end method dequeue method removeFromFront
26
27 // determine if queue is empty
28 public boolean isEmpty()
29 {
30 return queueList.isEmpty();
31 } // end method isEmpty Method isEmpty calls
32 List method isEmpty
33 // output queue contents
34 public void print()
35 {
36 queueList.print(); Method print calls
37 } // end method print
List method print
38 } // end class Queue

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.14: QueueTest.java 50
2 // Class QueueTest.
3 import com.deitel.jhtp6.ch17.Queue;
4 import com.deitel.jhtp6.ch17.EmptyListException;
5
6 public class QueueTest
7 {
8 public static void main( String args[] )
9 {
Create a Queue object
10 Queue queue = new Queue();
11
12 // use enqueue method
13 queue.enqueue( -1 );
14 queue.print(); Enqueue four integers
15 queue.enqueue( 0 );
16 queue.print();
17 queue.enqueue( 1 );
18 queue.print();
19 queue.enqueue( 5 );
20 queue.print();
21

© 1992-2007 Pearson Education, Inc. All rights reserved.

22 // remove objects from queue 51
23 try
24 { Dequeue the objects in
25 Object removedObject = null; first-in, first-out order
26
27 while ( true )
28 {
29 removedObject = queue.dequeue(); // use dequeue method
30 System.out.printf( "%s dequeued\n", removedObject );
31 queue.print();
32 } // end while
33 } // end try
34 catch ( EmptyListException emptyListException )
35 {
36 emptyListException.printStackTrace();
37 } // end catch
38 } // end main Display the exception’s stack trace
39 } // end class QueueTest

© 1992-2007 Pearson Education, Inc. All rights reserved.

 52
The queue is: -1

The queue is: -1 0

The queue is: -1 0 1

The queue is: -1 0 1 5

-1 dequeued
The queue is: 0 1 5

0 dequeued
The queue is: 1 5

1 dequeued
The queue is: 5

5 dequeued
Empty queue
com.deitel.jhtp6.ch17.EmptyListException: queue is empty
at com.deitel.jhtp6.ch17.List.removeFromFront(List.java:81)
at com.deitel.jhtp6.ch17.Queue.dequeue(Queue.java:24)
at QueueTest.main(QueueTest.java:29)

© 1992-2007 Pearson Education, Inc. All rights reserved.

 53

17.9 Trees

• Trees
– The root node is the first node in a tree
– Each link refers to a child
• Left child is the root of the left subtree
• Right child is the root of the right subtree
• Siblings are the children of a specific node
– A leaf node has no children

© 1992-2007 Pearson Education, Inc. All rights reserved.

 54

17.9 Trees (Cont.)

• Binary search trees

– Values in the left subtree are less than the value in that
subtree’s parent node and values in the right subtree are
greater than the value in that subtree’s parent node
• Traversing a tree
– Inorder - traverse left subtree, then process root, then
traverse right subtree
– Preorder - process root, then traverse left subtree, then
traverse right subtree
– Postorder - traverse left subtree, then traverse right
subtree, then process root

© 1992-2007 Pearson Education, Inc. All rights reserved.

 55

Fig. 17.15 | Binary tree graphical representation.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 56

Fig. 17.16 | Binary search tree containing 12 values.

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.17: Tree.java 57
2 // Definition of class TreeNode and class Tree.
3 package com.deitel.jhtp6.ch17;
4
5 // class TreeNode definition
6 class TreeNode
7 {
8 // package access members
9 TreeNode leftNode; // left node
10 int data; // node value
11 TreeNode rightNode; // right node
12
13 // constructor initializes data and makes this a leaf node
14 public TreeNode( int nodeData )
15 {
16 data = nodeData;
17 leftNode = rightNode = null; // node has no children
18 } // end TreeNode no-argument constructor
19

© 1992-2007 Pearson Education, Inc. All rights reserved.

20 // locate insertion point and insert new node; ignore duplicate values 58
21 public void insert( int insertValue )
22 {
Outline
23 // insert in left subtree Allocate a new TreeNode and
24 if ( insertValue < data )
assign it to reference leftNode
25 {
Tree.java
26 // insert new TreeNode
27 if ( leftNode == null )
(2 of 5)
28 leftNode = new TreeNode( insertValue );
29 else // continue traversing left subtree
30 leftNode.insert( insertValue );
31 } // end if
32 else if ( insertValue > data ) // insert in right subtree
33 {
Allocate a new TreeNode and assign
34 // insert new TreeNode
35 if ( rightNode == null )
it to reference rightNode
36 rightNode = new TreeNode( insertValue );
37 else // continue traversing right subtree
38 rightNode.insert( insertValue );
39 } // end else if
40 } // end method insert
41 } // end class TreeNode
42

© 1992-2007 Pearson Education, Inc. All rights reserved.

43 // class Tree definition 59
44 public class Tree
45 { TreeNode reference to
46 private TreeNode root; the root node of the tree
47
48 // constructor initializes an empty Tree of integers
49 public Tree()
50 {
51 root = null;
52 } // end Tree no-argument constructor
53
54 // insert a new node in the binary search tree Allocate a new TreeNode
55 public void insertNode( int insertValue )
and assign it to reference
56 {
57 if ( root == null )
root
58 root = new TreeNode( insertValue ); // create the root node here
59 else
60 root.insert( insertValue ); // call the insert method
61 } // end method insertNode
62
63 // begin preorder traversal
64 public void preorderTraversal() Call TreeNode method insert
65 {
66 preorderHelper( root );
67 } // end method preorderTraversal Call Tree helper method
68
preorderHelper to
begin traversal

© 1992-2007 Pearson Education, Inc. All rights reserved.

69 // recursive method to perform preorder traversal 60
70 private void preorderHelper( TreeNode node )
71 {
72 if ( node == null )
73 return;
74
75 System.out.printf( "%d ", node.data ); // output node data
76 preorderHelper( node.leftNode ); // traverse left subtree
77 preorderHelper( node.rightNode ); // traverse right subtree
78 } // end method preorderHelper
79
80 // begin inorder traversal
81 public void inorderTraversal()
82 {
83 inorderHelper( root ); Call Tree helper method
84 } // end method inorderTraversal inorderHelper to
85 begin traversal
86 // recursive method to perform inorder traversal
87 private void inorderHelper( TreeNode node )
88 {
89 if ( node == null )
90 return;
91
92 inorderHelper( node.leftNode ); // traverse left subtree
93 System.out.printf( "%d ", node.data ); // output node data
94 inorderHelper( node.rightNode ); // traverse right subtree
95 } // end method inorderHelper
96

© 1992-2007 Pearson Education, Inc. All rights reserved.

97 // begin postorder traversal 61
98 public void postorderTraversal()
Call Tree helper method
99 {
100 postorderHelper( root );
postorderHelper
101 } // end method postorderTraversal to begin traversal
102
103 // recursive method to perform postorder traversal
104 private void postorderHelper( TreeNode node )
105 {
106 if ( node == null )
107 return;
108
109 postorderHelper( node.leftNode ); // traverse left subtree
110 postorderHelper( node.rightNode ); // traverse right subtree
111 System.out.printf( "%d ", node.data ); // output node data
112 } // end method postorderHelper
113 } // end class Tree

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 17.18: TreeTest.java 62
2 // This program tests class Tree.
3 import java.util.Random;
4 import com.deitel.jhtp6.ch17.Tree;
5
6 public class TreeTest
7 {
8 public static void main( String args[] )
9 {
10 Tree tree = new Tree(); Create a Tree object
11 int value;
12 Random randomNumber = new Random();
13
14 System.out.println( "Inserting the following values: " );
15
16 // insert 10 random integers from 0-99 in tree
17 for ( int i = 1; i <= 10; i++ )
18 {
19 value = randomNumber.nextInt( 100 );
20 System.out.print( value + " " );
21 tree.insertNode( value ); Insert values into tree
22 } // end for
23
24 System.out.println ( "\n\nPreorder traversal" );
25 tree.preorderTraversal(); // perform preorder traversal of tree
26

© 1992-2007 Pearson Education, Inc. All rights reserved.

27 System.out.println ( "\n\nInorder traversal" ); 63
28 tree.inorderTraversal(); // perform inorder traversal of tree
29
30 System.out.println ( "\n\nPostorder traversal" );
31 tree.postorderTraversal(); // perform postorder traversal of tree
32 System.out.println();
33 } // end main

34 } // end class TreeTest

Inserting the following values:

92 73 77 16 30 30 94 89 26 80

Preorder traversal
92 73 16 30 26 77 89 80 94

Inorder traversal
16 26 30 73 77 80 89 92 94

Postorder traversal
26 30 16 80 89 77 73 94 92

© 1992-2007 Pearson Education, Inc. All rights reserved.

 64

17.9 Trees (Cont.)

• Inorder traversal steps

– Return immediately if the reference parameter is null
– Traverse the left subtree with a call to inorderHelper
– Process the value in the node
– Traverse the right subtree with a call to inorderHelper
• Binary tree sort
– The inorder traversal of a binary search tree prints the
node values in ascending order

© 1992-2007 Pearson Education, Inc. All rights reserved.

 65

17.9 Trees (Cont.)

• Preorder traversal steps

– Return immediately if the reference parameter is null
– Process the value in the node
– Traverse the left subtree with a call to preorderHelper
– Traverse the right subtree with a call to
preorderHelper

© 1992-2007 Pearson Education, Inc. All rights reserved.

 66

17.9 Trees (Cont.)

• Postorder traversal steps

– Return immediately if the reference parameter is null
– Traverse the left subtree with a call to
postorderHelper
– Traverse the right subtree with a call to
postorderHelper
– Process the value in the node

© 1992-2007 Pearson Education, Inc. All rights reserved.

 67

17.9 Trees (Cont.)

• Duplicate elimination
– Because duplicate values follow the same “go left” or “go
right” decisions, the insertion operation eventually
compares the duplicate with a same-valued node
– The duplicate can then be ignored
• Tightly packed (or balanced) trees
– Each level contains about twice as many elements as the
previous level
– Finding a match or determining that no match exists
among n elements requires at most log 2n comparisons
• Level-order traversal of a binary tree
– Visits the nodes of the tree row by row, starting at the root
node level
© 1992-2007 Pearson Education, Inc. All rights reserved.
 68

Fig. 17.19 | Binary search tree with seven values.

© 1992-2007 Pearson Education, Inc. All rights reserved.