BIT 115 – SPRING 2001



'Flattening a BST'

Due: Wednesday, May 16th

[pic]

Part 1: What the program must accomplish

You are to take the starter project that has been supplied to you, and implement the methods necessary to convert a Binary Search Tree into a sorted, circular, doubly-linked list, as explained in more detail below. The starter project should provide you with the vast majority of the 'infrastructure' code (stuff like a definition for a BST, some test code, etc, etc) so that you can focus your efforts on how to do the actual conversion itself.

Further, your solution must satisfy the following constraints: your solution needs to be an 'in-place' conversion, meaning that the existing nodes of the BST are converted into being nodes in a doubly-linked list. The alternative would be to keep the original BST, and to generate a new chain of nodes to represent the linked list, and then discard the original BST nodes (using this alternative will cap your possible points at 80 – other errors will then be subtracted from that cap). Your solution needs to be reasonably efficient – I believe that there are multiple O(N) solutions to this problem, so anything that's substantially less efficient will need to be fixed in the revision. You are free to use either an iterative approach, or a recursive approach. Because you're allowed to use a recursive approach, you may use more than O(1) memory. You shouldn't need more than O(lg(N)) memory (for recursion), and it's possible to use only O(1) memory in the iterative case.

A more detailed explanation of the problem:

Consider what a Binary Search Tree normally looks like. In essence, it consists of a collection of nodes, wherein each node has a reference to everything that's smaller than it (traditionally, this is labeled the "left" reference), and a reference to everything that's larger than it (traditionally, this is labeled the "right" reference). The below picture shows this concisely:

[pic]

Now think about what a sorted, doubly-linked list looks like. In essence, it consists of a collection of nodes, wherein each node has a reference to everything that's smaller than it (traditionally, this is labeled the "previous" reference), and a reference to everything that's larger than it (traditionally, this is labeled the "next" reference). The below picture shows this concisely:

[pic]

Depending on which 'conversion algorithm' you use, it may be useful to quickly access either the smallest or the largest element in this doubly-linked list. What you are REQUIRED to produce (whether you find this useful or not) is a circular, doubly-linked list, an example of which is pictured below:

[pic]

Given that both are sorted (in their own way), given that both nodes look very similar (key/data, and a 'smaller' reference, and a 'larger' reference), it seems reasonable to convert from one form to another. For this homework assignment, you need to ONLY convert from the Binary Search Tree TO the doubly-linked list.

[pic]

Group Work, Commenting:

You are not allowed to work in groups this assignment. For this assignment, you should start, finish, and do all the work on your own. If you have questions, please contact the instructor.

Additionally, you should aggressively comment your code, paying particular attention to areas that are difficult to understand. If you found something to be tricky when you wrote it, make sure to comment it so that the next person (the instructor, who's grading you) understands what your code is doing. It is not necessary to comment every single line.

The purpose of new requirement is to both help you understand, and have you demonstrate, a thorough understanding of exactly how your program works.

Every file that you turn in should have:

• At the top of the file, you should put your name (first and last), the name of this class (“BIT 143”), and the year and quarter, and the assignment number, including the revision number, which starts at 0 (“A2.0”). If you’re handing this in again for a regrade, make sure to increase the minor version number by one (from “A2.0”, to “A2.1").

In general, you should make sure to do the following before handing in your project:

• All variables used should have meaningful names.

• The code should be formatted consistently, and in an easy to read format.

What to turn in:

• A single electronic folder (a directory). This folder should contain:

o The C# source code for the entire program. This will be all the .CS files that Visual creates for you.

o Any other files that Visual has created for you, including the solution file (.SLN), and the project file (.CSPROJ). Basically, you need to hand in the entire directory that created for you. You should leave out subfolders (such as the Debug, bin, or obj directories) that are generated from the source code/project.

How to electronically submit your homework:

There's a link on the homework page to the document that guides you through handing in your work, using the SourceGear Vault program.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download