19

Data Structures

Objectives

•To be able to form linked data structures using references, self-referential classes and recursion.

•To be able to create and manipulate dynamic data structures, such as linked lists, queues, stacks and binary trees.

•To understand various important applications of linked data structures.

•To understand how to create reusable data structures with classes, inheritance and composition.

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 think that I shall never see

A poem lovely as a tree.

Joyce Kilmer

Outline

19.1Introduction

19.2Self-Referential Classes

19.3Dynamic Memory Allocation

19.4Linked Lists

19.5Stacks

19.6Queues

19.7Trees

Summary • Terminology • Self-Review Exercises • Answers to Self-Review Exercises • Exercises • Special Section: Building Your Own Compiler

19.1 Introduction

We have studied such fixed-size data structures as singleand double-subscripted arrays. This chapter introduces dynamic data structures that grow and shrink at execution time. Linked lists are collections of data items “lined up in a row”—insertions and deletions can be made anywhere in a linked list. Stacks are important in compilers and operating systems; insertions and deletions are made only at one end of a stack—its top. Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue and deletions are made from the front (also referred to as the head) of a queue. Binary trees facilitate high-speed searching and sorting of data, eliminating of duplicate data items efficiently, representing file system directories, compiling expressions into machine language and many other interesting applications.

We will discuss each of the major types of data structures and implement programs that create and manipulate them. We use classes, inheritance and composition to create and package these data structures for reusability and maintainability. In Chapter 20, “Java Utilities Package and Bit Manipulation,” and Chapter 21, “Collections,” we discuss Java’s predefined classes that implement the data structures discussed in this chapter.

The chapter examples are practical programs that can be used in more advanced courses and in industrial applications. The exercises include a rich collection of useful applications.

We encourage you to attempt the major project described in the special section entitled Building Your Own Compiler. You have been using a Java compiler to translate your Java programs to bytecodes so that you could execute these programs on your computer. In this project, you will actually build your own compiler. It will read a file of statements written in a simple, yet powerful high-level language similar to early versions of the popular language Basic. Your compiler will translate these statements into a file of Simpletron Machine Language (SML) instructions—SML is the language you learned in the Chapter 7 special section, Building Your Own Computer. Your Simpletron Simulator program will then execute the SML program produced by your compiler! Implementing this project by using an object-oriented approach will give you a wonderful opportunity to exercise most of what you have learned in this book. The special section carefully walks you through the specifications of the high-level language and describes the algorithms you will need to con-

vert each type of high-level language statement into machine language instructions. If you enjoy being challenged, you might attempt the many enhancements to both the compiler and the Simpletron Simulator suggested in the exercises.

19.2 Self-Referential Classes

A self-referential class contains an instance variable that refers to another object of the same class type. For example, the definition

class Node { private int data;

private Node nextNode;

}

defines class Node. This type has two private instance variables—integer data and Node reference nextNode. Member nextNode references an object of type Node, an object of the same type as the one being declared here—hence, the term “self-referential class.” Member nextNode is a link—nextNode “links” an object of type Node to another object of the same type. Type Node also has five methods: a constructor that receives an integer to initialize data, a setData method to set the value data, a getData method to return the value of data, a setNext method to set the value of nextNode and a getNext method to return the value of member nextNode.

Programs can link self-referential objects together to form such useful data structures as lists, queues, stacks and trees. Figure 19.1 illustrates two self-referential objects linked together to form a list. A backslash—representing a null reference—is placed in the link member of the second self-referential object to indicate that the link does not refer to another object. The backslash is for illustration purposes; it does not correspond to the backslash character in Java. Normally, a null reference indicates the end of a data structure.

Common Programming Error 19.1

Not setting the link in the last node of a list to null is a logic error.

19.3 Dynamic Memory Allocation

Creating and maintaining dynamic data structures requires 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. As we have already learned, Java programs do not explicitly release dynamically allocated memory. Rather, Java performs automatic garbage collection on objects that are no longer referenced in a program.

The limit for dynamic memory allocation can be as large as the amount of available physical memory in the computer or the amount of available disk space in a virtual-memory system. Often, the limits are much smaller, because the computer’s available memory must be shared among many applications.

Linked lists can be maintained in sorted order simply by inserting each new element at the proper point in the list (it does, of course, take time to locate the proper insertion point). Existing list elements do not need to be moved.

Linked list nodes normally are not stored contiguously in memory. Rather, they are logically contiguous. Figure 19.2 illustrates a linked list with several nodes. This diagram presents a singly-linked list—each node contains one reference to the next node in the list. Often, linked lists are implemented as doubly-linked lists—each node contains a reference to the next node in the list and a reference to the previous node in the list. Java’s LinkedList class (see Chapter 21) is a doubly-linked list implementation.

Performance Tip 19.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.

Performance Tip 19.4

The elements of an array are stored contiguously in memory. This allows immediate access to any array element, because the address of any element 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.

Performance Tip 19.5

Using dynamic memory allocation (instead of arrays) for data structures that grow and shrink at execution time can save memory. Keep in mind, however, that references occupy space, and that dynamic memory allocation incurs the overhead of method calls.

The program of Fig. 19.3–Fig. 19.5 uses a List class to manipulate a list of miscellaneous object types. The main method of class ListTest (Fig. 19.5) creates a list of objects, inserts objects at the beginning of the list using method insertAtFront, inserts objects at the end of the list using method insertAtBack, deletes objects from the front of the list using method removeFromFront and deletes objects from the end of the list using method removeFromBack. After each insert and remove operation, ListTest calls List method print to display the current list contents. A detailed discussion of the program follows. If an attempt is made to remove an item from an empty list, an EmptyListException (Fig. 19.4) occurs.

The program of Fig. 19.3–Fig. 19.5 consists of four classes—ListNode (Fig. 19.3), List (Fig. 19.3), EmptyListException (Fig. 19.4) and ListTest (Fig. 19.5). The

List and ListNode classes are placed in package com.deitel.jhtp4.ch19, so they can be reused throughout this chapter. Encapsulated in each List object is a linked list of ListNode objects. The ListNode class (lines 6–38 of Fig. 19.3) consists of package-access members data and nextNode. ListNode member data can refer to any Object. ListNode member nextNode stores a reference to the next ListNode object in the linked list.

[Note: Many of the classes in this chapter are defined in the package com.deitel.jhtp4.ch19. Each such class should be compiled with the -d com- mand-line option to javac. When compiling the classes that are not in this package and when running the programs, be sure to use the -classpath option to javac and java, respectively.]

H D ... Q

Fig. 19.2 A graphical representation of a linked list.

1// Fig. 19.3: List.java

2 // Class ListNode and class List definitions

3 package com.deitel.jhtp4.ch19;

4

5 // class to represent one node in a list 6 class ListNode {

7

8 // package access members; List can access these directly

9Object data;

10 ListNode nextNode;

11

12// constructor to create a ListNode that refers to object

