Transcript Chapter 4 – Control Structures Part 1

1
Chapter 25 – Data Structures
Outline
25.1 Introduction
25.2 Simple-Type structs, Boxing and Unboxing
25.3 Self-Referential Classes
25.4 Linked Lists
25.5 Stacks
25.6 Queues
25.7 Trees
25.7.1 Binary Search Tree of Integer Values
25.7.2 Binary Search Tree of IComparable Objects
Many slides modified by Prof. L. Lilien
(even many without an explicit message).
 2002 Prentice Hall. All rights reserved.
Slides added by L.Lilien are © 2006 Leszek T. Lilien.
Permision to use for non-commercial purposes slides added by
L.Lilien’s will be gladly granted upon a written (e.g., emailed)
request.
2
25.1 Introduction
• Dynamic data structures
– Grow and shrink at execution time
– Linked Lists:
• “Lined up in a row”
• Insertions and removals can occur anywhere in the list
– Stacks:
• Insertions and removals only at top
– Push and pop
– Queues:
• Insertions made at back, removals from front
– Trees, including binary trees:
• Facilitate high-speed searching and sorting of data
• Efficient elimination of duplicate items
 2002 Prentice Hall. All rights reserved.
3
25.2 Simple-Type structs, Boxing and Unboxing
• Data structures can store:
– Simple-type values
– Reference-type values
• There are mechanisms that enable manipulation of simple-type
values as objects
– Discussed below
 2002 Prentice Hall. All rights reserved.
Simple-Type structs
• Recall: Each simple type (int, char, …) has a corresponding
struct in namespace System that declares this simple type
We have structs:
– Boolean, Byte, Sbyte, Char, Decimal, Double,
Single, Int32, UInt32, Int64, UInt64, Int16,
UInt16
• Simple types are just aliases for these corresponding structs
– So a variable can be declared:
EITHER using the keyword for that simple type
OR the struct name
• E.g., int (keyword) and Int32 (struct name) are interchangeable
– Methods related to a simple type are located in the corresponding struct
• E.g. method Parse –converting string to int value– is located in struct
In32
 2002 Prentice Hall. All rights reserved.
4
Boxing Conversions
• All simple-type structs inherit from class ValueType in
namespace System
In turn, class ValueType inherits from class object
=> Any simple-type value can be assigned to an object
variable
• Such an assignment is named a Boxing conversions
– In Boxing conversion simple-type value is copied into an object
=> after Boxing conversion , a simple-type value can be manipulated
as an object
 2002 Prentice Hall. All rights reserved.
5
Boxing Conversions
• Boxing conversions can be explicit or implicit
int i = 5; // create an int value
object obj1 = ( object) i; // explicitly box the int value
object obj2 = i; // implicitly box the int value
– Now obj1 and obj2 refer to 2 different objects!
• Both objects include a copy of the integer value from the int variable i
 2002 Prentice Hall. All rights reserved.
6
Unboxing Conversions
7
• Unboxing conversions — used for explicit conversion of an object
reference to a simple value
int int1 = ( int ) obj1; // explicitly unbox the int value
// that was boxed within obj1
• Attempts to unbox an object reference that does not refer to a
correct simple value causes InvalidCastException
• We’ll see later(Ch. 27) how so called “generics” eliminate the
overhead of boxing/unboxing
 2002 Prentice Hall. All rights reserved.
8
25.3 Self-Referential Classes
• Self-Referential Class
– Contains a reference member to an object of the same class type
• E.g.: class Node
{
private int data;
private Node next; // self-reference to node
…
}
• Reference can be used to link objects of the same type together
• Dynamic data structures require dynamic memory
allocation
– Ability to obtain memory when needed
– Release memory when not needed any more
– Uses new operator
• Ex: Node nodeToAdd = new Node(10);
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Node
{
private int data;
private Node next;
// self-reference
public Node( int d )
{
/* constructor body */
}
Reference to object of
same type
9
25.3 SelfReferential
Class
public int Data
{
get
{
/* get body */
}
set
{
/* set body */
}
}
public Node Next
{
get
{
/* get body */
}
set
{
/* set body */
}
}
Fig. 23.1 Sample
self-referential Node
class definition (part 1)
}
 2002 Prentice Hall. All rights reserved.
Slide merged with next by L. Lilien
10
25.3 Self-Referential Class
data
15
next
data
next
10
Fig. 23.2 Two self-referential class objects (nodes) linked together.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
11
25.4 Linked Lists
• Linked List:
– Linear collection of self-referential nodes connected by links
• Nodes: class objects of linked-lists
• Programs access linked lists through a reference to first node
– Subsequent nodes accessed by link-reference members
– Last node’s link set to null to indicate end of list
• Nodes can hold data of any type
• Nodes created dynamically
reference to first node
lastNode
(with null link)
firstNode
H
 2002 Prentice Hall. All rights reserved.
