Transcript JavaHTP6e_17

1
17
Data Structures
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
3
OBJECTIVES
In this chapter you will learn:
 To form linked data structures using references, selfreferential 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 typewrapper 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.
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
5
17.1 Introduction
• Dynamic data structures
– Linear data structures
• Linked lists
• Stacks
• Queues
– Binary trees
 2005 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
 2005 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
• J2SE 5.0 automatically performs these
conversions
– Called autoboxing and auto-unboxing
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
9
Fig. 17.1 | Self-referential-class objects linked together.
 2005 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
 2005 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
 2005 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.
 2005 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.
 2005 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.
 2005 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
 2005 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).
 2005 Pearson Education, Inc. All rights reserved.
17
Fig. 17.2 | Linked list graphical representation.
 2005 Pearson Education, Inc. All rights reserved.
1
2
3
4
// Fig. 17.3: List.java
// ListNode and List class definitions.
package com.deitel.jhtp6.ch17;
18
Outline
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
10
ListNode nextNode;
11
12
// constructor creates a ListNode that refers to object
13
14
15
ListNode( Object object )
{
this( object, null );
16
17
18
19
20
21
22
23
24
25
} // end ListNode one-argument constructor
List.java
(1 of 6)
data can refer to any object
Stores a reference to the next
ListNode object in the linked list
// constructor creates ListNode that refers to
// Object and to next ListNode
ListNode( Object object, ListNode node )
{
data = object;
nextNode = node;
} // end ListNode two-argument constructor
 2005 Pearson Education,