13ListNode( Object object )

14{

15this( object, null );

16}

17

18// constructor to create ListNode that refers to Object

19// and to next ListNode in List

20ListNode( Object object, ListNode node )

21{

22data = object;

23nextNode = node;

24}

25

26// return Object in this node

27Object getObject()

28{

29return data;

30}

31

32// get next node

33ListNode getNext()

34{

35return nextNode;

36}

37

38 } // end class ListNode

39

Fig. 19.3 Definitions of class ListNode and class List (part 1 of 4).

40// class List definition

41public class List {

42private ListNode firstNode;

43private ListNode lastNode;

44private String name; // String like "list" used in printing

46// construct an empty List with a name

47public List( String string )

48{

49name = string;

50firstNode = lastNode = null;

51}

52

53// construct empty List with "list" as the name

54public List()

55{

56this( "list" );

57}

58

59// Insert Object at front of List. If List is empty,

60// firstNode and lastNode will refer to same object.

61// Otherwise, firstNode refers to new node.

62public synchronized void insertAtFront( Object insertItem )

63{

64if ( isEmpty() )

68firstNode = new ListNode( insertItem, firstNode );

69}

70

71// Insert Object at end of List. If List is empty,

72// firstNode and lastNode will refer to same Object.

73// Otherwise, lastNode's nextNode refers to new node.

74public synchronized void insertAtBack( Object insertItem )

75{

76if ( isEmpty() )

84// remove first node from List

85public synchronized Object removeFromFront()

86throws EmptyListException

87{

88Object removeItem = null;

89

90// throw exception if List is empty

91if ( isEmpty() )

92 throw new EmptyListException( name );

Fig. 19.3 Definitions of class ListNode and class List (part 2 of 4).

93

94// retrieve data being removed

95removeItem = firstNode.data;

97// reset the firstNode and lastNode references

98if ( firstNode == lastNode )

104// return removed node data

105return removeItem;

106}

107

108// Remove last node from List

109public synchronized Object removeFromBack()

110throws EmptyListException

111{

112Object removeItem = null;

113

114// throw exception if List is empty

115if ( isEmpty() )

116 throw new EmptyListException( name );

117

118// retrieve data being removed

119removeItem = lastNode.data;

121// reset firstNode and lastNode references

122if ( firstNode == lastNode )

136current.nextNode = null;

137}

138

139// return removed node data

140return removeItem;

141}

142

143// return true if List is empty

144public synchronized boolean isEmpty()

145{

Fig. 19.3 Definitions of class ListNode and class List (part 3 of 4).

146return firstNode == null;

147}

148

149// output List contents

150public synchronized void print()

151{

152if ( isEmpty() ) {

153 System.out.println( "Empty " + name );

154return;

155}

156

157 System.out.print( "The " + name + " is: " );

158

159 ListNode current = firstNode;

160

161// while not at end of list, output current node's data

162while ( current != null ) {

163 System.out.print( current.data.toString() + " " );

164current = current.nextNode;

165}

166

167System.out.println( "\n" );

168}

169

170 } // end class List

Fig. 19.3 Definitions of class ListNode and class List (part 4 of 4).

Class List contains private members firstNode (a reference to the first

ListNode in a List) and lastNode (a reference to the last ListNode in a List). The constructors (lines 47–51 and 54–57) initialize both references to null. The most important methods of class List are the synchronized methods insertAtFront (lines 62–69), insertAtBack (lines 74–82), removeFromFront (lines 85–106) and removeFromBack (lines 109–141). These methods are declared synchronized so List objects can be multithread safe when used in a multithreaded program. If one thread is modifying the contents of a List, no other thread can modify the same List object at the same time. Method isEmpty (lines 144–147) is a predicate method that determines whether the list is empty (i.e., the reference to the first node of the list is null). Predicate methods typically test a condition and do not modify the object on which they are called. If the list is empty, method isEmpty returns true; otherwise, it returns false. Method print (lines 150–168) displays the list’s contents. Both isEmpty and print are also synchronized methods.

1 // Fig. 19.4: EmptyListException.java

2 // Class EmptyListException definition

3 package com.deitel.jhtp4.ch19;

4

5 public class EmptyListException extends RuntimeException {

6

Fig. 19.4 Definition of class EmptyListException (part 1 of 2).

7// initialize an EmptyListException

8public EmptyListException( String name )

9{

10super( "The " + name + " is empty" );

11}

12

13 } // end class EmptyListException

Fig. 19.4 Definition of class EmptyListException (part 2 of 2).

1 // Fig. 19.5: ListTest.java

2 // Class ListTest

3

4// Deitel packages

5import com.deitel.jhtp4.ch19.List;

6 import com.deitel.jhtp4.ch19.EmptyListException;

7

8 public class ListTest {

9

10// test class List

11public static void main( String args[] )

12{

13List list = new List(); // create the List container

15// create objects to store in List

16Boolean bool = Boolean.TRUE;

17Character character = new Character( '$' );

18Integer integer = new Integer( 34567 );

19String string = "hello";

20

21// use List insert methods

22list.insertAtFront( bool );

23list.print();

24list.insertAtFront( character );

25list.print();

26list.insertAtBack( integer );

27list.print();

28list.insertAtBack( string );

29list.print();

30

31// use List remove methods

32Object removedObject;

33

34// remove objects from list; print after each removal

35try {

Fig. 19.5 Manipulating a linked list.

54list.print();

55}

56

57// process exception if List is empty when attempt is

58// made to remove an item

59catch ( EmptyListException emptyListException ) {

60emptyListException.printStackTrace();

61}

62

63 } // end method main

64

65 } // end class ListTest

The list is: true

The list is: $ true

The list is: $ true 34567

The list is: $ true 34567 hello

$ removed

The list is: true 34567 hello

true removed

The list is: 34567 hello

hello removed

The list is: 34567

34567 removed Empty list

Fig. 19.5 Manipulating a linked list.

Over the next several pages, we discuss each of the methods of class List (Fig. 19.3) in detail. Method insertAtFront (lines 62–69 of Fig. 19.3) places a new node at the front of the list. The method consists of several steps (Fig. 19.6 illustrates the operation):

1. Call isEmpty to determine whether the list is empty (line 64).

(a)firstNode

7 11

new ListNode

12

(b)firstNode

7 11

new ListNode 12

Fig. 19.6 The insertAtFront operation.

2.If the list is empty, both firstNode and lastNode are set to the ListNode allocated with new and initialized with insertItem (line 65). The ListNode constructor at lines 13–16 calls the ListNode constructor at lines 20–24 to set instance variable data to refer to the insertItem passed as an argument and to set reference nextNode to null.

3.If the list is not empty, the new node is “threaded” (not to be confused with multithreading) or “linked” into the list by setting firstNode to a new ListNode object and initializing that object with insertItem and firstNode (line 68). When the ListNode constructor (lines 20–24) executes, it sets instance variable data to refer to the insertItem passed as an argument and performs the insertion by setting the nextNode reference to the ListNode passed as an argument.