e
……
o
Slide modified by L. Lilien
12
25.4 Linked Lists
firstNode reference
H
lastNode refernce
D
……
Q
Fig. 23.3 A graphical representation of a linked list (with an
optional reference to the last node).
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
13
25.4 Linked Lists
• Linked lists - similar to arrays
However:
• Arrays are a fixed size
• Linked lists have no limit to size
– More nodes can be added as program executes
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
14
25.4 Linked Lists - InsertAtFront
firstNode
(a)
7
11
new ListNode
12
firstNode
(b)
7
11
new ListNode
12
Changed links
Unchanged links
Fig. 23.6 A graphical representation of the InsertAtFront operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
15
25.4 Linked Lists - InsertAtBack
(a)
firtNode
12
(b)
lastNode
7
firstNode
12
11
lastNode
7
Changed links
New ListNode
11
5
New ListNode
5
Unchanged links
Fig. 23.7 A graphical representation of the InsertAtBack operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
16
25.4 Linked Lists - RemoveFromFront
(a)
firstNode
12
(b)
lastNode
7
11
firstNode
12
5
lastNode
7
11
5
removeItem
Changed links
Unchanged links
Fig. 23.8 A graphical representation of the RemoveFromFront operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
17
25.4 Linked Lists - RemoveFromBack
(a)
firstNode
12
(b)
lastNode
7
11
firstNode
12
5
lastNode
7
11
5
removeItem
Changed links
Unchanged links
Fig. 23.9 A graphical representation of the RemoveFromBack operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Outline
// Fig. 23.4: LinkedListLibrary.cs
// Class ListNode and class List definitions.
using System;
namespace LinkedListLibrary
// create library
{
// class to represent one node in a list
class ListNode
{
Reference
to next
private object data;
// any object
can be
within a list node
private ListNode next; // self-referential
member
ListNode in linked
listvariable
LinkedListLibrar
y.cs
// constructor to create ListNode that refers to dataValue
// and is last node in list (added to the end of the list)
public ListNode( object dataValue )
Constructor for first item in list
: this( dataValue, null ) // calls constructor below
{
Invoke normal constructor,
}
which will set data to
// constructor to create ListNode that refers to dataValue
dataValue and next to null
// and refers to next ListNode in List (added to any list
// position other than the last one)
public ListNode( object dataValue, ListNode nextNode )
{
Constructor to set
data = dataValue;
data and next values
next = nextNode;
}
to parameter values
// property Next
public ListNode Next
{
get
{
return next;
}
Accessor method so a List
can access next member
variable
 2002 Prentice Hall.
All rights reserved.
19
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
Outline
set
{
next = value;
LinkedListLibrar
y.cs
}
}
// property Data
public object Data
{
get
{
return data;
}
}
Accessor method so a List can
access data member variable
} // end class ListNode
Reference to first
// class List definition
public class List
node in list
{
private ListNode firstNode;
private ListNode lastNode;
Reference to last
private string name;
// string like
"list"
node
in listto display
// construct empty List with specified name
public List( string listName )
{
name = listName;
Set reference to first
firstNode = lastNode = null;
and last nodes to null
}
 2002 Prentice Hall.
All rights reserved.
20
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// construct empty List with "list" as its name
public List() : this( "list" ) // uses previous constructor
{
}
Outline
LinkedListLibrar
y.cs
// Insert object at front of List. If List is empty,
// firstNode and lastNode will refer to same object.
// Otherwise, firstNode refers to new node.
public void InsertAtFront( object insertItem )
{
Method to insert an
lock ( this ) // ignore-needed in multithreaded environment
object at the front of
{
Get list lock
if ( IsEmpty() )
// defined in Line 163 belowthe list
firstNode = lastNode =
Test if list is empty
new ListNode( insertItem );
else
If list is empty, create new
firstNode =
new ListNode( insertItem, firstNode );node and set firstNode
}
and lastNode to refer to it
}
If list is not empty, insert
// Insert object at end of List. If List is empty,
// firstNode and lastNode will refer to same object. object by setting its next
// Otherwise, lastNode's Next property refers to new node.
reference to the first node
public void InsertAtBack( object insertItem )
{
Method to insert object
lock ( this ) // ignore-needed in multithreaded environment
into back of list
{
Get163
list below
lock
if ( IsEmpty() )
// defined in Line
firstNode = lastNode =
Test if list is empty
new ListNode( insertItem );
If list is empty create a new
node and set firstNode and
lastNode to reference it 2002 Prentice Hall.
All rights reserved.
21
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
Outline
else
lastNode = lastNode.Next =
new ListNode( insertItem );
If list is not empty, create a new
node and set the last node’s next
LinkedListLibrar
reference to the new node
y.cs
}
}
// remove first node from List
public object RemoveFromFront()
{
Method to remove an
lock ( this ) // ignore-needed in multithreaded environ.
from the front of list
{
object removeItem = null;
object
Get lock
if ( IsEmpty() )
// defined in Line 163 below
Throw
throw new EmptyListException( name );
exception
if list is empy
removeItem = firstNode.Data;
// retrieve data
// reset firstNode and lastNode references
if ( firstNode == lastNode )
firstNode = lastNode = null;
else
firstNode = firstNode.Next;
return removeItem;
}
}
Set removeItem equal
to data in first node
If there is only one node in the
list, set firstNode and lastNode
references to null
// return removed data
If there is more then one
node, set firstNode to
reference the second node
Return data
// remove last node from List
public object RemoveFromBack()
stored in node
{
lock ( this ) // ignore-needed in multithreaded environ.
Method to remove an object
{
from the back of the list
object removeItem = null;
 2002 Prentice Hall.
All rights reserved.
22
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
Outline
if ( IsEmpty() )
throw new EmptyListException( name );
removeItem = lastNode.Data;
LinkedListLibrar
Set removeItemy.cs
equal to
the data in the last node
// retrieve data
// reset firstNode and lastNode references
if ( firstNode == lastNode ) // only one node in list
firstNode = lastNode = null;
If there is only one
node, set firstNode
and lastNode to refer to null
else
{ // walk the list until current precedes lastNode
ListNode current = firstNode;
// loop while current node is not lastNode
Loop until next to
while ( current.Next != lastNode )
current = current.Next;
// move to next node
last node is reached
// current is now node next to the last
// make current new lastNode
Set lastNode to refer
lastNode = current;
current.Next = null;
to the next to last node
}
return removeItem;
}
}
// return
Set reference of new
lastdata
node to null
removed
Return data of old last node
// return true if List is empty
public bool IsEmpty()
{
Method to test if list is empty
lock ( this ) // ignore-needed in multithreaded environment
{
return firstNode == null; // checks if firstNode == null
}
}
 2002 Prentice Hall.
All rights reserved.
23
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
// output List contents
virtual public void Print()
Method to output the list
{
lock ( this ) // ignore-needed in multithreaded environ.
{
if ( IsEmpty() ) // defined in Line 163 above
{
Console.WriteLine( "Empty " + name );
Tell user
return;
}
Outline
LinkedListLibrar
y.cs
if list is empty
Console.Write( "The " + name + " is: " );
ListNode current = firstNode;
// output current node data while not at end of list
while ( current != null )
{
Console.Write( current.Data + " " );
current = current.Next;
Output
}
data in list
Console.WriteLine( "\n" );
}
}
} // end class List
 2002 Prentice Hall.
All rights reserved.
24
199
200
201
202
203
204
205
206
207
208
209
Outline
// class EmptyListException definition
public class EmptyListException : ApplicationException
{
public EmptyListException( string name )
LinkedListLibrar
Handles illegal operations
: base( "The " + name + " is empty" )
{
on an empty list y.cs
}
} // end class EmptyListException
} // end namespace LinkedListLibrary
 2002 Prentice Hall.