Inc. All rights reserved.
26
27
// return reference to data in node
Object getObject()
28
29
30
31
{
32
33
34
35
// return reference to next node in list
ListNode getNext()
{
return nextNode; // get next node
19
Outline
return data; // return Object in this node
} // end method getObject
36
} // end method getNext
37 } // end class ListNode
38
39 // class List definition
40 public class List
List.java
(2 of 6)
References to the first and last
ListNodes in a List
41 {
42
43
private ListNode firstNode;
private ListNode lastNode;
44
45
private String name; // string like "list" used in printing
46
47
48
// constructor creates empty List with "list" as the name
public List()
{
49
50
51
this( "list" );
} // end List no-argument constructor
Call one-argument constructor
 2005 Pearson Education,
Inc. All rights reserved.
52
53
54
// constructor creates an empty List with a name
public List( String listName )
{
Initialize
20
both references to null
name = listName;
firstNode = lastNode = null;
55
56
57
58
59
60
} // end List one-argument constructor
61
62
{
63
64
65
66
firstNode = lastNode = new ListNode( insertItem );
else // firstNode refers to new node
firstNode = new ListNode( insertItem, firstNode );
} // end method insertAtFront
67
68
// insert Object at end of List
69
public void insertAtBack( Object insertItem )
70
71
{
72
73
74
75
76
Outline
// insert Object at front of List
public void insertAtFront( Object insertItem )
List.java
(3 of 6)
if ( isEmpty() ) // firstNode and lastNode refer to same object
if ( isEmpty() ) // firstNode and lastNode refer to same Object
firstNode = lastNode = new ListNode( insertItem );
else // lastNode's nextNode refers to new node
lastNode = lastNode.nextNode = new ListNode( insertItem );
} // end method insertAtBack
 2005 Pearson Education,
Inc. All rights reserved.
77
78
79
// remove first node from List
public Object removeFromFront() throws EmptyListException
{
80
81
if ( isEmpty() ) // throw exception if List is empty
throw new EmptyListException( name );
82
83
84
85
Object removedItem = firstNode.data; // retrieve data being removed
// update references firstNode and lastNode
86
87
if ( firstNode == lastNode )
firstNode = lastNode = null;
88
89
90
91
else
firstNode = firstNode.nextNode;
21
Outline
List.java
(4 of 6)
return removedItem; // return removed node data
92
93
} // end method removeFromFront
94
// remove last node from List
95
96
public Object removeFromBack() throws EmptyListException
{
97
98
99
if ( isEmpty() ) // throw exception if List is empty
throw new EmptyListException( name );
100
101
Object removedItem = lastNode.data; // retrieve data being removed
 2005 Pearson Education,
Inc. All rights reserved.
102
// update references firstNode and lastNode
103
if ( firstNode == lastNode )
104
105
106
22
Outline
firstNode = lastNode = null;
else // locate new last node
{
107
ListNode current = firstNode;
108
109
110
List.java
// loop while current node does not refer to lastNode
while ( current.nextNode != lastNode )
(5 of 6)
111
112
113
114
115
current = current.nextNode;
lastNode = current; // current is new lastNode
current.nextNode = null;
} // end else
116
117
118
119
return removedItem; // return removed node data
} // end method removeFromBack
120
121
122
123
// determine whether list is empty
whether
public boolean isEmpty()
{
return firstNode == null; // return true if List is empty
124
125
} // end method isEmpty
Predicate method that determines
the list is empty
 2005 Pearson Education,
Inc. All rights reserved.
126
127
// output List contents
public void print()
128
{
129
130
131
if ( isEmpty() )
{
23
Display the list’s contents
System.out.printf( "Empty %s\n", name );
List.java
132
133
134
return;
} // end if
135
136
137
System.out.printf( "The %s is: ", name );
ListNode current = firstNode;
138
// while not at end of list, output current node's data
139
140
141
while ( current != null )
{
System.out.printf( "%s ", current.data );
142
143
144
145
Outline
Display a message indicating (6 of 6)
that the list is empty
Output a string representation
of current.data
current = current.nextNode;
} // end while
System.out.println( "\n" );
146
} // end method print
147 } // end class List
Move to the next node in the list
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 17.4: EmptyListException.java
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
11
this( "List" ); // call other EmptyListException constructor
} // end EmptyListException no-argument constructor
24
Outline
EmptyListException
.java
12
13
14
// one-argument constructor
public EmptyListException( String name )
15
{
16
17
super( name + " is empty" ); // call superclass constructor
} // end EmptyListException one-argument constructor
18 } // end class EmptyListException
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 17.5: ListTest.java
2
// ListTest class to demonstrate List capabilities.
3
import com.deitel.jhtp6.ch17.List;
4
5
import com.deitel.jhtp6.ch17.EmptyListException;
6
7
8
public class ListTest
{
public static void main( String args[] )
9
10
11
25
Outline
ListTest.java
(1 of 3)
{
List list = new List(); // create the List container
12
13
14
// insert integers in list
list.insertAtFront( -1 );
list.print();
15
list.insertAtFront( 0 );
16
17
list.print();
list.insertAtBack( 1 );
18
19
20
21
list.print();
list.insertAtBack( 5 );
list.print();
Insert objects at the beginning of the list
using method insertAtFront
Insert objects at the end of the list
using method insertAtBack
JVM autoboxes each literal
value in an Integer object
 2005 Pearson Education,
Inc. All rights reserved.
22
23
// remove objects from list; print after each removal
try
24
25
26
27
{
Object removedObject = list.removeFromFront();
System.out.printf( "%s removed\n", removedObject );
list.print();
28
29
30
31
32
removedObject = list.removeFromFront();
System.out.printf( "%s removed\n", removedObject );
list.print();
33
34
35
removedObject = list.removeFromBack();
System.out.printf( "%s removed\n", removedObject );
list.print();
36
removedObject = list.removeFromBack();
System.out.printf( "%s removed\n", removedObject );
37
38
39
40
41
list.print();
} // end try
catch ( EmptyListException emptyListException )
42
43
44
{
45
emptyListException.printStackTrace();
} // end catch
26
Outline
Deletes objects from the front of the list
using method removeFromFront
ListTest.java
(2 of 3)
Delete objects from the end of the list
using method removeFromBack
Call List method print to
display the current list contents
Exception handler for EmptyListException
} // end main
46 } // end class ListTest
 2005 Pearson Education,