In Fig. 19.6, part (a) shows the list and the new node during the insertAtFront operation and before the program threads the new node into the list. The dotted arrows in part (b) illustrate step 3 of the insertAtFront operation that enables the node containing 12 to become the new list front.

Method insertAtBack (lines 74–82 of Fig. 19.3) places a new node at the back of the list. The method consists of several steps (Fig. 19.7 illustrates the operation):

1.Call isEmpty to determine whether the list is empty (line 76).

2.If the list is empty, both firstNode and lastNode are set to the ListNode allocated with new and initialized with insertItem (line 77). The ListNode constructor at lines 13–16 calls the ListNode constructor at lines 20–24 to set instance variable data to refer to the insertItem passed as an argument and to set reference nextNode to null.

3.If the list is not empty, the new node is threaded into the list by setting LastNode and lastNode.nextNode to the ListNode that was allocated with new and initialized with insertItem (lines 80–81). When the ListNode constructor (lines 13–16) executes, it sets instance variable data to refer to the insertItem passed as an argument and sets reference nextNode to null.

12 7 11 5

Fig. 19.7 A graphical representation of the insertAtBack operation.

In Fig. 19.7, part (a) shows the list and the new node during the insertAtBack operation and before the program threads the new node into the list. The dotted arrows in part (b) illustrate the steps of method insertAtBack that enable a new node to be added to the end of a list that is not empty.

Method removeFromFront (lines 85–106 of Fig. 19.3) removes the front node of the list and returns a reference to the removed data. The method throws an EmptyListException (lines 91–92) if the list is empty when the program calls this method. Otherwise, the method returns a reference to the removed data. The method consists of several steps (illustrated in Fig. 19.8):

1.Assign firstNode.data (the data being removed from the list) to reference removeItem (line 95).

2.If the objects to which firstNode and lastNode refer are equal (line 98), the list has only one element prior to the removal attempt. In this case, the method sets firstNode and lastNode to null (line 99) to “dethread” (remove) the node from the list (leaving the list empty).

3.If the list has more than one node prior to removal, then the method leaves reference lastNode as is and simply assigns firstNode.nextNode to reference firstNode (line 102). Thus, firstNode references the node that was the second node prior to the removeFromFront call.

4.Return the removeItem reference (line 105).

In Fig. 19.8, part (a) illustrates the list before the removal operation. Part (b) shows actual reference manipulations.

12 7 11 5

removeItem

Fig. 19.8 A graphical representation of the removeFromFront operation.

Method removeFromBack (lines 109–141 of Fig. 19.3) removes the last node of a list and returns a reference to the removed data. The method throws an EmptyListException (lines 94 and 95) if the list is empty when the program calls this method. The method consists of several steps (Fig. 19.9 illustrates the operation):

1.Assign lastNode.data (the data being removed from the list) to reference removeItem (line 119).

2.If the objects to which firstNode and lastNode refer are equal (line 122), the list has only one element prior to the removal attempt. In this case, the method sets firstNode and lastNode to null (line 123) to dethread (remove) that node from the list (leaving the list empty).

3.If the list has more than one node prior to removal, then create the ListNode reference current and assign it firstNode.

4.Now “walk the list” with current until it references the node before the last node. The while loop (lines 131–132) assigns current.nextNode to current as long as current.nextNode is not lastNode.

5.After locating the second-to-last node, assign current to lastNode (line 135) to dethread the last node from the list.

6.Set the current.nextNode to null (line 136) to terminate the list at the current node.

7.Return the removeItem reference (liner 140).

In Fig. 19.9, part (a) illustrates the list before the removal operation. Part (b) shows the actual reference manipulations.

12 7 11 5

removeItem

Fig. 19.9 A graphical representation of the removeFromBack operation.

Method print (lines 150–168) first determines whether the list is empty (lines 152– 155). If so, print displays a message indicating that the list is empty and returns control to the calling method. Otherwise, print outputs the data in the list. Line 159 creates ListNode reference current and initializes it with firstNode. While current is not null, there are more items in the list. therefore, line 163 outputs a String representation of current.data. Line 164 moves to the next node in the list by assigning the value of current.nextNode to current. This printing algorithm is identical for linked lists, stacks and queues.

19.5 Stacks

A stack is a constrained version of a linked list—new nodes can be added to a stack and removed from a stack only at the top. For this reason, a stack is referred to as a last-in, firstout (LIFO) data structure. The link member in the bottom (i.e., last) node of the stack is set to null to indicate the bottom of the stack.

Common Programming Error 19.2

Not setting the link in the bottom node of a stack to null is a common logic error.

The primary methods used to manipulate a stack are push and pop. 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.

Stacks have many interesting applications. For example, when a program calls a method, the called method must know how to return to its caller, so the return address of the calling method is pushed onto the program execution stack. If a series of method calls

occurs, the successive return addresses are pushed onto the stack in last-in, first-out order so that each method can return to its caller. Stacks support recursive method calls in the same manner as they do conventional nonrecursive method calls.

The program execution stack contains the memory for local variables on each invocation of a method during a program’s execution. When the method returns to its caller, the memory for that method’s local variables is popped off the stack and those variables are no longer known to the program.

Compilers use stacks to evaluate arithmetic expressions and generate machine language code to process the expressions. The exercises in this chapter explore several applications of stacks, including using them to develop a complete working compiler. The java.util package of the Java API contains class Stack for implementing and manipulating stacks that can grow and shrink during program execution. We will discuss class Stack in Chapter 20.

We take advantage of the close relationship between lists and stacks to implement a stack class by reusing a list class. We demonstrate two different forms of reusability. First, we implement the stack class by extending class List of Fig. 19.3. Then we implement an identically performing stack class through composition by including a List object as a private member of a stack class. The list, stack and queue data structures in this chapter are implemented to store Object references to encourage further reusability. Thus, any object type can be stored in a list, stack or queue.

The application of Fig. 19.10 and Fig. 19.11 creates a stack class by extending class List of Fig. 19.3. We want the stack to have methods push, pop, isEmpty and print. Essentially, these are the methods insertAtFront, removeFromFront, isEmpty and print of class List. Of course, class List contains other methods (such as insertAtBack and removeFromBack) that we would rather not make accessible through the public interface to the stack class. It is important to remember that all methods in the public interface of class List class also are public methods of the subclass StackInheritance (Fig. 19.10). When we implement the stack’s methods, we have each StackInheritance method call the appropriate List method—method push calls insertAtFront and method pop calls removeFromFront. Class StackInheritance is defined as part of package com.deitel.jhtp4.ch19 for reuse purposes. Note that StackInheritance does not import List, because both classes are in the same package.

1 // Fig. 19.10: StackInheritance.java

2// Derived from class List

3 package com.deitel.jhtp4.ch19;

4