All rights reserved.
25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Outline
// Fig 23.5: ListTest.cs
// Testing class List.
using System;
using LinkedListLibrary;
ListTest.cs
// library we created
namespace ListTest
{
// class to test List class functionality
class ListTest
{
static void Main( string[] args )
{
List list = new List(); // create List container
// create data to store in List
bool aBoolean = true;
char aCharacter = '$';
int anInteger = 34567;
string aString = "hello";
// use List insert methods
list.InsertAtFront( aBoolean );
list.Print();
list.InsertAtFront( aCharacter );
list.Print();
list.InsertAtBack( anInteger );
list.Print();
list.InsertAtBack( aString );
list.Print();
// use List remove methods
object removedObject;
Create list of objects
Create data to put in list
Insert objects at beginning
of listinto list using
InsertAtFront method
Insert objects at end of
listinto list using
InsertAtBack method
Print the list
 2002 Prentice Hall.
All rights reserved.
26
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// remove data from list and print after each removal
try
{
removedObject = list.RemoveFromFront();
Console.WriteLine( removedObject + " removed" );
list.Print();
removedObject = list.RemoveFromFront();
Console.WriteLine( removedObject + " removed" );
list.Print();
removedObject = list.RemoveFromBack();
Console.WriteLine( removedObject + " removed" );
list.Print();
removedObject = list.RemoveFromBack();
Console.WriteLine( removedObject + " removed" );
list.Print();
Outline
ListTest.cs
Remove objects from
front of list using method
RemoveFromFront
Print the list after
each remove
Remove objects from
back of list using method
RemoveFromBack
}
// process exception if list empty when attempt is
// made to remove item
catch ( EmptyListException emptyListException )
{
Console.Error.WriteLine( "\n" + emptyListException );
}
If remove is called on
an empty list tell user
} // end method Main
} // end class ListTest
}
 2002 Prentice Hall.
All rights reserved.
27
The list is: True
Outline
The list is: $ True
The list is: $ True 34567
ListTest.cs
Program Output
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
 2002 Prentice Hall.
All rights reserved.
We have already seen this and next 3 slides
- Review yourself if needed
25.4 Linked Lists - InsertAtFront
28
firstNode
(a)
7
11
new ListNode
12
firstNode
(b)
7
11
new ListNode
12
Changed links
Unchanged links
Fig. 23.6 A graphical representation of the InsertAtFront operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
29
25.4 Linked Lists - InsertAtBack
(a)
firtNode
12
(b)
lastNode
7
firstNode
12
11
lastNode
7
Changed links
New ListNode
11
5
New ListNode
5
Unchanged links
Fig. 23.7 A graphical representation of the InsertAtBack operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
30
25.4 Linked Lists - RemoveFromFront
(a)
firstNode
12
(b)
lastNode
7
11
firstNode
12
5
lastNode
7
11
5
removeItem
Changed links
Unchanged links
Fig. 23.8 A graphical representation of the RemoveFromFront operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
31
25.4 Linked Lists - RemoveFromBack
(a)
firstNode
12
(b)
lastNode
7
11
firstNode
12
5
lastNode
7
11
5
removeItem
Changed links
Unchanged links
Fig. 23.9 A graphical representation of the RemoveFromBack operation.
 2002 Prentice Hall. All rights reserved.