Inc. All rights reserved.
The list is: -1
The list is: 0 -1
27
Outline
The list is: 0 -1 1
The list is: 0 -1 1 5
0 removed
The list is: -1 1 5
ListTest.java
(3 of 3)
-1 removed
The list is: 1 5
5 removed
The list is: 1
1 removed
Empty list
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
29
Fig. 17.6 | Graphical representation of operation insertAtFront.
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
31
Fig. 17.7 | Graphical representation of operation insertAtBack.
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
33
Fig. 17.8 | Graphical representation of operation removeFromFront.
 2005 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
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
36
Fig. 17.9 | Graphical representation of operation removeFromBack.
 2005 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
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 17.10: StackInheritance.java
2
// Derived from class List.
3
package com.deitel.jhtp6.ch17;
4
5
public class StackInheritance extends List
6
{
39
Outline
Class StackInheritance
extends class List
7
8
9
// no-argument constructor
public StackInheritance()
{
10
11
super( "stack" );
} // end StackInheritance no-argument constructor
12
13
// add object to stack
14
15
16
public void push( Object object )
{
insertAtFront( object );
17
} // end method push
18
19
// remove object from stack
20
public Object pop() throws EmptyListException
21
{
22
return removeFromFront();
23
} // end method pop
24 } // end class StackInheritance
StackInheritance
.java
Method push calls inherited
method insertAtFront
Method pop calls inherited method
removeFromFront
 2005 Pearson Education,
Inc. All rights reserved.
1
// Fig. 17.11: StackInheritanceTest.java
2
// Class StackInheritanceTest.
3
import com.deitel.jhtp6.ch17.StackInheritance;
4
5
import com.deitel.jhtp6.ch17.EmptyListException;
6
7
8
public class StackInheritanceTest
{
public static void main( String args[] )
9
10
11
{
StackInheritance stack = new StackInheritance();
12
13
14
// use push method
stack.push( -1 );
stack.print();
15
stack.push( 0 );
16
17
stack.print();
stack.push( 1 );
18
19
20
21
stack.print();
stack.push( 5 );
stack.print();
40
Outline
StackInheritance
Test.java
(1 of 3)
Create a StackInheritenace object
Push integers onto the stack
 2005 Pearson Education,
Inc. All rights reserved.
22
// remove items from stack
23
24
try
{
41
Outline
Pop the objects from the stack
in an infinite while loop
25
Object removedObject = null;
26
27
28
29
30
31
while ( true )
{
removedObject = stack.pop(); // use pop method
System.out.printf( "%s popped\n", removedObject );
stack.print();
32
} // end while
33
34
} // end try
catch ( EmptyListException emptyListException )
35
36
37
{
38
StackInheritance
Test.java
(2 of 3)
Implicitly call inherited
method print
emptyListException.printStackTrace();
} // end catch
} // end main
39 } // end class StackInheritanceTest
Display the exception’s stack trace
 2005 Pearson Education,
Inc. All rights reserved.
The stack is: -1
The stack is: 0 -1
42
Outline
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
StackInheritance
Test.java
(3 of 3)
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)
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 17.12: StackComposition.java
2
// Class StackComposition definition with composed List object.
3
package com.deitel.jhtp6.ch17;
44
Outline
4
5
6
public class StackComposition
{
7
8
private List stackList;
StackComposition
.java
9
10
// no-argument constructor
public StackComposition()
(1 of 2)
11
{
private List reference
stackList = new List( "stack" );
12
13
14
15
16
} // end StackComposition no-argument constructor
17
18
19
20
{
// add object to stack
public void push( Object object )
stackList.insertAtFront( object );
} // end method push
push method delegates call to List
method insertAtFront
 2005 Pearson Education,
Inc. All rights reserved.
21
// remove object from stack
22
23
public Object pop() throws EmptyListException
{
24
return stackList.removeFromFront();
25
26
27
28
29
30
} // end method pop
31
} // end method isEmpty
32
33
// output stack contents
34
35
36
public void print()
{
stackList.print();
37
} // end method print
// determine if stack is empty
public boolean isEmpty()
{
return stackList.isEmpty();
45
Outline
Method pop delegates call to List
method removeFromFront
StackComposition
.java
(2 of 2)
Method isEmpty delegates call to
List method isEmpty
Method print delegates call to
List method print
38 } // end class StackComposition
 2005 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
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
1
2
// Fig. 17.13: Queue.java
// Class Queue.
3
package com.deitel.jhtp6.ch17;
4
5
public class Queue
6
{
private List queueList;
7
8
9
// no-argument constructor
10
11
public Queue()
{
12
13
14
queueList = new List( "queue" );
} // end Queue no-argument constructor
15
16
// add object to queue
public void enqueue( Object object )
17
{
18
19
20
queueList.insertAtBack( object );
} // end method enqueue
48
Outline
An object of class List
Queue.java
(1 of 2)
Method enqueue calls List
method insertAtBack
 2005 Pearson Education,
Inc. All rights reserved.
21
// remove object from queue
22
23
public Object dequeue() throws EmptyListException
{
24
return queueList.removeFromFront();
25
26
27
28
29
30
} // end method dequeue
31
} // end method isEmpty
32
33
// output queue contents
34
35
36
public void print()
{
queueList.print();
37
} // end method print
// determine if queue is empty
public boolean isEmpty()
{
return queueList.isEmpty();
38 } // end class Queue
49
Outline
Method dequeue calls List
method removeFromFront
Queue.java
(2 of 2)
Method isEmpty calls
List method isEmpty
Method print calls
List method print
 2005 Pearson Education,