5 public class StackInheritance extends List {

6

7// construct stack

8public StackInheritance()

9{

10super( "stack" );

11}

12

Fig. 19.10 Class StackInheritance extends class List (part 1 of 2).

13// add object to stack

14public synchronized void push( Object object )

15{

16insertAtFront( object );

17}

18

19// remove object from stack

20public synchronized Object pop() throws EmptyListException

21{

22return removeFromFront();

23}

24

25 } // end class StackInheritance

Fig. 19.10 Class StackInheritance extends class List (part 2 of 2).

Class StackInheritanceTest’s method main (Fig. 19.11) uses class StackInheritance to instantiate a stack of Objects called stack. The program pushes onto the stack (lines 22, 24, 26 and 28) a Boolean object containing true, a Character object containing $, an Integer object containing 34567 and a String object containing hello, then popped off stack. Lines 37–42 pop the objects from the stack in an infinite while loop. When there are no objects left to pop, an method pop throws an EmptyListException, and the program displays the exception’s stack trace, which shows the methods on the program execution stack at the time the exception occurred. Note that the program uses method print (inherited from List) to output the contents of the stack.

1 // Fig. 19.11: StackInheritanceTest.java

2 // Class StackInheritanceTest

3

4// Deitel packages

5import com.deitel.jhtp4.ch19.StackInheritance;

6 import com.deitel.jhtp4.ch19.EmptyListException;

7

8 public class StackInheritanceTest {

9

10// test class StackInheritance

11public static void main( String args[] )

12{

13StackInheritance stack = new StackInheritance();

15// create objects to store in the stack

16Boolean bool = Boolean.TRUE;

17Character character = new Character( '$' );

18Integer integer = new Integer( 34567 );

19String string = "hello";

20

21// use push method

22stack.push( bool );

23stack.print();

24stack.push( character );

Fig. 19.11 A simple stack program (part 1 of 2).

Another way to implement a stack class is by reusing a list class through composition. The class in Fig. 19.12 uses a private object of class List (line 6) in the definition of class StackComposition. Composition enables us to hide the methods of class List that should not be in our stack’s public interface by providing public interface methods only to the required List methods. This technique of implementing each stack method as a call to a List method is called delegating—the stack method invoked delegates the call to the appropriate List method. In particular, StackComposition delegates calls to List methods insertAtFront, removeFromFront, isEmpty and print. In this example, we do not show class StackCompositionTest, because the only difference in this example is that we change the type of the stack from StackInheritance to StackComposition. If you execute the application from the code on the CD that accompanies this book, you will see that the output is identical.

1// Fig. 19.12: StackComposition.java

2 // Class StackComposition definition with composed List object

3 package com.deitel.jhtp4.ch19;

4

5 public class StackComposition {

6 private List stackList;

7

8// construct stack

9public StackComposition()

10{

11stackList = new List( "stack" );

12}

13

14// add object to stack

15public synchronized void push( Object object )

16{

17stackList.insertAtFront( object );

18}

19

20// remove object from stack

21public synchronized Object pop() throws EmptyListException

22{

23return stackList.removeFromFront();

24}

25

26// determine if stack is empty

27public synchronized boolean isEmpty()

28{

29return stackList.isEmpty();

30}

31

32// output stack contents

33public synchronized void print()

34{

35stackList.print();

36}

37

38 } // end class StackComposition

Fig. 19.12 A simple stack class using composition.

19.6 Queues

Another common data structure is the queue. A queue is similar to a checkout line in a su- permarket—the cashier services the person at the beginning of the line first. Other customers enter the line only at the end and wait for service. Queue nodes are removed only from the head (or front) of the queue and are inserted only at the tail (or end) of the queue. For this reason, a queue is a first-in, first-out (FIFO) data structure. The insert and remove operations are known as enqueue and dequeue.

Queues have many applications in computer systems. Most computers have only a single processor, so only one application at a time can be serviced. Entries for the other applications are placed in a queue. The entry at the front of the queue is the next to receive service. Each entry gradually advances to the front of the queue as applications receive service.

Queues are also used to support print spooling. A multiuser environment may have only a single printer. Many users may send print jobs to the printer. Even when the printer is busy, other people may still send print jobs. These are “spooled” to disk (much as thread is wound onto a spool) where they wait in a queue until the printer becomes available.

Information packets also wait in queues in computer networks. Each time a packet arrives at a network node, it must be routed to the next node on the network along the path to the packet’s final destination. The routing node routes one packet at a time, so additional packets are enqueued until the router can route them.

A file server in a computer network handles file-access requests from many clients throughout the network. Servers have a limited capacity to service requests from clients. When that capacity is exceeded, client requests wait in queues.

The application of Fig. 19.13 and Fig. 19.14 creates a queue by extending class List (Fig. 19.3). We want class QueueInheritance (Fig. 19.13) to have methods enqueue and dequeue, isEmpty and print. Note that these are essentially the List methods insertAtBack and removeFromFront. Of course, class List contains other methods (i.e., insertAtFront and removeFromBack) that we would rather not make accessible through the public interface of the queue. Remember that all methods in the public interface of the List class are also public methods of the subclass QueueInheritance. In the queue’s implementation, each method of class QueueInheritance calls the appropriate List method—method enqueue calls insertAtBack and method dequeue calls removeFromFront. Class QueueInheritance is defined in package com.deitel.jhtp4.ch19 for reuse purposes.

Common Programming Error 19.3

Not setting the link in the last node of a queue to null is a common logic error.

1// Fig. 19.13: QueueInheritance.java

2 // Class QueueInheritance extends class List

3

4// Deitel packages

5 package com.deitel.jhtp4.ch19;

6

7 public class QueueInheritance extends List {

8

Fig. 19.13 Class QueueInheritance extends class List (part 1 of 2).

20

21// use enqueue method

22queue.enqueue( bool );

23queue.print();

24queue.enqueue( character );

25queue.print();

26queue.enqueue( integer );

27queue.print();

28queue.enqueue( string );

29queue.print();

30

31// remove objects from queue

32try {

42}

43}

44

45// process exception if queue empty when item removed

46catch ( EmptyListException emptyListException ) {

47emptyListException.printStackTrace();

48}

49

50 } // end method main

51

52 } // end class QueueInheritanceTest

The queue is: true

The queue is: true $

The queue is: true $ 34567

The queue is: true $ 34567 hello

true dequeued

The queue is: $ 34567 hello

$ dequeued

The queue is: 34567 hello

34567 dequeued

The queue is: hello

hello dequeued Empty queue

(continued on next page)

Fig. 19.14 Processing a queue (part 2 of 3).

Fig. 19.16 A binary search tree containing 12 values.

The application of Fig. 19.17 and Fig. 19.18 creates a binary search tree of integers and traverses it (i.e., walks through all its nodes) three ways—using recursive inorder, preorder and postorder traversals. The program generates 10 random numbers and inserts each into the tree. Class Tree is defined in package com.deitel.jhtp4.ch19 for reuse purposes.

