C++代写：ECE244 Binary Search Trees|留学生CS代写|代做Java编程|C作业|C++程序|Python代码

代写数据结构中的Binary Search Tree，很常见的一类作业，补充实现class中的方法即可。

Objectives

The objectives of this assignment are to provide you with more practice on the use of the various C++ concepts/constructs introduced in the lectures so far, including classes, dynamic memory allocation, pointers, I/O, and dynamic data structures. This will be done in the context of implementing a binary search tree class.

Problem Statement

In this assignment, you will implement a simple database to store and retrieve data. You are creating a simple “domain name server” - a database that can rapidly look up string names, such as www.google.com, and return a 32-bit integer that is the Internet Protocol (IP) address corresponding to that “domain name”. This is the function performed by the domain name servers that allow you to type in easy to remember website names and have your web browser automatically go to the correct IP address (computer) to retrieve the web data.
You will implement three classes: DBentry, TreeNode and TreeDB. The DBentry class will be used to create objects that hold an entry of the database. Each entry has a key (a string, corresponding to the name of the internet domain) and some data (a 32-bit integer that gives the IP address and a boolean flag that indicates whether the computer at that IP address is active or not). The TreeDB and TreeNode classes will be used to create a binary search tree database of DBentry objects. TreeDB represents the entire binary tree, while each TreeNode represents a single node in the tree.
In a real domain names server, we would have to rapidly search billions of domain names (strings) as we looked for the IP address corresponding to a name. The fact that a binary search tree can find entries in large datasets very efficiently, and can also add new entries efficiently, makes it a very appropriate data structure for this application.

Command and Output Specification

Your database will be exercised by a simple parser. Whenever the parser expects the user to enter a command, it should prompt the user for input by outputting a greater than sign followed by a space:

> user input would appear here

The parser reads commands from cin, calls the appropriate TreeDB and DBentry functions, and sends the appropriate output to cout. Each command consists of an operation, followed by zero or more arguments. The command and the arguments are separated by white spaces, and will always appear on the same line. You parser should process commands until the end-of-file (eof) is encountered. You may assume that all the input is syntactically correct - your program will not be tested with invalid commands, the wrong number of arguments, or misspelt arguments. The only error messages you need to generate are those listed below. The commands and their parameters are:

insert name IPaddress status

This command creates a new entry with name (a string) as the key and IPaddress (a non-negative integer) and status (active or inactive) as specified. You may assume that the name, IPaddress, and active arguments are separated by spaces and that there are no spaces within an argument. The new entry is then inserted into the database. If there already exists an entry with the same key, the error message “Error: entry already exists” is printed to cout. Otherwise “Success” is printed.

find name

This command finds the entry with the key name in the database, and prints its contents to cout as name : IPaddress : status. Name and IPaddress are printed as a string and an unsigned integer, respectively, while status is either active or inactive. Between values a space, colon and space should be printed.
If no such entry exists, the error message “Error: entry does not exist” is printed to cout.

remove name

This command deletes the entry with the key name from the database. If no such entry exists, the error message “Error: entry does not exist” is printed to cout. Otherwise “Success” is printed.

printall

This command prints all the entries in the database, sorted in ascending order of keys, one entry per line.

printprobes name

This command finds the entry with the key name in the database.
If no such entry exists, the error message “Error: entry does not exist” is printed to cout. Otherwise, the number of probes (DBentries examined during the tree search) is printed to cout.

removeall

This command deletes all the entries in the database, returning it to the empty state. When done, “Success” is printed.

countactive

This command counts the number of entries in the database that are active and prints this count to cout.

updatestatus name status

This command updates the status of the entry with the given name; status must be either active or inactive. If no entry with name exists, the error message “Error: entry does not exist” is printed to cout.
Otherwise “Success” is printed.

The Tree-based Database

The tree-based implementation assumes that the database is made of a BST, with data being pointers to DBentrys, as shown below.
The left and right pointers fields in each TreeNode are pointers to the left and right subtrees respectively. The BST is “ordered” by keys. That is, the name field of each DBentry is the key of the BST.

Code Structure and Development Procedure

Create a sub-directory called lab5 in your ece244 directory, using the mkdir command.
Make it your working directory. You are given 3 .h files to get you started in the lab; download them from the portal.

The DBentry Class

The DBentry class has three fields: one to represent the key and two data fields. It also has the several methods to set and access this private data, as shown in the header file below.

class DBentry {
private:
  string name;
  unsigned int IPaddress;
  bool active;
public:
  // constructors
  DBentry();
  DBentry (string _name, unsigned int _IPaddress, bool _active);

  // the destructor
  ~DBentry();

  // sets the domain name, which we will use as a key.
  void setName(string _name);

  // sets the IPaddress data.
  void setIPaddress(unsigned int _IPaddress);

  // sets whether or not this entry is active.
  void setActive (bool _active);

  // returns the name.
  string getName() const;

  // returns the IPaddress data.
  unsigned int getIPaddress() const;

  // returns whether or not this entry is active.
  bool getActive() const;

  // prints the entry in the format
  // name : IPaddress : active followed by newline
  // active is printed as a string (active or inactive)
  friend ostream& operator<< (ostream& out, const DBentry& rhs);
}

Write the implementation of this class in a file called DBentry.cpp. We suggest you implement this class first, and then test it with a simple test harness - a main () function that creates, modifies and prints DBentries. This is a good practice in developing larger programs: build components one at a time, and test each one before building a larger component that relies on it.