Slide modified by L. Lilien
32
25.5 Stacks
• Stack – a special version of a linked list:
– Last-in, first-out (LIFO) data structure:
• Takes and releases new nodes only at top
• Operations:
– Push: adds new entry (node) to top of stack
– Pop: removes top entry (node) from stack
• Can be used for:
– Storing return addresses
– Storing local variables
– …
 2002 Prentice Hall. All rights reserved.
33
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Outline
// Fig. 23.10: StackInheritanceLibrary.cs
// Implementing a stack by inheriting from class List.
using System;
using LinkedListLibrary;
StackInheritance
Library.cs
namespace StackInheritanceLibrary
{
// class StackInheritance inherits class List's capabilities
public class StackInheritance : List
StackInheritance class is
{
// pass name "stack" to List constructor
derived from List class
public StackInheritance() : base( "stack" )
{
}
// place dataValue at top of stack by inserting
// dataValue at front of linked list
public void Push( object dataValue )
{
Call InsertAtFront method
InsertAtFront( dataValue );
of List class to push objects
}
// remove item from top of stack by removing
// item at front of linked list
public object Pop()
{
return RemoveFromFront();
}
Call RemoveFromFront method
of List class to pop objects
} // end class StackInheritance
}
 2002 Prentice Hall.
All rights reserved.
34
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Outline
// Fig. 23.11: StackInheritanceTest.cs
// Testing class StackInheritance.
using System;
using StackInheritanceLibrary;
using LinkedListLibrary;
StackInheritance
Test.cs
namespace StackInheritanceTest
{
// demonstrate functionality of class StackInheritance
class StackInheritanceTest
{
static void Main( string[] args )
{
StackInheritance stack = new StackInheritance();
// create objects to store in the stack
bool aBoolean = true;
char aCharacter = '$';
Create objects
int anInteger = 34567;
store in stack
string aString = "hello";
// use method Push to add items to stack
stack.Push( aBoolean );
stack.Print();
stack.Push( aCharacter );
stack.Print();
stack.Push( anInteger );
stack.Print();
stack.Push( aString );
stack.Print();
Create stack
to
Push objects onto the stack
Print stack after each push
// use method Pop to remove items from stack
object removedObject = null;
 2002 Prentice Hall.
All rights reserved.
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// remove items from stack
try
{
while ( true )
{
removedObject = stack.Pop();
Console.WriteLine( removedObject + " popped" );
stack.Print();
}
}
// if exception occurs, print stack trace
catch ( EmptyListException emptyListException )
{
Console.Error.WriteLine(
emptyListException.StackTrace );
}
Outline
StackInheritance
Test.cs
Remove
objects
from stack
Empty stack
exception
} // end method Main
} // end class StackInheritanceTest
}
 2002 Prentice Hall.
