Transcript ppt

L12 (Chapter 20)
Lists, Stacks, Queues, Trees, and Heaps 2
Chapter 11 Object-Oriented Design
Chapter 20 Lists, Stacks, Queues, Trees, and Heaps
Chapter 21 Generics
Chapter 22 Java Collections Framework
Chapter 19 Recursion
Chapter 23 Algorithm Efficiency and Sorting
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
1
Stacks and Queues
A stack can be viewed as a special type of list, where the
elements are accessed, inserted, and deleted only from the
end, called the top, of the stack. A queue represents a
waiting list. A queue can be viewed as a special type of list,
where the elements are inserted into the end (tail) of the
queue, and are accessed and deleted from the beginning
(head) of the queue.
Since the insertion and deletion operations on a stack are
made only the end of the stack, using an array list to
implement a stack is more efficient than a linked list. Since
deletions are made at the beginning of the list, it is more
efficient to implement a queue using a linked list than an
array list. This section implements a stack class using an
array list and a queue using a linked list.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
2
Design of the Stack and Queue Classes
There are two ways to design the stack and queue classes:
·
Using inheritance: You can declare the stack class by
extending the array list class, and the queue class by
extending the linked list class.
·
Using composition: You can declare an array list as a
data field in the stack class, and a linked list as a data field
in the queue class.
Both designs are fine, but using composition is better
because it enables you to declare a complete new stack
class and queue class without inheriting the unnecessary
and inappropriate methods from the array list and linked
list.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
3
MyStack and MyQueue
MyStack
MyStack
-list: MyArrayList
+isEmpty(): boolean
Returns true if this stack is empty.
+getSize(): int
Returns the number of elements in this stack.
+peek(): Object
Returns the top element in this stack.
+pop(): Object
Returns and removes the top element in this stack.
+push(o: Object): Object
Adds a new element to the top of this stack.
+search(o: Object): int
Returns the position of the specified element in this stack.
MyQueue
MyQueue
-list: MyLinkedList
+enqueue(element: Object): void Adds an element to this queue.
+dequeue(): Object
Removes an element from this queue.
+getSize(): int
Returns the number of elements from this queue.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
4
Example: Using Stacks and Queues
Write a program that creates a stack using MyStack and a
queue using MyQueue. It then uses the push (enqueu)
method to add strings to the stack (queue) and the pop
(dequeue) method to remove strings from the stack
(queue).
TestStackQueue
Run
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
5
Binary Trees
A list, stack, or queue is a linear structure that consists of a sequence
of elements. A binary tree is a hierarchical structure. It is either empty
or consists of an element, called the root, and two distinct binary
trees, called the left subtree and right subtree. Examples of binary
trees are shown in Figure 20.18.
60
G
55
45
F
100
57
67
(A)
107
R
M
A
T
(B)
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
6
Binary Tree Terms
The root of left (right) subtree of a node is called a left
(right) child of the node. A node without children is called
a leaf. A special type of binary tree called a binary search
tree is often useful. A binary search tree (with no duplicate
elements) has the property that for every node in the tree
the value of any node in its left subtree is less than the
value of the node and the value of any node in its right
subtree is greater than the value of the node. The binary
trees in Figure 20.18 are all binary search trees. This
section is concerned with binary search trees.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
7
Representing Binary Trees
A binary tree can be represented using a set of linked
nodes. Each node contains a value and two links named
left and right that reference the left child and right child,
respectively, as shown in Figure 20.19.
class TreeNode {
Object element;
TreeNode left;
TreeNode right;
60
root
55
45
100
57
67
107
public TreeNode(Object o) {
element = o;
}
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
8
Inserting an Element to a Binary Tree
If a binary tree is empty, create a root node with the new
element. Otherwise, locate the parent node for the new
element node. If the new element is less than the parent
element, the node for the new element becomes the left
child of the parent. If the new element is greater than the
parent element, the node for the new element becomes the
right child of the parent. Here is the algorithm:
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
9
Inserting an Element to a Binary Tree
if (root == null)
root = new TreeNode(element);
For example, to insert 101 into the tree in
else {
Figure 20.19, the parent is the node for 107.
// Locate the parent node
The new node for 101 becomes the left child
current = root;
of the parent. To insert 59 into the tree, the
while (current != null)
parent is the node for 57. The new node for 59
if (element value < the value in current.element) {
becomes the right child of the parent, as shown
parent = current;
in Figure 20.20.
current = current.left;
}
else if (element value > the value in current.element) {
parent = current;
current = current.right;
60
root
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (element < parent.element)
parent.left = new TreeNode(elemenet);
else
parent.right = new TreeNode(elemenet);
55
45
100
57
67
107
return true; // Element inserted
}
59
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
101
10
Tree Traversal
Tree traversal is the process of visiting each node in the
tree exactly once. There are several ways to traverse a tree.
This section presents inorder, preorder, postorder, depthfirst, and breadth-first traversals.
The inorder traversal is to visit the left subtree of the
current node first, then the current node itself, and finally
the right subtree of the current node.
The postorder traversal is to visit the left subtree of the
current node first, then the right subtree of the current
node, and finally the current node itself.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
11
Tree Traversal, cont.
The breadth-first traversal is to visit the nodes level by
level. First visit the root, then all children of the root from
left to right, then grandchildren of the root from left to
right, and so on.
For example, in the tree in Figure 20.20, the inorder is 45
55 57 59 60 67 100 101 107. The postorder is 45 59 57 55
67 101 107 100 60. The preorder is 60 55 45 57 59 100 67
107 101. The breadth-first traversal is 60 55 100 45 57 67
107 59 101.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
12
The BinaryTree Class
Let’s define the binary tree class, named BinaryTree with
the insert, inorder traversal, postorder traversal, and
preorder traversal, as shown in Figure 20.21. Its
implementation is given as follows:
TreeNode
m
1
BinaryTree
BinaryTree
element: Object
-root: TreeNode
left: TreeNode
+BinaryTree()
right: TreeNode
+BinaryTree(objects: Object[]) Creates a binary tree from an array of objects.
+insert(o: Object): boolean
Adds an element to the binary tree.
1
Link
Creates a default binary tree.
+inorder(): void
Prints the nodes in inorder traversal.
+preorder(): void
Prints the nodes in preorder traversal.
+postorder(): void
Prints the nodes in postorder traversal.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
13
Example: Using Binary Trees
Write a program that creates a binary tree using
BinaryTree. Add strings into the binary tree and traverse
the tree in inorder, postorder, and preorder.
BinaryTree
Run
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
14
Heap
Heap is a useful data structure for designing efficient sorting
algorithms and priority queues. A heap is a binary tree with the
following properties:
It
is a complete binary tree.
Each node is greater than or equal to any of its children.
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
15
Complete Binary Tree
A binary tree is complete if every level of the tree is full except that the last level
may not be full and all the leaves on the last level are placed left-most. For
example, in Figure 20.23, the binary trees in (a) and (b) are complete, but the
binary trees in (c) and (d) are not complete. Further, the binary tree in (a) is a heap,
but the binary tree in (b) is not a heap, because the root (39) is less than its right
child (42).
42
32
22
39
39
29
14
32
33
22
42
29
14
42
42
32
22
32
39
14
33
22
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
29
16
Representing a Heap
For a node at position i, its left child is at position 2i+1 and its right
child is at position 2i+2, and its parent is (i-1)/2. For example, the
node for element 39 is at position 4, so its left child (element 14) is at
9 (2*4+1), its right child (element 33) is at 10 (2*4+2), and its parent
(element 42) is at 1 ((4-1)/2).
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13]
62
[10][11]
62 42 59 32 39 44 13 22 29 14 33 17 30 9
42
32
22
59
39
29
14
44
33
17
13
30
9
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
17
Rebuilding a Heap
9
59
42
32
22
59
39
29
14
44
33
17
42
13
30
32
22
9
39
29
14
44
33
59
59
42
22
44
39
29
14
9
33
17
30
(b) After swapping 9 with 59
(a) After moving 9 to the root
32
17
13
42
13
30
(c) After swapping 9 with 44
32
22
44
39
29
14
30
33
17
13
9
(d) After swapping 9 with 30
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
18
Removing the Root
9
59
42
32
22
59
39
29
14
44
33
17
42
13
30
32
22
9
39
29
14
44
33
59
59
42
22
44
39
29
14
9
33
17
30
(b) After swapping 9 with 59
(a) After moving 9 to the root
32
17
13
42
13
30
(c) After swapping 9 with 44
32
22
44
39
29
14
30
33
17
13
9
(d) After swapping 9 with 30
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
19
Adding a New Node
59
59
42
32
22
44
39
29
14
30
33
17
42
13
88
32
22
(a) Add 88 into an existing heap
44
39
29
14
88
33
88
42
22
88
39
29
14
44
33
17
30
(b) After swapping 88 with 30
59
32
17
13
42
13
30
(c) After swapping 88 with 44
32
22
59
39
29
14
44
33
17
13
30
(d) After swapping 88 with 59
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
20
The Heap Class
Heap
-list: java.util.ArrayList
+Heap()
Creates a default heap.
+Heap(objects: Object[])
Creates a heap with the specified objects.
+remove(): Object
Removes the root from the heap and returns it.
+add(newObject: Object): void
Adds a new object to the heap.
+getSize(): int
Returns the size of the heap.
Heap
TestHeap
Run
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
21
Priority Queue
A regular queue is a first-in and first-out data structure. Elements are
appended to the end of the queue and are removed from the
beginning of the queue. In a priority queue, elements are assigned
with priorities. When accessing elements, the element with the
highest priority is removed first. A priority queue has a largest-in,
first-out behavior. For example, the emergency room in a hospital
assigns patients with priority numbers; the patient with the highest
priority is treated first.
MyPriorityQueue
-heap: Heap
+enqueue(element: Object): void
Adds an element to this queue.
+dequeue(): Object
Removes an element from this queue.
+getSize(): int
Returns the number of elements from this queue.
MyPriorityQueue TestPriorityQueue
Liang, Introduction to Java Programming, Sixth Edition, (c) 2007 Pearson Education, Inc. All
rights reserved. 0-13-222158-6
Run
22