1// Fig. 19.17: Tree.java

2 // Definition of class TreeNode and class Tree.

3

4// Deitel packages

5 package com.deitel.jhtp4.ch19;

6

7 // class TreeNode definition

8 class TreeNode {

9

10// package access members

11TreeNode leftNode;

12int data;

13TreeNode rightNode;

14

15// initialize data and make this a leaf node

16public TreeNode( int nodeData )

17{

18data = nodeData;

19leftNode = rightNode = null; // node has no children

20}

21

22// insert TreeNode into Tree that contains nodes;

23// ignore duplicate values

24public synchronized void insert( int insertValue )

25{

26// insert in left subtree

27if ( insertValue < data ) {

85 if ( node == null )

86 return;

87

88// output node data

89System.out.print( node.data + " " );

91// traverse left subtree

92preorderHelper( node.leftNode );

94// traverse right subtree

95preorderHelper( node.rightNode );

96}

97

98// begin inorder traversal

99public synchronized void inorderTraversal()

100{

101inorderHelper( root );

102}

103

104// recursive method to perform inorder traversal

105private void inorderHelper( TreeNode node )

106{

107if ( node == null )

110// traverse left subtree

111inorderHelper( node.leftNode );

113// output node data

114System.out.print( node.data + " " );

116// traverse right subtree

117inorderHelper( node.rightNode );

118}

119

120// begin postorder traversal

121public synchronized void postorderTraversal()

122{

123postorderHelper( root );

124}

125

126// recursive method to perform postorder traversal

127private void postorderHelper( TreeNode node )

128{

129if ( node == null )

132// traverse left subtree

133postorderHelper( node.leftNode );

135// traverse right subtree

136postorderHelper( node.rightNode );

Fig. 19.17 Definitions of TreeNode and Tree for a binary search tree (part 3 of 4).

37

38 } // end class TreeTest

Inserting the following values: 39 69 94 47 50 72 55 41 97 73

Fig. 19.18 Creating and traversing a binary tree (part 2 of 2).

Class Tree (lines 55–142 of Fig. 19.17) has as private data root—a reference to the root node of the tree. The class contains public method insertNode (lines 67–74) to insert a new node in the tree and public methods preorderTraversal (lines 77– 80), inorderTraversal (lines 99–102) and postorderTraversal (lines 121– 124) to begin traversals of the tree. Each of these methods calls a separate recursive utility method to perform the traversal operations on the internal representation of the tree. The Tree constructor (lines 59–62) initializes root to null to indicate that the tree is empty.

The Tree class’s synchronized method insertNode (lines 67–74) first determines if the tree is empty. If so, it allocates a new TreeNode, initializes the node with the integer being inserted in the tree and assigns the new node to the root reference (line 70). If the tree is not empty, insertNode calls TreeNode method insert (lines 24–52). This method uses recursion to determine the location for the new node in the tree and inserts the node at that location. A node can be inserted only as a leaf node in a binary search tree.

The TreeNode method insert compares the value to insert with the data value in the root node. If the insert value is less than the root node data, the program determines if the left subtree is empty (line 30). If so, line 31 allocates a new TreeNode, initializes it with the integer being inserted and assigns the new node to reference leftNode. Otherwise, line 35 recursively calls insert for the left subtree to insert the value into the left subtree. If the insert value is greater than the root node data, the program determines if the right subtree is empty (line 42). If so, line 43 allocates a new TreeNode, initializes it with the integer being inserted and assigns the new node to reference rightNode. Otherwise, line 47 recursively calls insert for the right subtree to insert the value in the right subtree.

Methods inorderTraversal, preorderTraversal and postorderTraversal call helper methods inorderHelper (lines 105–118), preorderHelper

(lines 83–96) and postorderHelper (lines 127–140), respectively, to traverse the tree (Fig. 19.19) and print the node values. The purpose of the helper methods in class Tree is to allow the programmer to start a traversal without the need to obtain a reference to the root node first, then call the recursive method with that reference. Methods inorderTraversal, preorderTraversal and postorderTraversal simply take the private root reference and pass it to the appropriate helper method to initiate a traversal of the tree.

the same “go left” or “go right” decisions on each comparison as the original value did. Thus, the insertion operation eventually compares the duplicate with a node containing the same value. At this point, the insertion operation might simply discard the duplicate value.

Searching a binary tree for a value that matches a key value is fast, especially for tightly packed trees. In a tightly packed tree, each level contains about twice as many elements as the previous level. Figure 19.19 is a tightly packed binary tree. A binary search tree with n elements has a minimum of log2n levels. Thus, at most log2n comparisons are required either to find a match or to determine that no match exists. Searching a (tightly packed) 1000-element binary search tree requires at most 10 comparisons, because 210 > 1000. Searching a (tightly packed) 1,000,000-element binary search tree requires at most 20 comparisons, because 220 > 1,000,000.

The chapter exercises present algorithms for several other binary tree operations, such as deleting an item from a binary tree, printing a binary tree in a two-dimensional tree format and performing a level-order traversal of a binary tree. The level-order traversal of a binary tree visits the nodes of the tree row-by-row, starting at the root node level. On each level of the tree, a level-order traversal visits the nodes from left to right. Other binary tree exercises include allowing a binary search tree to contain duplicate values, inserting string values in a binary tree and determining how many levels are contained in a binary tree.

SUMMARY

•Dynamic data structures can grow and shrink at execution time.

•Linked lists are collections of data items “lined up in a row”—insertions and deletions can be made anywhere in a linked list.

•Stacks are important in compilers and operating systems—insertions and deletions are made only at one end of a stack, its top.

•Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue and deletions are made from the front (also referred to as the head) of a queue.

•Binary trees facilitate high-speed searching and sorting of data, eliminating duplicate data items efficiently, representing file system directories and compiling expressions into machine language.

•A self-referential class contains a reference that refers to another object of the same class type. Self-referential objects can be linked together to form useful data structures such as lists, queues, stacks and trees.

•Creating and maintaining dynamic data structures requires 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.

•The limit for dynamic memory allocation can be as large as the available physical memory in the computer or the amount of available disk space in a virtual-memory system. Often, the limits are much smaller because the computer’s available memory must be shared among many users.

•Operator new takes as an operand the type of the object being dynamically allocated and returns a reference to a newly created object of that type. If no memory is available, new throws an OutOfMemoryError.

•A linked list is a linear collection (i.e., a sequence) of self-referential class objects, called nodes, connected by reference links.

•A linked list is accessed via a reference to the first node of the list. Each subsequent node is accessed via the link-reference member stored in the previous node.

•By convention, the link reference in the last node of a list is set to null to mark the end of the list.

•A node can contain data of any type, including objects of other classes.

•Trees are nonlinear data structures.

•A linked list is appropriate when the number of data elements to be represented in the data structure is unpredictable. Linked lists are dynamic, so the length of a list can increase or decrease as necessary.

•The size of a “conventional” Java array cannot be altered—the size is fixed at creation time.

•Linked lists can be maintained in sorted order simply by inserting each new element at the proper point in the list.

•List nodes are normally not stored contiguously in memory. Rather, they are logically contiguous.

•Methods that manipulate the contents of a list should be declared synchronized so list objects can be multithread safe when used in a multithreaded program. If one thread is modifying the contents of a list, no other thread is allowed to modify the same list at the same time.

•A stack is a constrained version of a linked list—new nodes can be added to a stack and removed from a stack only at the top. A stack is referred to as a last-in, first-out (LIFO) data structure.

•The primary methods used to manipulate a stack are push and pop. 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 object from the popped node.

•Stacks have many interesting applications. When a method call is made, the called method must know how to return to its caller, so the return address is pushed onto the program execution stack. If a series of method calls occurs, the successive return values are pushed onto the stack in last-in, first-out order so that each method can return to its caller.

•The program execution stack contains the space created for local variables on each invocation of a method. When the method returns to its caller, the space for that method’s local variables is popped off the stack, and those variables are no longer known to the program.

•Stacks are also used by compilers in the process of evaluating arithmetic expressions and generating machine language code to process the expressions.

•The technique of implementing each stack method as a call to a List method is called delegat- ing—the stack method invoked delegates the call to the appropriate List method.

•A queue is a constrained version of a list.

•A queue is similar to a checkout line in a supermarket—the first person in line is serviced first, and other customers enter the line only at the end and wait to be serviced.

•Queue nodes are removed only from the head of the queue and are inserted only at the tail of the queue. For this reason, a queue is referred to as a first-in, first-out (FIFO) data structure.

•The insert and remove operations for a queue are known as enqueue and dequeue.

•Queues have many applications in computer systems. Most computers have only a single processor, so only one user at a time can be serviced. Entries for the other users are placed in a queue. The entry at the front of the queue is the next to receive service. Each entry gradually advances to the front of the queue as users receive service.

•Queues are also used to support print spooling. A multiuser environment might have only a single printer. Many users may be generating outputs to be printed. If the printer is busy, other outputs may still be generated. These are “spooled” to disk (much as thread is wound onto a spool) where they wait in a queue until the printer becomes available.

•Information packets also wait in queues in computer networks. Each time a packet arrives at a network node, it must be routed to the next node on the network along the path to the packet’s final

destination. The routing node routes one packet at a time, so additional packets are enqueued until the router can route them.

•A file server in a computer network handles file-access requests from many clients throughout the network. Servers have a limited capacity to service requests from clients. When that capacity is exceeded, client requests wait in queues.

•A tree is a nonlinear, two-dimensional data structure.

•Tree nodes contain two or more links.

•A binary tree is a tree whose nodes all contain two links. The root node is the first node in a tree.

•Each link in the root node refers to a child. The left child is the first node in the left subtree, and the right child is the first node in the right subtree.

•The children of a node are called siblings. A node with no children is called a leaf node.

•Computer scientists normally draw trees from the root node down.

•A binary search tree (with no duplicate node values) has the characteristic that the values in any left subtree are less than the value in its parent node, and the values in any right subtree are greater than the value in its parent node.

•A node can be inserted only as a leaf node in a binary search tree.

•An inorder traversal of a binary search tree processes the node values in ascending order.

•The process of creating a binary search tree actually sorts the data—and thus this process is called the binary tree sort.

•In a preorder traversal, the value in each node is processed as the node is visited. After the value in a given node is processed, the values in the left subtree are processed, then the values in the right subtree are processed.

•In a postorder traversal, the value in each node is processed after the values of its children.

•The binary search tree facilitates duplicate elimination. As the tree is created, attempts to insert a duplicate value are recognized because a duplicate follows the same “go left” or “go right” decisions on each comparison as the original value did. Thus, the duplicate eventually is compared with a node containing the same value. The duplicate value could simply be discarded at this point.

•Searching a binary tree for a value that matches a key value is also fast, especially for tightly packed trees. In a tightly packed tree, each level contains about twice as many elements as the pre-

vious level. So a binary search tree with n elements has a minimum of log2n levels, and thus at most log2n, comparisons would have to be made either to find a match or to determine that no match exists. Searching a (tightly packed) 1000-element binary search tree requires at most 10 comparisons, because 210 > 1000. Searching a (tightly packed) 1,000,000-element binary search tree requires at most 20 comparisons, because 220 > 1,000,000.

TERMINOLOGY

SELF-REVIEW EXERCISES

19.1Fill in the blanks in each of the following statements:

19.2What are the differences between a linked list and a stack?

19.3What are the differences between a stack and a queue?

19.4Perhaps a more appropriate title for this chapter would have been “Reusable Data Structures.” Comment on how each of the following entities or concepts contributes to the reusability of data structures:

a)classes

b)inheritance