All rights reserved.
36
The stack is: True
Outline
The stack is: $ True
The stack is: 34567 $ True
The stack is: hello 34567 $ True
StackInheritance
Test.cs
Program Output
hello popped
The stack is: 34567 $ True
34567 popped
The stack is: $ True
$ popped
The stack is: True
True popped
Empty stack
at LinkedListLibrary.List.RemoveFromFront()
in z:\ch24\linkedlistlibrary\linkedlistlibrary.cs:line 114
at StackInheritanceLibrary.StackInheritance.Pop()
in z:\ch24\stackinheritancelibrary\
stackinheritancelibrary.cs:line 28
at StackInheritanceTest.StackInheritanceTest.Main(String[] args
in z:\ch24\fig24_11\stackinheritancetest.cs:line 41
Line 144 - Slide 16
 2002 Prentice Hall.
All rights reserved.
37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Fig. 23.12: StackCompositionLibrary.cs
// StackComposition definition with composed List object.
// (no inheritance here!)
using System;
using LinkedListLibrary;
Outline
StackComposition
Library.cs
namespace StackCompositionLibrary
{
// class StackComposition encapsulates List's capabilities
public class StackComposition
{
Create List object
private List stack;
// construct empty stack
public StackComposition()
{
stack = new List( "stack" );
}
// add object to stack
public void Push( object dataValue )
{
stack.InsertAtFront( dataValue );
}
// remove object from stack
public object Pop()
{
return stack.RemoveFromFront();
}
Call method
InsertAtFront to push
Use method
RemoveFromFront
to pop
 2002 Prentice Hall.
All rights reserved.
38
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// determine whether stack is empty
public bool IsEmpty()
{
return stack.IsEmpty();
Call
}
is empty to see
if list has nodes
// output stack contents
public void Print()
{
stack.Print();
}
Outline
StackComposition
Library.cs
Call method Print
for output
} // end class StackComposition
}
 2002 Prentice Hall.
All rights reserved.
39
25.6 Queues
• Queue:
First-in, first-out (FIFO) data structure
– Nodes added to tail, removed from head
• Operations:
– Enqueue: insert node at the end
– Dequeue: remove node from the front
• Many computer applications:
– Printer spooling
– Information packets on networks
– …
 2002 Prentice Hall. All rights reserved.
40
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Outline
// Fig. 23.13: QueueInheritanceLibrary.cs
// Implementing a queue by inheriting from class List.
using System;
using LinkedListLibrary;
QueueInheritance
Library.cs
namespace QueueInheritanceLibrary
{
// class QueueInheritance inherits List's capabilities
public class QueueInheritance : List
{
Class QueueInheritance
// pass name "queue" to List constructor
public QueueInheritance() : base( "queue" )
derives from class List
{
}
// place dataValue at end of queue by inserting
// dataValue at end of linked list
public void Enqueue( object dataValue )
Call InsertAtBack
{
InsertAtBack( dataValue );
to enqueue
}
// remove item from front of queue by removing
// item at front of linked list
public object Dequeue( )
{
return RemoveFromFront();
Call RemoveFromFront
}
to dequeue
} // end of QueueInheritance
}
 2002 Prentice Hall.
All rights reserved.
41
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Outline
// Fig. 23.14: QueueTest.cs
// Testing class QueueInheritance.
using System;
using QueueInheritanceLibrary;
using LinkedListLibrary;
QueueTest.cs
namespace QueueTest
{
// demonstrate functionality of class QueueInheritance
class QueueTest
{
static void Main( string[] args )
{
QueueInheritance queue = new QueueInheritance();
// create objects to store in the stack
bool aBoolean = true;
char aCharacter = '$';
int anInteger = 34567;
string aString = "hello";
Create queue
Create objects to be
inserted into queue
// use method Enqueue to add items to queue
queue.Enqueue( aBoolean );
queue.Print();
Enqueue objects
queue.Enqueue( aCharacter );
queue.Print();
queue.Enqueue( anInteger );
Print queue after
queue.Print();
each enqueue
queue.Enqueue( aString );
queue.Print();
// use method Dequeue to remove items from queue
object removedObject = null;
 2002 Prentice Hall.
All rights reserved.
42
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// remove items from queue
try
{
while ( true )
{
removedObject = queue.Dequeue();
Console.WriteLine( removedObject + " dequeue" );
queue.Print();
}
Print queue after
}
Outline
QueueTest.cs
Dequeue objects
each enqueue
// if exception occurs, print stack trace
catch ( EmptyListException emptyListException )
{
Console.Error.WriteLine(
emptyListException.StackTrace );
}
} // end method Main
} // end class QueueTest
}
 2002 Prentice Hall.
All rights reserved.
43
The queue is: True
Outline
The queue is: True $
The queue is: True $ 34567
QueueTest.cs
Program Output
The queue is: True $ 34567 hello
True dequeue
The queue is: $ 34567 hello
$ dequeue
The queue is: 34567 hello
34567 dequeue
The queue is: hello
hello dequeue
Empty queue
at LinkedListLibrary.List.RemoveFromFront()
in z:\ch24\linkedlistlibrary\linkedlistlibrary.cs:line 114
at QueueInheritanceLibrary.QueueInheritance.Dequeue()
in z:\ch24\queueinheritancelibrary\
queueinheritancelibrary.cs:line 28
at QueueTest.QueueTest.Main(String[] args)
in z:\ch24\fig24_13\queuetest.cs:line 41
 2002 Prentice Hall.
All rights reserved.
44
25.7 Trees
• Tree: non-linear, two-dimensional data structure
• Binary tree:
– Each node contains data & two links (hence “binary in the name): left link
and right link
B
– Root node: “top” node in a tree
• Links refer to child nodes
– Leaf node: node with no children
X
A
Y
 2002 Prentice Hall. All rights reserved.
45
25.7 Trees
• Binary search tree:
– Values in left subtree are less than the value of the subtree’s
parent
– Values in right subtree are greater than the value of the
subtree’s parent
47
J
25
A
77
P
11
M
 2002 Prentice Hall. All rights reserved.
43
65
93
46
25.7.1 Binary Search Tree of Integer Values
• Traversal: method of retrieving data from a tree
– In these methods if there is a subtree, recursively the
traversal is called recursively
• Kinds of traversals:
– Inorder traversal:
• Get data from left subtree/child of node
• Get data from node
• Get data from right subtree/child of node
25
• Example (figure)
Inorder traversal:
11 25 43 47 65 77 93
 2002 Prentice Hall. All rights reserved.
47
11
77
43
65
93
25.7.1 Binary Search
Tree of Integer Values
– Preorder traversal:
•
•
•
•
25
11
Get data from node
Get data from left subtree/child of node
Get data from right subtree/child of node
Example: 47 25 11 43 77 65 93
77
43
– Postorder traversal
•
•
•
•
Get data from left subtree/child of node
Get data from right subtree/child of node
Get data from node
Example: 11 43 25 65 93 77 47
– Level-order traversal
• Visit nodes of tree row by row, from left to right
• Example: 47 25 77 11 43 65 93
 2002 Prentice Hall. All rights reserved.
47
47
65
93
48
25.7 Trees
Reference to the tree
B
A
D
C
Fig. 23.15 A graphical representation of a binary tree.
 2002 Prentice Hall. All rights reserved.
49
25.7 Trees
47
25
77
11
7
43
17
31
65
44
93
68
Fig. 23.16 A binary search tree containing 12 values.
 2002 Prentice Hall. All rights reserved.
50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Outline
// Fig. 23.17: BinaryTreeLibrary.cs
// Definition of class TreeNode and class Tree.
using System;
namespace BinaryTreeLibrary
{
// class TreeNode definition
class TreeNode
{
private TreeNode leftNode;
private int data;
private TreeNode rightNode;
BinaryTreeLibrar
y.cs
Left and right subtree references
Data stored in node
// initialize data and make this a leaf node
public TreeNode( int nodeData )
{
data = nodeData;
leftNode = rightNode = null; // node has no children
}
// LeftNode property
public TreeNode LeftNode
{
get
{
return leftNode;
}
Since new nodes are leaf, set
subtree references to null
Accessor methods
for left subtree
set
{
leftNode = value;
}
}
 2002 Prentice Hall.
All rights reserved.
51
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Data property
public int Data
{
get
{
return data;
}
Outline
Accessor methods
for nodes data
BinaryTreeLibrar
y.cs
set
{
data = value;
}
}
// RightNode property
public TreeNode RightNode
{
get
{
return rightNode;
}
Accessor methods
for right subtree
set
{
rightNode = value;
}
}
 2002 Prentice Hall.
All rights reserved.
52
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
Outline
// insert TreeNode into Binary Search Tree containing nodes;
// ignore duplicate values
public void Insert( int insertValue )
Method to determine
{
location of new BinaryTreeLibrar
node
// insert in left subtree
y.cs
if ( insertValue < data )
{
// insert new TreeNode
If value of new node is less than
if ( leftNode == null )
root, and the left subtree is empty,
leftNode = new TreeNode( insertValue );
insert node as left child of root
// continue traversing left subtree
else
leftNode.Insert( insertValue );
}
// insert in right subtree
else if ( insertValue > data )
{
// insert new TreeNode
if ( rightNode == null )
rightNode = new TreeNode( insertValue );
If left subtree is not empty,
recursively call Insert to determine
location of new node in subtree
// continue traversing right subtree
else
rightNode.Insert( insertValue );
}
}
}
// ignore if insertValue == data (duplicate value)
// end method Insert
// end class TreeNode
If value of new node is
greater than root, and the
right subtree is empty, insert
node as right child of root
If right subtree is not empty,
recursively call Insert to
determine location of new
node in subtree
 2002 Prentice Hall.
All rights reserved.
53
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// class Tree definition
public class Tree
{
private TreeNode root;
Outline
Reference to root of tree
BinaryTreeLibrar
y.cs
// construct an empty Tree of integers
public Tree()
{
Set root to null when
root = null;
}
tree first created
// Insert a new node in the binary search tree.
// If the root node is null, create the root node here.
// Otherwise, call the insert method of class TreeNode.
public void InsertNode( int insertValue )
Method to insert a
{
lock ( this )
// ignore locks
new node into tree
{
if ( root == null )
root = new TreeNode( insertValue );
If tree is empty insert
new node as root
else
root.Insert( insertValue ); // see l.67
}
}
// begin preorder traversal
public void PreorderTraversal()
{
lock ( this )
{
PreorderHelper( root );
}
}
If tree is not empty call
Insert to determine
location of new node
Perform preorder traversal
Call PreorderHelper to
help perform traversal
 2002 Prentice Hall.
All rights reserved.
54
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// recursive method to perform preorder traversal
private void PreorderHelper( TreeNode node )
{
if ( node == null )
return;
// output data from this node
Console.Write( node.Data + " " );
// traverse left subtree
PreorderHelper( node.LeftNode );
// traverse right subtree
PreorderHelper( node.RightNode );
}
// begin inorder traversal
public void InorderTraversal()
{
lock ( this )
{
InorderHelper( root );
}
}
Method to help with
BinaryTreeLibrar
preorder traversal
y.cs
Display node data
Call PreorderHelper
recursively on left subtree
Call PreorderHelper
recursively on right subtree
Perform inorder traversal
Call InorderHelper to
help with traversal
// recursive method to perform inorder traversal
private void InorderHelper( TreeNode node )
{
if ( node == null )
return;
// traverse left subtree
InorderHelper( node.LeftNode );
Outline
Method to help with
inorder traversal
Call InorderHelper
recursively on left subtree
 2002 Prentice Hall.
All rights reserved.
55
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
// output node data
Console.Write( node.Data + " " );
// traverse right subtree
InorderHelper( node.RightNode );
}
// begin postorder traversal
public void PostorderTraversal()
{
lock ( this )
{
PostorderHelper( root );
}
}
Call InorderHelper BinaryTreeLibrar
recursively on righty.cs
subtree
Perform postorder traversal
Call PostorderHelper
to help with traversal
// recursive method to perform postorder traversal
private void PostorderHelper( TreeNode node )
{
if ( node == null )
return;
// traverse left subtree
PostorderHelper( node.LeftNode );
// traverse right subtree
PostorderHelper( node.RightNode );
// output node data
Console.Write( node.Data + " " );
}
}
}
Outline
Display node data
Method to help with
postorder traversal
Call PostorderHelper
recursively on left subtree
Call PostorderHelper
recursively on right subtree
Display node data
// end class Tree
 2002 Prentice Hall.
All rights reserved.
56
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Outline
// Fig. 23.18: TreeTest.cs
// This program tests class Tree.
using System;
using BinaryTreeLibrary;
namespace TreeTest
{
// class TreeTest definition
public class TreeTest
{
// test class Tree
static void Main( string[] args )
{
Tree tree = new Tree();
int insertValue;
TreeTest.cs
Create a tree
Console.WriteLine( "Inserting values: " );
Random random = new Random();
// insert 10 random integers from 0-99 in tree
for ( int i = 1; i <= 10; i++ )
{
insertValue = random.Next( 100 );
Console.Write( insertValue + " " );
Insert ten nodes in tree
tree.InsertNode( insertValue );
}
// perform preorder traveral of tree
Console.WriteLine( "\n\nPreorder traversal" );
tree.PreorderTraversal();
Call preorder traversal
 2002 Prentice Hall.
All rights reserved.
57
34
35
36
37
38
39
40
41
42
43
44
45
// perform inorder traveral of tree
Console.WriteLine( "\n\nInorder traversal" );
tree.InorderTraversal();
// perform postorder traveral of tree
Console.WriteLine( "\n\nPostorder traversal" );
tree.PostorderTraversal();
Console.WriteLine();
Outline
Call inorder traversal
TreeTest.cs
Call postorder traversal
}
}
// end class TreeTest
}
Inserting values:
39 69 94 47 50 72 55 41 97 73
Program Output
Preorder traversal
39 69 47 41 50 55 94 72 73 97
Inorder traversal
39 41 47 50 55 69 72 73 94 97
Postorder traversal
41 55 50 47 73 72 97 94 69 39
 2002 Prentice Hall.
All rights reserved.
58
25.7 Binary Search Tree of Integer Values
27
13
6
Fig. 23.19 A binary search tree.
 2002 Prentice Hall. All rights reserved.
42
17
33
48
59
25.7.2 Binary Search Tree of IComparable Objects
• Can use polymorphism to manipulate objects of different
types in uniform ways
– Binary search trees can be implemented to manipulate data of any
object that implements the IComparable interface
• Implementation of IComparable defines:
– CompareTo method
• E.g.: public void Insert( IComparable insertValue )
{
…
if ( insertValue.CompareTo( data ) < 0 )
…
}
– insertValue.CompareTo( data ) returns value:
• < 0 if insertValue < data
• = 0 if they are equal
• > 0 if insertValue > data
 2002 Prentice Hall. All rights reserved.
60
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Fig. 23.20: BinaryTreeLibrary2.cs
// Definition of class TreeNode and class Tree for IComparable
// objects.
using System;
Outline
BinaryTreeLibrar
y2.cs
namespace BinaryTreeLibrary2
{
// class TreeNode definition
class TreeNode
{
private TreeNode leftNode;
private IComparable data;
// polymorphic data stored in node
private TreeNode rightNode;
// initialize data and make this a leaf node
public TreeNode( IComparable nodeData )
{
data = nodeData;
leftNode = rightNode = null; // node has no children
}
// LeftNode property
public TreeNode LeftNode
{
get
{
return leftNode;
}
set
{
leftNode = value;
}
}
 2002 Prentice Hall.
All rights reserved.
61
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Data property
public IComparable Data
{
get
{
return data;
}
Outline
BinaryTreeLibrar
y2.cs
set
{
data = value;
}
}
// RightNode property
public TreeNode RightNode
{
get
{
return rightNode;
}
set
{
rightNode = value;
}
}
 2002 Prentice Hall.
All rights reserved.
62
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
Outline
// insert TreeNode into Tree that contains nodes;
// ignore duplicate values
public void Insert( IComparable insertValue )
{ // insertValue of polymorphic-enabling type IComparable
BinaryTreeLibrar
// insert in left subtree
y2.cs
if ( insertValue.CompareTo( data ) < 0 ) // Use
needIcomparable’s method
{ // ‘insertValue < data’ not sufficient – cf. sl.47 l.70)
CompareTo to determine if new
// insert new TreeNode
if ( leftNode == null )
node is less than its parent
leftNode = new TreeNode( insertValue );
// continue traversing left subtree
else
leftNode.Insert( insertValue ); // recursive
}
// insert in right subtree
Use Icomparable’s method
else if ( insertValue.CompareTo( data ) > 0 )
CompareTo to determine if new
{// ‘insertValue > data’ not sufficient – cf. sl.47 l.82
// insert new TreeNode
node is greater than its parent
if ( rightNode == null )
rightNode = new TreeNode( insertValue );
// continue traversing right subtree
else
rightNode.Insert( insertValue ); // recursive
}
// ignore if insertValue.CompareTo( data ) == 0 (duplicate value)
} // end method Insert
}
// end class TreeNode
 2002 Prentice Hall.
All rights reserved.
63
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// class Tree definition
public class Tree // differences w.r.t. Fig. 23.17 {
private TreeNode root;
in red
// construct an empty Tree of integers
public Tree()
{
root = null;
}
Outline
BinaryTreeLibrar
y2.cs
// Insert a new node in the binary search tree.
// If the root node is null, create the root node here.
// Otherwise, call the insert method of class TreeNode.
public void InsertNode( IComparable insertValue )
{
lock ( this )
{
if ( root == null )
root = new TreeNode( insertValue );
}
}
else
root.Insert( insertValue ); // use Insert from
// previous slide to insert new node into tree
// rooted at ‘root’
// begin preorder traversal
public void PreorderTraversal()
{
lock ( this )
{
PreorderHelper( root );
}
}
 2002 Prentice Hall.
All rights reserved.
64
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// recursive method to perform preorder traversal
private void PreorderHelper( TreeNode node )
{
if ( node == null )
return;
Outline
BinaryTreeLibrar
y2.cs
// output node data
Console.Write( node.Data + " " );
// traverse left subtree
PreorderHelper( node.LeftNode );
// traverse right subtree
PreorderHelper( node.RightNode );
}
// begin inorder traversal
public void InorderTraversal()
{
lock ( this )
{
InorderHelper( root );
}
}
// recursive method to perform inorder traversal
private void InorderHelper( TreeNode node )
{
if ( node == null )
return;
// traverse left subtree
InorderHelper( node.LeftNode );
 2002 Prentice Hall.
All rights reserved.
65
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
// output node data
Console.Write( node.Data + " " );
// traverse right subtree
InorderHelper( node.RightNode );
}
Outline
BinaryTreeLibrar
y2.cs
// begin postorder traversal
public void PostorderTraversal()
{
lock ( this )
{
PostorderHelper( root );
}
}
// recursive method to perform postorder traversal
private void PostorderHelper( TreeNode node )
{
if ( node == null )
return;
// traverse left subtree
PostorderHelper( node.LeftNode );
// traverse right subtree
PostorderHelper( node.RightNode );
// output node data
Console.Write( node.Data + " " );
}
}
}
// end class Tree
 2002 Prentice Hall.