For example, if you write your test harness in a file called testDBentry.cpp, you could then test DBentry using:

g++ -g -Wall testDBentry.cpp DBentry.cpp -o testDBentry
./testDBentry

The TreeNode Class

This class stores individual nodes of the tree. Each node stores left and right pointers to children of this node, as well as a pointer to a DBentry that stores the key and data associated with a node. Its header file is given below.

#include "DBentry.h"

class TreeNode {
private:
  DBentry* entryPtr;
  TreeNode* left;
  TreeNode* right;

public:
  // A useful constructor
  TreeNode(DBentry* \_entryPtr);

  // the destructor
  ~TreeNode();

  // sets the left child of the TreeNode.
  void setLeft(TreeNode* newLeft);

  // sets the right child of the TreeNode
  void setRight(TreeNode* newRight);

  // gets the left child of the TreeNode.
  TreeNode* getLeft() const;

  // gets the right child of the TreeNode
  TreeNode* getRight() const;

  // returns a pointer to the DBentry the TreeNode contains.
  DBentry* getEntry() const;
};

Write the implementation of this class in a file called TreeNode.cpp. Once again we recommend that you implement TreeNode completely and test it with a test harness (another
.cpp file that implements a main() function and possibly helper subroutines that create, manipulate and print TreeNodes) before continuing on to the next part of the lab.

The TreeDB Class

This class respresents the overall database, and has methods to perform various useful functions on the database. An initial header file is given below. You will have to add new private functions to this header file to complete the lab.

#include "TreeNode.h"
#include "DBentry.h"

class TreeDB {
private:
  TreeNode* root;
  int probesCount;
  // You will need to add additional private functions

public:
  // the default constructor, creates an empty database.
  TreeDB();

  // the destructor, deletes all the entries in the database.
  ~TreeDB();

  // inserts the entry pointed to by newEntry into the database.
  // If an entry with the same key as newEntry's exists
  // in the database, it returns false. Otherwise, it returns true.
  bool insert(DBentry* newEntry);

  // searches the database for an entry with a key equal to name.
  // If the entry is found, a pointer to it is returned.
  // If the entry is not found, the NULL pointer is returned.
  // Also sets probesCount
  DBentry* find(string name);

  // deletes the entry with the specified name (key) from the database.
  // If the entry was indeed in the database, it returns true.
  // Returns false otherwise.
  // See Section 6 for the *required* removal method so you match
  // exercise's output.
  bool remove(string name);

  // deletes all the entries in the database.
  void clear();

  // prints the number of probes stored in probesCount
  void printProbes() const;

  // computes and prints out the total number of active entries
  // in the database (i.e. entries with active==true).
  void countActive () const;

  // Prints the entire tree, in ascending order of key/name
  // The entries are printed one per line, using the
  // operator<< for DBentry.
  friend ostream& operator[[ (ostream& out, const TreeDB& rhs);
};
// You *may* choose to implement the function below to help print the
// tree. You do not have to implement this function if you do not wish to. ostream& operator[[ (ostream& out, TreeNode* rhs);

Main.cpp

Implement your parser in Main.cpp. You will call public functions in TreeDB and DBentry to implement the commands after you have parsed them.

Coding Requirements

No global variables are to be used.
All data members of DBentry, TreeNode and TreeDB must be of private type.
You should minimize the number of additional public functions you create. No additional public functions in DBentry, TreeNode and TreeDB are required to complete the lab.
Your program should free all its memory; we will check for memory leaks using valgrind, and deduct marks if your program leaks memory.
As the purpose of this lab is to implement a binary search tree “from scratch”, you are not allowed use the standard template library.

Deliverables

You must submit the following files:

Main.cpp
DBentry.h
DBentry.cpp
TreeNode.h
TreeNode.cpp
TreeDB.h
TreeDB.cpp

Background

A binary search tree (BST) is a binary tree for which: (1) each node has a key that is unique; (2) the key of each node is greater than the keys of all nodes in its left subtree; and (3) the key of each node is smaller than the keys of all nodes in its right subtree. Thus, a BST is an ordered binary tree in which left is smaller than node, which in turn is smaller than right. Since this order property holds for every node in the tree, the left and right subtrees of any node are also binary search trees. That is, the order property holds recursively.
For example, the binary tree below is a BST, in which the keys of the nodes are integers. The key of the root is larger than any of the keys in its left subtree and is smaller than any of the keys in its right subtree. Each of the left and right subtrees is also BST. The left subtree is rooted at a node whose key 10 is larger than all the keys in its own left subtree (8), but smaller than all the keys in its own right subtree (11).
On the other hand, the binary tree below is not a BST (why? Hint: hotel elevators often skip this floor).
The order property of a BST makes it easy and efficient to search for a node in the tree, with a given search key. Given a BST and a search key k, the goal is to determine if there exists a node in the BST that has a key k (remember, because the keys are unique, there can be at most one such node). One simply compares the search key k to the key of the root of the BST. If they are equal, then the root is the node searched for. If k is less than the key of the root, then if a node exists with a matching key, the node must be in the left subtree. One then recursively repeats the search in the left subtree. Otherwise, k is greater than the key of the root, and thus, if a node exists with a matching key, it must be in the right subtree. Thus, one recursively repeats the search in the right subtree. Each comparison of the search key with a key of a node in the tree is called a probe.