project 7 binary coding + extra credit

P7.pdf

Home >Computer Science homework help >project 7 binary coding + extra credit

Project 7 Programming and Algorithms II

CSCI 211, Spring 2018

Objectives

• Implement a Binary Tree • Practice writing recursive functions • More practice parsing commands • Use the STL vector and queue

Protip: Start early and work daily.

Overview

Write a binary search tree class (called BST) that is a tree of C++ strings. A binary search tree (BST), is a binary tree (two children) where for every node in the tree, all the values in the node’s left subtree are less than the node’s value and all the values in the node’s right subtree are greater than the node’s value.

Write a main.cpp that instantiates a BST ob- ject and reads and executes commands from standard input. See table below for the list of commands.

Several of these commands are difficult to implement (especially the balanced and rebalance commands). It may take you a long time to figure out how to implement them. Example Binary Search Tree

Protip: You are free to use Google to read about binary search trees. However, you will face problems like these during employment interviews and you will not be allowed to use Google (even if you are interviewing at Google). The better you are at solving difficult problems the more career potential you will have.

Program Requirements

All program input/output must be done in main.cpp. This means that the BST functions must pass results back to the calling function using return values and/or reference parame- ters. Use a Standard Template Library (STL) vector when you need to pass multiple strings.

The program must handle the commands listed in the table below. If a command has an argument, the argument is on the same line as the command. All string arguments are allowed to contains spaces.

Each line of the input will have the following format (assume there is always a space between the command and the argument). The “<” and “>” are NOT in the input.

If there is no argument:

If there is an argument:

The space following the command is NOT part of the string. Assume that all string arguments are NOT empty.

Sample Input/Output

Input

insert Saturday

insert Friday

insert Tuesday

insert Monday

insert Thursday

insert Wednesday

echo Number of nodes in tree:

size

find Monday

find Sunday

echo The nodes in depth-first order:

echo The nodes in breadth-first order:

breadth

balanced

Output

Number of nodes in tree:

<Monday> is in tree.

<Sunday> is not in tree.

The nodes in depth-first order:

{Friday, Monday, Saturday, Thursday,

Tuesday, Wednesday}

The nodes in breadth-first order:

{Saturday, Friday, Tuesday, Monday,

Thursday, Wednesday}

Tree is balanced.

http://www.cplusplus.com/reference/vector/vector/

Command Argument Action Potential Error

echo string Write the string to standard output. Do not insert into tree. Used for commenting tests. Has nothing to do with the tree

none

insert string Insert the given string into the binary search tree. The tree must maintain the BST property after insert.

Print error if string already in tree.

size none Print the number of elements (also number of nodes) in the tree.

none (0 if tree is empty)

find string Print if the given string is or is not in the tree (both messages to stdout)

none

print none Use a depth-first traversal (dft) to print all elements in the tree.

none (empty brackets if tree is empty)

breadth none Use a breadth-first traversal (bft) to print all elements in the tree.

none (empty brackets if tree is empty)

distance none Print the average distance nodes are from the root. The root’s distance is 0. The root’s children are distance == 1, the root’s grandchildren are distance == 2, and so on. Calculate the distance for ALL nodes and then take the average.

none (0 if zero or one nodes)