c)composition

19.7Write a program that merges two ordered-list objects of integers into a single ordered list object of integers. Method merge of class ListMerge should receive references to each of the list objects to be merged and should return a reference to the merged list object.

19.8Write a program that inserts 25 random integers from 0 to 100 in order into a linked list object. The program should calculate the sum of the elements and the floating-point average of the elements.

19.9Write a program that creates a linked list object of 10 characters, then creates a second list object containing a copy of the first list, but in reverse order.

19.10Write a program that inputs a line of text and uses a stack object to print the words of the line in reverse order.

19.11Write a program that uses a stack to determine whether a string is a palindrome (i.e., the string is spelled identically backward and forward). The program should ignore spaces and punctuation.

19.12Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code. In this and the next exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses.

Humans generally write expressions like 3 + 4 and 7 / 9 in which the operator (+ or / here) is written between its operands—this is called infix notation. Computers “prefer” postfix notation, in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 + and 7 9 /, respectively.

To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation and evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its operation, and in each algorithm, the stack is used for a different purpose.

In this exercise, you will write a Java version of the infix-to-postfix conversion algorithm. In the next exercise, you will write a Java version of the postfix expression evaluation algorithm. In a later exercise, you will discover that code you write in this exercise can help you implement a complete working compiler.

Write class InfixToPostfixConverter to convert an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers such as

(6 + 2) * 5 - 8 / 4

to a postfix expression. The postfix version of the preceding infix expression is (note that no parenthesis are needed)

6 2 + 5 * 8 4 / -

The program should read the expression into StringBuffer infix and use one of the stack classes implemented in this chapter to help create the postfix expression in StringBuffer postfix. The algorithm for creating a postfix expression is as follows:

a)Push a left parenthesis '(' on the stack.

b)Append a right parenthesis ')' to the end of infix.

c)While the stack is not empty, read infix from left to right and do the following: If the current character in infix is a digit, append it to postfix.

If the current character in infix is a left parenthesis, push it onto the stack. If the current character in infix is an operator:

Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and append the popped operators to postfix.

