C++ Binary Search Tree question. I heed help with the level 2 question please, as level 1 is already completed. I will rate the answer a 100% thumbs up. I really appreciate the help!. Thank you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
// change to stored attribute if efficiency is important
template <class N> int size(N *root) {
if (root == 0)
return 0;
return 1 + size(root->left) + size(root->right);
}
// returns depth of tree
// change to stored attribute if efficiency is important
template <class N> int depth(N *root) {
if (root == 0)
return 0;
return 1 + max(depth(root->left), depth(root->right));
}
// returns true if tree is valid
// also checks size for randomised trees and depth for avl trees
template <class N> bool valid(N *root) {
if (root == 0)
return true;
return valid(root->left) && valid(root->right) &&
(root->left == 0 || root->left->key == root->key ||
root->left->key < root->key) &&
(root->right == 0 || root->key == root->right->key ||
root->key < root->right->key) &&
(mode != randomised ||
size(root) == 1 + size(root->left) + size(root->right)) &&
(mode != avl ||
depth(root) == 1 + max(depth(root->left), depth(root->right)));
}
// displays tree as a single-line with parens to indicate structure
// only really useful for small trees
template <class N> void print(N *root, ostream &out, bool verbose) {
if (root != 0) {
out << "(";
print(root->left, out, verbose);
out << root->key;
if (verbose) {
out << "/" << root->value;
if (mode == randomised)
out << "/" << size(root);
if (mode == avl)
out << "/" << depth(root);
}
print(root->right, out, verbose);
out << ")";
}
}
// displays tree as multiple lines with one node per line
// useful for trees up to around 100 nodes
template <class N>
void explode(N *root, ostream &out, bool verbose, string leader = "",
string before = " ", string after = " ") {
if (root != 0) {
explode(root->right, out, verbose, leader + before + " ", " ", "|");
out << leader + "+--" << root->key;
if (verbose) {
out << "/" << root->value;
if (mode == randomised)
out << "/" << size(root);
if (mode == avl)
out << "/" << depth(root);
}
out << endl;
explode(root->left, out, verbose, leader + after + " ", "|", " ");
}
}
/*
* Binary Search Tree template
* Key is key type (must define "<" and "==")
* Value is value type
*/
template <class Key, class Value> class BST {
struct Node {
Key key;
Value value;
Node *left;
Node *right;
};
public:
BST() { root = 0; }
// retuns true (and modifies value) if given key found
//level 1
bool search(const Key &key, Value &value) {
Node *node = root;
while(node != NULL) {
if(node->key == key) {
value = node->value;
return true;
}
if(key < node->key)
node = node->left;
else
node = node->right;
}
return false;
}
// inserts given key and value
void insert(const Key &key, const Value &value) {
Node *node = root;
Node *newNode = new Node;
newNode->key = key;
newNode->value = value;
newNode->left = newNode->right = NULL;
while (node != NULL) {
if(key < node->key) {
if(node->left == NULL) {
node->left = newNode;
return;
} else {
node = node->left;
}
} else {
if (node->right == NULL) {
node->right = newNode;
return;
} else {
node = node->right;
}
}
}
}
//level 2
// removes first-found match (if any) to given key
void remove(const Key &key) {
// add code here
}
// ------- tree information (for debugging)
bool valid() { return ::valid(root); }
int size() { return ::size(root); }
int depth() { return ::depth(root); }
void print(ostream &out, bool verbose) {
::print(root, out, verbose);
cout << endl;
}
void explode(ostream &out, bool verbose) { ::explode(root, out, verbose); }
private:
Node *root;
};
int main(int argc, char **argv) {
bool verbose = false;
bool auto_print = false;
bool auto_explode = false;
mode = simple;
for (int c; (c = getopt(argc, argv, "sravpeR")) != -1;) {
switch (c) {
case 's':
mode = simple;
break;
case 'r':
mode = randomised;
break;
case 'a':
mode = avl;
break;
case 'v':
verbose = true;
break; // verbose display
case 'p':
auto_print = true;
break; // print tree on every command
case 'e':
auto_explode = true;
break; // explode tree on every command
case 'R':
srand(getpid());
break; // randomise number sequence
}
}
argc -= optind;
argv += optind;
BST<int, int> tree;
string command;
while (getline(cin, command)) {
char function = 'i';
int limit = 100;
char sequence = '=';
int count = 1;
stringstream tokens(command);
if (tokens)
tokens >> function;
if (tokens)
tokens >> limit;
if (tokens)
tokens >> sequence;
if (tokens)
tokens >> count;
int found = 0;
int total = 0;
for (int i = 0; i < count; i++) {
int key = 0;
int value = 0;
switch (sequence) {
case '?':
key = rand() % limit;
break;
case '+':
key = (count + i) % limit;
break;
case '-':
key = (count - i - 1) % limit;
break;
case '=':
key = limit;
break;
}
switch (function) {
case 'i':
tree.insert(key, value = rand() % 100);
break;
case 'r':
tree.remove(key);
break;
case 'f':
if (tree.search(key, value))
found += 1;
break;
case 't':
if (tree.search(key, value))
total += value;
break;
}
}
if (!tree.valid()) {
cout << "Oops!" << endl;
exit(1);
}
if (function == 'f')
cout << "Found: " << found << endl;
if (function == 't')
cout << "Total: " << total << endl;
if (function == 'p' || auto_print)
tree.print(cout, verbose);
if (function == 'e' || auto_explode)
tree.explode(cout, verbose);
if (function == 'd' || verbose)
cout << "Depth: " << tree.depth() << endl;
if (function == 's' || verbose)
cout << "Size: " << tree.size() << endl;
}
}
//End of Code
Thank you!
Homework Answers
CODE:
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
// change to stored attribute if efficiency is important
template <class N> int size(N *root) {
if (root == 0)
return 0;
return 1 + size(root->left) + size(root->right);
}
// returns depth of tree
// change to stored attribute if efficiency is important
template <class N> int depth(N *root) {
if (root == 0)
return 0;
return 1 + max(depth(root->left), depth(root->right));
}
// returns true if tree is valid
// also checks size for randomised trees and depth for avl trees
template <class N> bool valid(N *root) {
if (root == 0)
return true;
return valid(root->left) && valid(root->right) &&
(root->left == 0 || root->left->key == root->key ||
root->left->key < root->key) &&
(root->right == 0 || root->key == root->right->key ||
root->key < root->right->key) &&
(mode != randomised ||
size(root) == 1 + size(root->left) + size(root->right)) &&
(mode != avl ||
depth(root) == 1 + max(depth(root->left), depth(root->right)));
}
// displays tree as a single-line with parens to indicate structure
// only really useful for small trees
template <class N> void print(N *root, ostream &out, bool verbose) {
if (root != 0) {
out << "(";
print(root->left, out, verbose);
out << root->key;
if (verbose) {
out << "/" << root->value;
if (mode == randomised)
out << "/" << size(root);
if (mode == avl)
out << "/" << depth(root);
}
print(root->right, out, verbose);
out << ")";
}
}
// displays tree as multiple lines with one node per line
// useful for trees up to around 100 nodes
template <class N>
void explode(N *root, ostream &out, bool verbose, string leader = "",
string before = " ", string after = " ") {
if (root != 0) {
explode(root->right, out, verbose, leader + before + " ", " ", "|");
out << leader + "+--" << root->key;
if (verbose) {
out << "/" << root->value;
if (mode == randomised)
out << "/" << size(root);
if (mode == avl)
out << "/" << depth(root);
}
out << endl;
explode(root->left, out, verbose, leader + after + " ", "|", " ");
}
}
/*
* Binary Search Tree template
* Key is key type (must define "<" and "==")
* Value is value type
*/
template <class Key, class Value> class BST {
struct Node {
Key key;
Value value;
Node *left;
Node *right;
};
public:
BST() { root = 0; }
// retuns true (and modifies value) if given key found
//level 1
bool search(const Key &key, Value &value) {
Node *node = root;
while(node != NULL) {
if(node->key == key) {
value = node->value;
return true;
}
if(key < node->key)
node = node->left;
else
node = node->right;
}
return false;
}
// inserts given key and value
void insert(const Key &key, const Value &value) {
Node *node = root;
Node *newNode = new Node;
newNode->key = key;
newNode->value = value;
newNode->left = newNode->right = NULL;
while (node != NULL) {
if(key < node->key) {
if(node->left == NULL) {
node->left = newNode;
return;
} else {
node = node->left;
}
} else {
if (node->right == NULL) {
node->right = newNode;
return;
} else {
node = node->right;
}
}
}
}
//level 2
// removes first-found match (if any) to given key
void remove(const Key &key) {
Node *node = root;
Node *parNode = null;
//Search for node with given key to delete
while(node != root) {
if(key == node->key){
break;
}
parNode = node;
if(key < node->key)
node = node->left;
else
node = node->right;
}
//Node with the key does not exists
if(node == null)
return;
// Bubble down the node
while(node->right != null) {
Node rightNode = node->right;
Node leftNode = node->left;
// Swap node and it's right child node
if(parNode->left == node){
parNode->left = rightNode;
} else {
parNode->right = rightNode;
}
node->right = rightNode->right;
node->left = rightNode->left;
rightNode->left = leftNode;
rightNode->right = node;
parNode = rightNode;
}
// Delete node
if(parNode->left == node){
parNode->left = node->left;
} else {
parNode->right = node->left;
}
delete node;
}
// ------- tree information (for debugging)
bool valid() { return ::valid(root); }
int size() { return ::size(root); }
int depth() { return ::depth(root); }
void print(ostream &out, bool verbose) {
::print(root, out, verbose);
cout << endl;
}
void explode(ostream &out, bool verbose) { ::explode(root, out, verbose); }
private:
Node *root;
};
int main(int argc, char **argv) {
bool verbose = false;
bool auto_print = false;
bool auto_explode = false;
mode = simple;
for (int c; (c = getopt(argc, argv, "sravpeR")) != -1;) {
switch (c) {
case 's':
mode = simple;
break;
case 'r':
mode = randomised;
break;
case 'a':
mode = avl;
break;
case 'v':
verbose = true;
break; // verbose display
case 'p':
auto_print = true;
break; // print tree on every command
case 'e':
auto_explode = true;
break; // explode tree on every command
case 'R':
srand(getpid());
break; // randomise number sequence
}
}
argc -= optind;
argv += optind;
BST<int, int> tree;
string command;
while (getline(cin, command)) {
char function = 'i';
int limit = 100;
char sequence = '=';
int count = 1;
stringstream tokens(command);
if (tokens)
tokens >> function;
if (tokens)
tokens >> limit;
if (tokens)
tokens >> sequence;
if (tokens)
tokens >> count;
int found = 0;
int total = 0;
for (int i = 0; i < count; i++) {
int key = 0;
int value = 0;
switch (sequence) {
case '?':
key = rand() % limit;
break;
case '+':
key = (count + i) % limit;
break;
case '-':
key = (count - i - 1) % limit;
break;
case '=':
key = limit;
break;
}
switch (function) {
case 'i':
tree.insert(key, value = rand() % 100);
break;
case 'r':
tree.remove(key);
break;
case 'f':
if (tree.search(key, value))
found += 1;
break;
case 't':
if (tree.search(key, value))
total += value;
break;
}
}
if (!tree.valid()) {
cout << "Oops!" << endl;
exit(1);
}
if (function == 'f')
cout << "Found: " << found << endl;
if (function == 't')
cout << "Total: " << total << endl;
if (function == 'p' || auto_print)
tree.print(cout, verbose);
if (function == 'e' || auto_explode)
tree.explode(cout, verbose);
if (function == 'd' || verbose)
cout << "Depth: " << tree.depth() << endl;
if (function == 's' || verbose)
cout << "Size: " << tree.size() << endl;
}
}
Comment down for any queries
Please give a thumb up
Add Answer to:
C++ Binary Search Tree question. I heed help with the level 2 question please, as level...
C++ Binary Search Tree question. I heed help with the level 2 question please, as level...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a...
PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a class called MyTree with the methods __init__(x), getLeft(), getRight(), getData(), insert(x) and getHeight(). Each child should itself be a MyTree object. The height of a leaf node should be zero. The insert(x) method should return the node that occupies the original node's position in the tree. Create a class called MyBST that extends MyTree. Override the method insert(x) to meet the definitions of a...
Hi there, I am working on a binary search tree code in c++. The program must...
Hi there, I am working on a binary search tree code in c++. The program must store and update students' academic records, each node includes the student name, credits attempted, credits earned and GPA. I have made some progress with the code and written most of the functions in the .cpp file (already did the .h file) but i am struggling with what to put in the main and how to put an update part in the insert function. I...
In this assignment, you will add several methods to the Binary Search Tree. You should have compl...
In this assignment, you will add several methods to the Binary Search Tree. You should have completed the following three methods in the lab: public void insert(Key key, Value value) public Value get(Key key) public void inorder(Node root) For this assignment, you will implement the following: public void remove(Node root, Key key) public Key getMin(Node n) public Key getMax(Node n) public int height(Node n) The main method contains the statements to check whether your implementation works. You need to change...
Consider the partial implementation of a Binary Search Tree (BST) class. For simplicity, each Node stores...
Consider the partial implementation of a Binary Search Tree
(BST) class. For simplicity, each Node stores only the key. Add a
public member function to class BST that returns the largest
absolute value in the tree.
The language is C++
Want the height
#4 Coding [6 points] Consider the partial implementation of a Binary Search Tree (BST) class. For simplicity, each Node stores only the key. Add a public member function to class BST that returns the height of the...
Binary Search Tree Part A: The code attached in this document is a sample code to demonstrate ins...
Binary Search Tree Part A: The code attached in this document is a sample code to demonstrate insert operation in binary search tree. Please fill in the missing part for the insert method to make the program work. The expected output should be as follows. 20 30 40 50 60 70 80 Part B: Find Lowest Common Ancestor (LCA) of a Binary Search Tree. According to WikiPedia definition , The lowest common ancestor is defined between two nodes v and...
C++: PLEASE HELP~!!! ~~~~~~~~ Implement bool AVLTree::deleteNode(string ss) method. Function deleteNode() tries to delete the node...
C++: PLEASE HELP~!!! ~~~~~~~~ Implement bool AVLTree::deleteNode(string ss) method. Function deleteNode() tries to delete the node containing value ss. If there is no such node, it returns false. Otherwise, it deletes the node, check the balance of the tree, rebalance the tree if it is necessary. When you delete a node, consider three different scenarios: -The node is a leaf -The node has only ONE child subtree -The node has two child subtrees Important: When you implement this project, do...
Consider the class specifications for the Binary Tree class and Binary Search Tree class in the...
Consider the class specifications for the Binary Tree class and Binary Search Tree class in the attached files // BinaryTree.h #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct TreeNode { elemType data; TreeNode<elemType> *left; TreeNode<elemType> *right; }; //Definition of class Binary Tree template <class elemType> class BinaryTree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); BinaryTree(); bool is Empty() const; virtual boot search(const elemType& searchItem) const = 0; virtual void insert(const elemType& insertItem)...
JAVA QUESTION: *******THE QUESTION:******** /** numberOfNodesAtDepth * * Returns the number of nodes with...
JAVA QUESTION: *******THE QUESTION:******** /** numberOfNodesAtDepth * * Returns the number of nodes with depth == d * Precondition: none * * param: d the depth to search for * * hint: use a recursive helper function * * ToDo 4 */ public int numNodesAtDepth(int d) { return -1; } **********USEFUL CODE FROM THE ASSIGNMENT:*********** public class simpleBST<Key extends Comparable<Key>, Value> { private Node root; ...
Java : This function is to search through a binary tree left and right and return...
Java : This function is to search through a binary tree left and right and return a count of the nodes above depth k. This is what I have so far, but I'm getting a Null pointer exception. public class MyIntSET { private Node root; private static class Node { public final int key; public Node left, right; public Node(int key) { this.key = key; } } public int sizeAboveDepth(int...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
Consider the partial implementation of a Binary Search Tree
(BST) class. For simplicity, each Node stores only the key. Add a
public member function to class BST that returns the largest
absolute value in the tree.
The language is C++
Want the height
#4 Coding [6 points] Consider the partial implementation of a Binary Search Tree (BST) class. For simplicity, each Node stores only the key. Add a public member function to class BST that returns the height of the...
Consider the class specifications for the Binary Tree class and Binary Search Tree class in the attached files // BinaryTree.h #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct TreeNode { elemType data; TreeNode<elemType> *left; TreeNode<elemType> *right; }; //Definition of class Binary Tree template <class elemType> class BinaryTree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); BinaryTree(); bool is Empty() const; virtual boot search(const elemType& searchItem) const = 0; virtual void insert(const elemType& insertItem)...
Most questions answered within 3 hours.
-
2. Boris recently synthesized an explosive compound he named
Badenoughium. The molecular formula for Bdenoughium is...
asked 3 hours ago -
5. A car decelerate evenly from a velocity of 50mph until rest
in a distance of...
asked 3 hours ago -
IN HTML Programming
1. Write a script that inputs integers (one at a time) and
passes...
asked 3 hours ago -
A dentist uses a mirror to examine a tooth that is 0.75 cm in
front of...
asked 3 hours ago -
You set up a 100,000 line of credit for the business on 1/1/X8,
annual interest is...
asked 3 hours ago -
What is the measurement uncertainty of a pan balance? How did you
get that?
asked 3 hours ago -
Suppose four firms have market shares of 30%, 30%, 20% and 20%.
What is the Herfindahl-Hirschman...
asked 3 hours ago -
IBT Industrial Solutions produces forty units of rack and pinion
type steering gears during an eight...
asked 3 hours ago -
The Ksp for PbI2 is 9.8×10−9 . Will PbI2 precipitate if 2.5 mL
of 0.0025 M...
asked 4 hours ago -
- Write a Person Constructor that initializes `name` and
`age` from arguments.
- All instances of...
asked 4 hours ago -
What is the meaning of the statement: In acid-base catalysis,
acid catalysis involves partial proton transfer...
asked 4 hours ago -
Polo Publishers purchased a multi-color offset press with terms
of $65,000 down and a noninterest-bearing note...
asked 4 hours ago