Inc. All rights reserved.
1
2
// Fig. 17.14: QueueTest.java
// Class QueueTest.
3
4
5
import com.deitel.jhtp6.ch17.Queue;
import com.deitel.jhtp6.ch17.EmptyListException;
6 public class QueueTest
7 {
8
public static void main( String args[] )
9
{
10
Queue queue = new Queue();
11
12
// use enqueue method
13
queue.enqueue( -1 );
14
15
queue.print();
queue.enqueue( 0 );
16
queue.print();
17
18
queue.enqueue( 1 );
queue.print();
19
20
21
queue.enqueue( 5 );
queue.print();
50
Outline
QueueTest.java
Create a Queue object
(1 of 3)
Enqueue four integers
 2005 Pearson Education,
Inc. All rights reserved.
22
// remove objects from queue
23
try
24
{
Object removedObject = null;
25
51
Dequeue the objects in
first-in, first-out order
Outline
26
27
while ( true )
28
{
Queue.java
29
removedObject = queue.dequeue(); // use dequeue method
30
System.out.printf( "%s dequeued\n", removedObject );
31
queue.print();
} // end while
32
33
} // end try
34
catch ( EmptyListException emptyListException )
35
{
36
37
38
(2 of 3)
emptyListException.printStackTrace();
} // end catch
} // end main
Display the exception’s stack trace
39 } // end class QueueTest
 2005 Pearson Education,
Inc. All rights reserved.
The queue is: -1
The queue is: -1 0
52
Outline
The queue is: -1 0 1
The queue is: -1 0 1 5
-1 dequeued
The queue is: 0 1 5
QueueTest.java
(3 of 3)
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)
 2005 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
 2005 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
 2005 Pearson Education, Inc. All rights reserved.
55
Fig. 17.15 | Binary tree graphical representation.
 2005 Pearson Education, Inc. All rights reserved.
56
Fig. 17.16 | Binary search tree containing 12 values.
 2005 Pearson Education, Inc. All rights reserved.
1
// Fig. 17.17: Tree.java
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
57
Outline
Tree.java
Declare left child, node
value and right child
13
// constructor initializes data and makes this a leaf node
14
15
public TreeNode( int nodeData )
{
16
data = nodeData;
17
leftNode = rightNode = null; // node has no children
18
19
(1 of 5)
} // end TreeNode no-argument constructor
 2005 Pearson Education,
Inc. All rights reserved.
20
21
22
23
24
25
26
27
// locate insertion point and insert new node; ignore duplicate values
public void insert( int insertValue )
{
// insert in left subtree
if ( insertValue < data )
{
// insert new TreeNode
if ( leftNode == null )
Outline
Allocate a new TreeNode and
assign it to reference leftNode
Tree.java
(2 of 5)
leftNode = new TreeNode( insertValue );
28
58
29
30
31
32
else // continue traversing left subtree
leftNode.insert( insertValue );
} // end if
else if ( insertValue > data ) // insert in right subtree
33
{
34
// insert new TreeNode
35
36
if ( rightNode == null )
rightNode = new TreeNode( insertValue );
Allocate a new TreeNode and assign
it to reference rightNode
37
else // continue traversing right subtree
38
rightNode.insert( insertValue );
39
} // end else if
40
} // end method insert
41 } // end class TreeNode
42
 2005 Pearson Education,