Push the current character in infix onto the stack.

If the current character in infix is a right parenthesis:

Pop operators from the top of the stack and append them to postfix until a left parenthesis is at the top of the stack.

Pop (and discard) the left parenthesis from the stack.

The following arithmetic operations are allowed in an expression: + addition

- subtraction

* multiplication / division

^ exponentiation % modulus

The stack should be maintained with stack nodes that each contain an instance variable and a reference to the next stack node. Some of the methods you may want to provide are as follows:

a)Method convertToPostfix, which converts the infix expression to postfix notation.

b)Method isOperator, which determines whether c is an operator.

c)Method precedence, which determines if the precedence of operator1 (from the infix expression) is less than, equal to or greater than the precedence of operator2 (from the stack). The method returns true if operator1 has lower precedence than operator2. Otherwise, false is returned.

d)Method stackTop (this should be added to the stack class), which returns the top value of the stack without popping the stack.

19.13Write class PostfixEvaluator, which evaluates a postfix expression (assume it is valid)

such as

6 2 + 5 * 8 4 / -

The program should read a postfix expression consisting of digits and operators into a StringBuffer. Using modified versions of the stack methods implemented earlier in this chapter, the program should scan the expression and evaluate it. The algorithm is as follows:

a)Append a right parenthesis (')') to the end of the postfix expression. When the rightparenthesis character is encountered, no further processing is necessary.

b)When the right-parenthesis character has not been encountered, read the expression from left to right.

If the current character is a digit do the following:

Push its integer value on the stack (the integer value of a digit character is its value in the computer’s character set minus the value of '0' in Unicode).

Otherwise, if the current character is an operator:

Pop the two top elements of the stack into variables x and y. Calculate y operator x.

Push the result of the calculation onto the stack.

c)When the right parenthesis is encountered in the expression, pop the top value of the stack. This is the result of the postfix expression.

[Note: In b) above (based on the sample expression at the beginning of this exercises), if the operator is '/', the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y, evaluate 8 / 2 and push the result, 4, back on the stack. This note also applies to operator '-'.] The arithmetic operations allowed in an expression are:

+ addition

- subtraction

* multiplication / division

^ exponentiation % modulus

The stack should be maintained with one of the stack classes introduced in this chapter. You may want to provide the following methods:

a)Method evaluatePostfixExpression, which evaluates the postfix expression.

b)Method calculate, which evaluates the expression op1 operator op2.

c)Method push, which pushes a value onto the stack.

d)Method pop, which pops a value off the stack.

e)Method isEmpty, which determines whether the stack is empty.

f)Method printStack, which prints the stack.

19.14Modify the postfix evaluator program of Exercise 19.13 so that it can process integer operands larger than 9.

19.15(Supermarket Simulation) Write a program that simulates a checkout line at a supermarket. The line is a queue object. Customers (i.e., customer objects) arrive in random integer intervals of from 1 to 4 minutes. Also, each customer is serviced in random integer intervals of from 1 to 4 minutes. Obviously, the rates need to be balanced. If the average arrival rate is larger than the average service rate, the queue will grow infinitely. Even with “balanced” rates, randomness can still cause long lines. Run the supermarket simulation for a 12-hour day (720 minutes), using the following algorithm:

a)Choose a random integer between 1 and 4 to determine the minute at which the first customer arrives.

b)At the first customer’s arrival time, do the following:

Determine customer’s service time (random integer from 1 to 4). Begin servicing the customer.

Schedule the arrival time of the next customer (random integer 1 to 4 added to the current time).

c)For each minute of the day, consider the following:

If the next customer arrives, proceed as follows: Say so.

Enqueue the customer.

Schedule the arrival time of the next customer.

If service was completed for the last customer, do the following: Say so.

Dequeue next customer to be serviced.

Determine customer’s service completion time (random integer from 1 to 4 added to the current time).

Now run your simulation for 720 minutes and answer each of the following:

a)What is the maximum number of customers in the queue at any time?

b)What is the longest wait any one customer experiences?

c)What happens if the arrival interval is changed from 1 to 4 minutes to 1 to 3 minutes?

19.16Modify the program of Fig. 19.17 and Fig. 19.18 to allow the binary tree to contain duplicates.

19.17Write a program based on the program of Fig. 19.17 and Fig. 19.18 that inputs a line of text, tokenizes the sentence into separate words (you might want to use the StreamTokenizer class from the java.io package), inserts the words in a binary search tree and prints the inorder, preorder and post-order traversals of the tree.

19.18In this chapter, we saw that duplicate elimination is straightforward when creating a binary search tree. Describe how you would perform duplicate elimination when using only a single-sub- scripted array. Compare the performance of array-based duplicate elimination with the performance of binary-search-tree-based duplicate elimination.

19.19Write a method depth that receives a binary tree and determines how many levels it has.

19.20(Recursively Print a List Backwards) Write a method printListBackwards that recursively outputs the items in a linked list object in reverse order. Write a test program that creates a sorted list of integers and prints the list in reverse order.

19.21(Recursively Search a List) Write a method searchList that recursively searches a linked list object for a specified value. Method searchList should return a reference to the value if it is found; otherwise, null should be returned. Use your method in a test program that creates a list of integers. The program should prompt the user for a value to locate in the list.

19.22(Binary Tree Delete) In this exercise, we discuss deleting items from binary search trees. The deletion algorithm is not as straightforward as the insertion algorithm. There are three cases that are encountered when deleting an item—the item is contained in a leaf node (i.e., it has no children), the item is contained in a node that has one child or the item is contained in a node that has two children.

If the item to be deleted is contained in a leaf node, the node is deleted and the reference in the parent node is set to null.

If the item to be deleted is contained in a node with one child, the reference in the parent node is set to reference the child node and the node containing the data item is deleted. This causes the child node to take the place of the deleted node in the tree.

The last case is the most difficult. When a node with two children is deleted, another node in the tree must take its place. However, the reference in the parent node cannot simply be assigned to reference one of the children of the node to be deleted. In most cases, the resulting binary search tree would not adhere to the following characteristic of binary search trees (with no duplicate values):

The values in any left subtree are less than the value in the parent node, and the values in any right subtree are greater than the value in the parent node.

Which node is used as a replacement node to maintain this characteristic? It is either the node containing the largest value in the tree less than the value in the node being deleted, or the node containing the smallest value in the tree greater than the value in the node being deleted. Let us consider the node with the smaller value. In a binary search tree, the largest value less than a parent’s value is located in the left subtree of the parent node and is guaranteed to be contained in the rightmost node of the subtree. This node is located by walking down the left subtree to the right until the reference to the right child of the current node is null. We are now referencing the replacement node, which is either a leaf node or a node with one child to its left. If the replacement node is a leaf node, the steps to perform the deletion are as follows:

a)Store the reference to the node to be deleted in a temporary reference variable.

b)Set the reference in the parent of the node being deleted to reference the replacement node.