balanced none Print if the tree is balanced or not balanced (this type of balanced is called “height-balanced”.

none (balanced if empty)

rebalance none Modify the tree so it is balanced.

Output Formatting

Command Output Formatting

echo Print string argument to standard output followed by newline.

insert None unless there is an error (see below for error message).

size Print the integer size of the tree to standard output followed by a newline.

find If the target string is in the tree, print the following to standard output: “<str> is in tree.\n” where str is the target. If the target string is NOT in the tree print the following to standard output: “<str> is not in tree.\n”

print Traverse the tree using a depth-first algorithm. Print all the elements in {}, separate strings by a comma+space, and terminate with a newline. {string one, string two, string three} There is NO comma after the last string. Print “{}\n” if the tree is empty (no space between the braces).

breadth Same format as print (it is helpful to write a vector printing function and use it for both print and breadth commands).

distance Print “Average distance of nodes to root = ” followed by the average (as a double) of all the node’s distances from root followed by a newline.

balanced If the tree is balanced, print to standard output: “Tree is balanced.\n” If the tree is NOT balanced, print to standard out- put: “Tree is not balanced.\n”

rebalance none

Error Messages

If an illegal command is entered, print to standard error: “Illegal command <cmd>.\n” where cmd is the illegal command. After an illegal command is entered, skip all other char- acters on that line of input and continue the program.

If insert is called on a string that is already in the tree, print to standard error: “insert <str> failed. String already in tree.\n” where str is the string entered.

The program should continue after both types of errors.

Protip: Always return zero from main(), even if there was an error.

Tips & Tricks

Implement and test the commands one at a time in the order they are listed in the above tables.

Protip: The tests are organized so for each command you implement you will pass one or more additional tests.

Several of the commands are best implemented using one public and one private functions. Consider the insert function:

class BST

{

public:

...

bool insert(string str) {return insert(str , m_root );}

...

private:

....

bool insert(string str , Node *& cur_root );

....

};

If the cur root is passed to the private insert function as a reference to a pointer (see above), the implementation will be less complicated. For example, consider the first time that the private insert() is called. m root is NULL but since a reference to m root is passed to insert() when it sets cur root to the new node, it is really updating m root:

bool BST:: insert(string str , Node *& cur_root)

{

if (cur_root == NULL)

{

// first time this is called , cur_root is a reference to m_root.

cur_root = new Node(str);

return true;

}

else

{

...

Subsequent calls to insert() will be passed the m left and m right fields of Nodes. If you use a reference parameter you do not have to check if m left or m right is NULL before you call insert; a reference to a NULL m left/m right pointer will work just like the reference to a NULL m root. If you use this method, you will never have m left = new Node(...) or m right = new Node(...). All calls to new Node(str) will always be assigned to cur root. HOWEVER, if you do not understand how the reference parameter works, you do not have to use it.

Protip: Commands do not contains spaces, so you can read them using operator>> (e.g. while (cin >> command)).

Protip: String arguments may contains spaces, so you must read them using getline().

Implement the recursive depth first traversal (dft) and breadth first traversal by inserting elements at the end of a vector as they traverse the tree. Pass the vector to the function as a reference:

void BST::dft(vector<string> &values, Node *cur root).

The breadth first traversal algorithm requires a queue. To remove an element from this queue, you first get the element with a call to front(), and then you remove it will a call to pop(). The pop() function removes the first element but does not return it, so you must use front() before you call pop().

Protip: Use the standard template library (STL) queue for this project.

balanced command

Write a recursive function that does two things:

1. determines if the tree is balanced and

2. returns the height of the tree.

If at any point during the tree traversal you discover a subtree (pointed to by cur root) is not balanced return -1. Otherwise return the height of the largest sub-tree plus one. Here is the algorithm:

int BST::balanced(Node *cur_root)

if cur_root is NULL

return 0; // balanced but of height zero

if either of my children’s subtrees

(those rooted at cur_root->m_left and cur_root->m_right)

is NOT balanced

return -1; // I’m not balanced

else return the largest of my children’s subtree plus one

(plus one is because we must count cur_node in the height)

rebalance command

Use the depth-first-traversal function used to print the tree to fill a vector with the elements in the tree. The elements will automatically be sorted from smallest to largest.

Delete all the Nodes in the tree. Set m root to NULL.

Write a recursive insert function (insert from vector()) that will insert all the elements in the vector into the tree calling the regular insert function.

The algorithm works like this:

insert the element in the middle of the vector

recursively insert the elements before that middle element

recursively insert the elements after that middle element

The argument to this function is always the complete vector of elements plus unique start and stop indexes for the range under consideration:

void BST::insert_from_vector(vector <string> &elements,

int start_index, int end_index)

{

// this call should recursively insert elements[start_index]..elements[end_index]

// on each recursive call, you send a different start_index and end_index

// to the recursive calls

handle the base cases where the range is of size zero or one

think carefully about what should happen in each of these cases

figure out the index of the middle element:

int middle_index = ... (if there are two possible middle indexes,

e.g. middle of an array of 4 is 1 or 2,

pick the smallest)

use your existing insert() to insert elements[middle_index];

recursively call insert_from_vector with middle_index+1 .. end_index

recursively call insert_from_vector with start_index .. middle_index - 1

}

General Requirements

The first lines of all your files (both .h and .cpp) must contain the following comments:

// filename

// last name , first name

// ecst_username

Programs without your name in all files will not be graded.

Comment your program. You should have block comments that explain each function. You should also comment for each line or short code block.

Format your code. Make sure your code blocks align. There is no required indentation strategy, but be consistent throughout your program.

Use descriptive variable names. Avoid ambiguous or short variable names, with the excep- tion of loop counters (e.g., i, j, k).

Use a capital letter to name classes in your code (e.g., BST). Use all lower case for your file names (e.g., bst.h).

Protip: Look at the .cmd files in the test directory to see the command line arguments of each test.

Submission

Submit your program at Turn-in. This assignment is worth 200 points.

main.cpp

bst.h

bst.cpp

Protip: Submit only your C++ files. Do not submit your object file or your executable program. Do not archive (e.g., zip) your files.

Each student will complete and submit this assignment individually. Submit your work be- fore the deadline as late work is not accepted (except using your late days).

Protip: If you do not finish in time, turn in whatever work you have. If you turn nothing, you get a zero. If you turn in something, you receive partial credit.

https://turnin.ecst.csuchico.edu/