Introduction
1 :
Example.java size = 10
：
3 ：
5：，
Requirement
Data Structures and Algorithms
COMP 2140
Department of Computer Science
University of Manitoba
Assignment 4 due by 4:30 pm on November 22
To permit the prompt distribution of solutions and return of marked assignments, late assignments will
not be accepted. Include your name, student number, and email address at the top of the first page on all
submitted material, as well as the names of people with whom you have discussed your assignment solution.
Cite any sources to which you refer, as you should do when presenting any scientific document. You must
submit your solution electronically using UMLearn. Only pdf and java files will be accepted.
Familiarize yourself with the code in the following files.
• MyQueue.java: This class implements a queue with the usual operations enqueue, dequeue, and
isEmpty. This code is similar to that used in Assignment 3. You should not edit this file.
• MyStack.java: This class implements a stack with the usual operations push, pop, and isEmpty. This
code is similar to that used in Lab 3 and Assignment 3. You should not edit this file.
• Node.java: This class implements a linked-list node. This code is similar to that used in Lab 2, Lab
3, Assignment 2, and Assignment 3. You should not edit this file.
• EmptyStackQueueException.java: This class implements an exception thrown when an attempt is
made to perform. a pop or dequeue operation on an empty stack or queue. This code is similar to that
used in Lab 3 and Assignment 3. You should not edit this file.
• TreeNode.java: This class implements a binary tree node. This code is similar to that used in Lab 4.
You should not edit this file.
• Example.java: This code shows an example of how to instantiate and use the class BST. You may edit
this file to help you test your code.
• DictionaryADT.java: This interface declares the usual methods for the Dictionary Abstract Data
Type: insert, delete, search, minimum, maximum, predecessor, and successor. You should not
edit this file.
• BST.java: This class implements the Dictionary ADT using a binary search tree. Although the
basic operations are unchanged (insert, delete, search, minimum, maximum, predecessor, and
successor), this code has a few differences from that used in Lab 4. You are to edit and submit
this file.
You are to edit the file BST.java as described below and write answers to the corresponding questions.
Submit two files on UMLearn:
• your edited file BST.java as described in Questions 2 and 4,
• a file named answers.pdf with your written answers to Questions 1, 3, and 5.
1. In your written solution, identify the type of tree traversal implemented by the method graphAux.
2. Add code to the method methodA in the class BST that does the following:
(a) Declare and instantiate a new (empty) stack whose elements will be instances of the class TreeNode.
The syntax should look something like this:
MyStack> stack = new MyStack>();
(b) Push the root of the binary search tree onto the stack.
Fall 2017, Assignment 4 page 1
Data Structures and Algorithms
COMP 2140
Department of Computer Science
University of Manitoba
(c) Write a while loop that terminates once the stack is empty.
(d) Each iteration of the loop should do the following:
• Pop the stack.
• If the popped item is not null, then print the element, push its left child onto the stack, and
push its right child onto the stack.
This method should be an accessor method. That is, only local variables within the method should be
modified; none of the instance variables should be modified.
3. In your written solution, describe the outcome of a call to methodA on a binary search tree.
4. Add code to the method methodB in the class BST that does the following:
(a) Declare and instantiate a new (empty) queue whose elements will be instances of the class
TreeNode. The syntax should look something like this:
MyQueue> queue = new MyQueue>();
(b) Enqueue the root of the binary search tree to the queue.
(c) Write a while loop that terminates once the queue is empty.
(d) Each iteration of the loop should do the following:
• Dequeue an item from the queue.
• If the dequeued item is not null, then print the element, enqueue its left child to the queue,
and enqueue its right child to the queue.
This method should be an accessor method. That is, only local variables within the method should be
modified; none of the instance variables should be modified.
5. In your written solution, describe the outcome of a call to methodB on a binary search tree.
Fall 2017, Assignment 4 page 2