Inc. All rights reserved.
43 // class Tree definition
44 public class Tree
45 {
46
private TreeNode root;
59
TreeNode reference to
the root node of the tree
47
48
49
50
51
52
53
// constructor initializes an empty Tree of integers
public Tree()
{
root = null;
} // end Tree no-argument constructor
54
// insert a new node in the binary search tree
55
public void insertNode( int insertValue )
56
57
58
59
60
{
61
62
} // end method insertNode
63
// begin preorder traversal
64
65
public void preorderTraversal()
{
66
67
68
preorderHelper( root );
} // end method preorderTraversal
Outline
Tree.java
(3 of 5)
Allocate a new TreeNode
and assign it to reference
root
if ( root == null )
root = new TreeNode( insertValue ); // create the root node here
else
root.insert( insertValue ); // call the insert method
Call TreeNode method insert
Call Tree helper method
preorderHelper
 2005 Pearson Education,
Inc. All rights reserved.
69
// recursive method to perform preorder traversal
70
71
private void preorderHelper( TreeNode node )
{
60
Outline
if ( node == null )
72
return;
73
74
75
76
77
78
System.out.printf( "%d ", node.data ); // output node data
preorderHelper( node.leftNode );
// traverse left subtree
preorderHelper( node.rightNode );
// traverse right subtree
} // end method preorderHelper
Tree.java
(4 of 5)
79
80
81
// begin inorder traversal
public void inorderTraversal()
82
83
84
85
86
{
87
88
89
90
91
92
93
private void inorderHelper( TreeNode node )
{
if ( node == null )
return;
94
95
96
inorderHelper( node.rightNode );
} // end method inorderHelper
Call Tree helper method
inorderHelper
inorderHelper( root );
} // end method inorderTraversal
// recursive method to perform inorder traversal
inorderHelper( node.leftNode );
// traverse left subtree
System.out.printf( "%d ", node.data ); // output node data
// traverse right subtree
 2005 Pearson Education,
Inc. All rights reserved.
97
// begin postorder traversal
98
99
public void postorderTraversal()
{
100
101
102
103
104
105
106
107
108
109
110
111
112
postorderHelper( root );
61
Call Tree helper method
postorderHelper
Outline
} // end method postorderTraversal
// recursive method to perform postorder traversal
private void postorderHelper( TreeNode node )
{
if ( node == null )
Tree.java
(5 of 5)
return;
postorderHelper( node.leftNode );
// traverse left subtree
postorderHelper( node.rightNode );
// traverse right subtree
System.out.printf( "%d ", node.data ); // output node data
} // end method postorderHelper
113 } // end class Tree
 2005 Pearson Education,
Inc. All rights reserved.
1
2
// Fig. 17.18: TreeTest.java
// This program tests class Tree.
3
4
import java.util.Random;
import com.deitel.jhtp6.ch17.Tree;
62
Outline
5
6
public class TreeTest
7
8
{
9
TreeTest.java
public static void main( String args[] )
(1 of 2)
{
10
Tree tree = new Tree();
11
12
13
14
15
16
int value;
Random randomNumber = new Random();
17
18
for ( int i = 1; i <= 10; i++ )
{
Create a Tree object
System.out.println( "Inserting the following values: " );
// insert 10 random integers from 0-99 in tree
19
20
value = randomNumber.nextInt( 100 );
System.out.print( value + " " );
21
tree.insertNode( value );
Insert values into tree
22
23
} // end for
24
25
26
System.out.println ( "\n\nPreorder traversal" );
tree.preorderTraversal(); // perform preorder traversal of tree
 2005 Pearson Education,
Inc. All rights reserved.
27
System.out.println ( "\n\nInorder traversal" );
28
tree.inorderTraversal(); // perform inorder traversal of tree
63
Outline
29
30
System.out.println ( "\n\nPostorder traversal" );
31
tree.postorderTraversal(); // perform postorder traversal of tree
32
System.out.println();
33
TreeTest.java
} // end main
34 } // end class TreeTest
(2 of 2)
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
 2005 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
 2005 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
 2005 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
 2005 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 log2n comparisons
• Level-order traversal of a binary tree
– Visits the nodes of the tree row by row, starting at the root
node level
 2005 Pearson Education, Inc. All rights reserved.
68
Fig. 17.19 | Binary search tree with seven values.
 2005 Pearson Education, Inc. All rights reserved.