Have a question?
Message sent Close

Data Structures & Algorithms (CS 351) Lab 9 Spring 2018

Sandra Watson
0 reviews
  • Description
  • Full Document

University of Wisconsin-Milwaukee

Data Structures & Algorithms (CS 351)

Lab Exercise 9
Cursor Over Binary Search Trees
Just like other Collections we’ve used this semester, binary search trees (BST) may allow iteration over
their elements through use of an Iterator. In this lab, instead of using an Iterator, we will implement a
cursor over a BST. You will be required to implement the following method for a BST of integers:
• advance()
To help illustrate this, we provided an applet that prints a BST. The applet will highlight the current node
when there is one.
Using Eclipse, import “Lab9”:
/afs/cs.uwm.edu/users/classes/cs351/401/pantherid /git/lab9.git
1 advance()
The advance() method performs an in-order traversal controlled by the caller so the elements in the tree
would be returned in order. We use a current reference to keep track of the currently-traversed node.
Initially, current is null, because there is no current element. The start() method sets current to the node
that contains the smallest integer. An example is given below.
Each time the method advance() is called, we can get the new current value using getCurrent().
However, updating the reference current requires more work. In this lab, we use the parent pointers to find
the next element in the tree. Refer to Section 4, “Parent Pointers”, of the handout on the course website
for more details: http://www.cs.uwm.edu/classes/cs351/navigating-trees.pdf



Data Structures & Algorithms (CS 351) Lab 9 Spring 2018

NOTE: Please check the details before purchasing the document.