All rights reserved.
66
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Outline
// Fig. 23.21: TreeTest.cs
// This program tests class Tree.
using System;
using BinaryTreeLibrary2;
namespace TreeTest
{
// class TreeTest definition
public class TreeTest
{
// test class Tree
static void Main( string[] args )
{
int[] intArray = { 8, 2, 4, 3, 1, 7, 5, 6 };
double[] doubleArray =
{ 8.8, 2.2, 4.4, 3.3, 1.1, 7.7, 5.5, 6.6 };
string[] stringArray = { "eight", "two", "four",
"three", "one", "seven", "five", "six" };
TreeTest.cs
Populate trees with int,
double and string values
// create int Tree
// - using: public public class Tree
Tree intTree = new Tree();
// empty tree
populateTree( intArray, intTree, "intTree" ); // next sl.
traverseTree( intTree, "intTree" );
// next sl.
// create double Tree
Tree doubleTree = new Tree();
populateTree( doubleArray, doubleTree, "doubleTree" );
traverseTree( doubleTree, "doubleTree" );
// create string Tree
Tree stringTree = new Tree();
populateTree( stringArray, stringTree, "stringTree" );
traverseTree( stringTree, "stringTree" );
}
 2002 Prentice Hall.
All rights reserved.
67
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
Outline
// populate Tree with array elements
static void populateTree(
Method to add data
Array array, Tree tree, string name )
from arrays
to trees
TreeTest.cs
{
Console.WriteLine( "\nInserting into " + name + ":" );
foreach ( IComparable data in array )
{
Console.Write( data + " " );
tree.InsertNode( data );
}
Insert nodes into tree
}
// insert perform traversals
static void traverseTree( Tree tree, string treeType )
{
// perform preorder traveral of tree
Console.WriteLine(
"\n\nPreorder traversal of " + treeType );
tree.PreorderTraversal();
// perform inorder traveral of tree
Console.WriteLine(
"\n\nInorder traversal of " + treeType );
tree.InorderTraversal();
Method to traverse tree
Perform preorder traversal
Perform inorder traversal
 2002 Prentice Hall.
All rights reserved.
68
63
64
65
66
67
68
69
70
71
// perform postorder traveral of tree
Console.WriteLine(
"\n\nPostorder traversal of " + treeType );
tree.PostorderTraversal();
Console.WriteLine( "\n" );
}
}
Outline
TreeTest.cs
Perform postorder traversal
// end class TreeTest
}
Inserting into intTree:
8 2 4 3 1 7 5 6
Program Output
Preorder traversal of intTree
8 2 1 4 3 7 5 6
Inorder traversal of intTree
1 2 3 4 5 6 7 8
Postorder traversal of intTree
1 3 6 5 7 4 2 8
 2002 Prentice Hall.
All rights reserved.
69
Inserting into doubleTree:
Outline
8.8 2.2 4.4 3.3 1.1 7.7 5.5 6.6
Preorder traversal of doubleTree
8.8 2.2 1.1 4.4 3.3 7.7 5.5 6.6
TreeTest.cs
Program Output
Inorder traversal of doubleTree
1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8
Postorder traversal of doubleTree
1.1 3.3 6.6 5.5 7.7 4.4 2.2 8.8
Inserting into stringTree:
eight two four three one seven five six
Preorder traversal of stringTree
eight two four five three one seven six
Inorder traversal of stringTree
eight five four one seven six three two
Postorder traversal of stringTree
five six seven one three four two eight
 2002 Prentice Hall.
All rights reserved.
70
The End
 2002 Prentice Hall. All rights reserved.