c)Set the reference in the parent of the replacement node to null.

d)Set the reference to the right subtree in the replacement node to reference the right subtree of the node to be deleted.

e)Set the reference to the left subtree in the replacement node to reference the left subtree of the node to be deleted.

The deletion steps for a replacement node with a left child are similar to those for a replacement node with no children, but the algorithm also must move the child into the replacement node’s position in the tree. If the replacement node is a node with a left child, the steps to perform the deletion are as follows:

a)Store the reference to the node to be deleted in a temporary reference variable.

b)Set the reference in the parent of the node being deleted to reference the replacement node.

c)Set the reference in the parent of the replacement node reference to the left child of the replacement node.

d)Set the reference to the right subtree in the replacement node reference to the right subtree of the node to be deleted.

e)Set the reference to the left subtree in the replacement node to reference the left subtree of the node to be deleted.

Write method deleteNode, which takes as its argument the value to be deleted. Method deleteNode should locate in the tree the node containing the value to be deleted and use the algorithms discussed here to delete the node. If the value is not found in the tree, the method should print a message that indicates whether the value is deleted. Modify the program of Fig. 19.17 and Fig. 19.18 to use this method. After deleting an item, call the methods inorderTraversal, preorderTraversal and postorderTraversal to confirm that the delete operation was performed correctly.

19.23(Binary Tree Search) Write method binaryTreeSearch, which attempts to locate a specified value in a binary search tree object. The method should take as an argument a search key to be located. If the node containing the search key is found, the method should return a reference to that node; otherwise, the method should return a null reference.

19.24(Level-Order Binary Tree Traversal) The program of Fig. 19.17 and Fig. 19.18 illustrated three recursive methods of traversing a binary tree—inorder, preorder and postorder traversals. This exercise presents the level-order traversal of a binary tree, in which the node values are printed level- by-level, starting at the root node level. The nodes on each level are printed from left to right. The level-order traversal is not a recursive algorithm. It uses a queue object to control the output of the nodes. The algorithm is as follows:

a)Insert the root node in the queue.

b)While there are nodes left in the queue, do the following:

Get the next node in the queue.

Print the node’s value.

If the reference to the left child of the node is not null:

Insert the left child node in the queue.

If the reference to the right child of the node is not null:

Insert the right child node in the queue.

Write method levelOrder to perform a level-order traversal of a binary tree object. Modify the program of Fig. 19.17 and Fig. 19.18 to use this method. [Note: You will also need to use queueprocessing methods of Fig. 19.13 in this program.]

19.25 (Printing Trees) Write a recursive method outputTree to display a binary tree object on the screen. The method should output the tree row-by-row, with the top of the tree at the left of the screen and the bottom of the tree toward the right of the screen. Each row is output vertically. For example, the binary tree illustrated in Fig. 19.20 is output as shown in Fig. 19.21.

Note that the rightmost leaf node appears at the top of the output in the rightmost column and the root node appears at the left of the output. Each column of output starts five spaces to the right of the preceding column. Method outputTree should receive an argument totalSpaces representing the number of spaces preceding the value to be output. (This variable should start at zero so the root node is output at the left of the screen.) The method uses a modified inorder traversal to output the tree—it starts at the rightmost node in the tree and works back to the left. The algorithm is as follows:

While the reference to the current node is not null, perform the following: Recursively call outputTree with the right subtree of the current node and

totalSpaces + 5.

Use a for structure to count from 1 to totalSpaces and output spaces. Output the value in the current node.

Set the reference to the current node to refer to the left subtree of the current node. Increment totalSpaces by 5.

19.27 (Building A Compiler; Prerequisite: Complete Exercise 7.42, Exercise 7.43, Exercise 19.12, Exercise 19.13 and Exercise 19.26) Now that the Simple language has been presented (Exercise 19.26), we discuss how to build a Simple compiler. First, we consider the process by which a Simple program is converted to SML and executed by the Simpletron simulator (see Fig. 19.26). A file containing a Simple program is read by the compiler and converted to SML code. The SML code is output to a file on disk, in which SML instructions appear one per line. The SML file is then loaded into the Simpletron simulator, and the results are sent to a file on disk and to the screen. Note that the Simpletron program developed in Exercise 7.43 took its input from the keyboard. It must be modified to read from a file so it can run the programs produced by our compiler.

The Simple compiler performs two passes of the Simple program to convert it to SML. The first pass constructs a symbol table (object) in which every line number (object), variable name (object) and constant (object) of the Simple program is stored with its type and corresponding location in the final SML code (the symbol table is discussed in detail below). The first pass also produces the corresponding SML instruction object(s) for each of the Simple statements (object, etc.). If the Simple program contains statements that transfer control to a line later in the program, the first pass results in an SML program containing some “unfinished” instructions. The second pass of the compiler locates and completes the unfinished instructions and outputs the SML program to a file.

First Pass

The compiler begins by reading one statement of the Simple program into memory. The line must be separated into its individual tokens (i.e., “pieces” of a statement) for processing and compilation. (The StreamTokenizer class from the java.io package can be used.) Recall that every statement begins with a line number followed by a command. As the compiler breaks a statement into tokens, if the token is a line number, a variable or a constant, it is placed in the symbol table. A line number is placed in the symbol table only if it is the first token in a statement. The symbolTable object is an array of tableEntry objects representing each symbol in the program. There is no restriction on the number of symbols that can appear in the program. Therefore, the symbolTable for a particular program could be large. Make the symbolTable a 100-element array for now. You can increase or decrease its size once the program is working.

Each tableEntry object contains three members. Member symbol is an integer containing the Unicode representation of a variable (remember that variable names are single characters), a line number or a constant. Member type is one of the following characters indicating the symbol’s type: 'C' for constant, 'L' for line number or 'V' for variable. Member location contains the Simpletron memory location (00 to 99) to which the symbol refers. Simpletron memory is an array of 100 integers in which SML instructions and data are stored. For a line number, the location is the element in the Simpletron memory array at which the SML instructions for the Simple statement begin. For a variable or constant, the location is the element in the Simpletron memory array in which the variable or constant is stored. Variables and constants are allocated from the end of Simpletron’s memory backwards. The first variable or constant is stored at location 99, the next at location 98, etc.

The symbol table plays an integral part in converting Simple programs to SML. We learned in Chapter 7 that an SML instruction is a four-digit integer comprised of two parts—the operation code and the operand. The operation code is determined by commands in Simple. For example, the simple command input corresponds to SML operation code 10 (read), and the Simple command print corresponds to SML operation code 11 (write). The operand is a memory location containing the data on which the operation code performs its task (e.g., operation code 10 reads a value from the keyboard and stores it in the memory location specified by the operand). The compiler searches symbolTable to determine the Simpletron memory location for each symbol, so the corresponding location can be used to complete the SML instructions.

Fig. 19.27 SML instructions produced after the compiler’s first pass (part 2 of 2).