Take the following code for a binary source tree and make it include the following operations....
Take the following code for a binary source tree and make it include the following operations.
bool replace(const Comparable & item, const Comparable & replacementItem);
int getNumberOfNodes() const;
(a) The replace method searches for the node that contains item in a binary search tree, if it is found, it replaces item with replacementItem. The binary tree should remain as a binary search tree after the replacement is done. Add the replace operation to the BinarySearchTree class. Test your replace using a client program of BinarySearchTree class.
(b) Implement the getNumberOfNodes method in the BinarySearchTree class. Test your implementation of getNumberOfNodes using a client program of BinarySearchTree class.
#include <iostream>
using namespace std;
template<typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree()
{
root =
NULL;
}
BinarySearchTree(const
BinarySearchTree & rhs);
~BinarySearchTree()
{
makeEmpty();
}
const Comparable & findMin()
const
{
return
findMin(root);
}
const Comparable & findMax()
const
{
return
findMax(root);
}
bool contains(const Comparable
& x) const
{
return
contains(x, root);
}
bool isEmpty() const
{
return ((root ==
NULL) ? true : false);
}
void printTree(ostream & out =
cout) const
{
out <<
"Start Traversing" << endl;
if
(isEmpty())
out << "Empty tree" << endl;
else
printTree(root, out);
out <<
"End Traversing" << endl;
}
void makeEmpty()
{
makeEmpty(root);
}
void insert(const Comparable &
x)
{
insert(x,
root);
}
void remove(const Comparable &
x)
{
remove(x,
root);
}
const BinarySearchTree &
operator=(const BinarySearchTree & rhs)
{
if (this !=
&rhs)
{
makeEmpty();
root = clone(rhs.root);
}
return
*this;
}
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const Comparable & theElement,
BinaryNode *lt, BinaryNode *rt) :
element(theElement), left(lt), right(rt)
{
}
};
BinaryNode *root;
void insert(const Comparable &
x, BinaryNode * & t)
{
if (t ==
NULL)
t = new BinaryNode(x, NULL, NULL);
else if (x <
t->element)
insert(x, t->left);
else if
(t->element < x)
insert(x, t->right);
else
; // Duplicate; do nothing
}
void remove(const Comparable &
x, BinaryNode * & t)
{
if (t ==
NULL)
return; // Item not found; do nothing
if (x <
t->element)
remove(x, t->left);
else if
(t->element < x)
remove(x, t->right);
else if
(t->left != NULL && t->right != NULL) // Two
children
{
t->element =
findMin(t->right)->element;
remove(t->element, t->right);
}
else
{
BinaryNode *oldNode = t;
t = (t->left != NULL) ? t->left :
t->right;
delete oldNode;
}
}
BinaryNode * findMin(BinaryNode *t)
const
{
if (t ==
NULL)
return NULL;
if (t->left
== NULL)
return t;
return
findMin(t->left);
}
BinaryNode * findMax(BinaryNode *t)
const
{
if (t !=
NULL)
while (t->right != NULL)
t = t->right;
return t;
}
bool contains(const Comparable
& x, BinaryNode *t) const
{
if (t ==
NULL)
return false;
else if (x <
t->element)
return contains(x, t->left);
else if
(t->element < x)
return contains(x, t->right);
else
return true; // Match
}
void makeEmpty(BinaryNode * &
t)
{
if (t !=
NULL)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
int height(BinaryNode *t)
{
if (t ==
NULL)
return -1;
else
return 1 + max(height(t->left),
height(t->right));
}
void printTree(BinaryNode *t,
ostream & out) const
{
if (t !=
NULL)
{
// out << t->element <<
"\n";
printTree(t->left, out);
// out << t->element <<
"\n";
printTree(t->right, out);
out << t->element << "\n";
}
}
BinaryNode * clone(BinaryNode *t)
const
{
if (t ==
NULL)
return NULL;
return new
BinaryNode(t->element, clone(t->left),
clone(t->right));
}
};
int main()
{
cout << "Starting!" << endl;
BinarySearchTree<int> myTree;
myTree.insert(11);
cout << "Inserted 11" << endl;
myTree.insert(12);
cout << "Inserted 12" << endl;
myTree.insert(6);
cout << "Inserted 6" << endl;
myTree.insert(8);
cout << "Inserted 8" << endl;
myTree.insert(7);
cout << "Inserted 7" << endl;
myTree.insert(9);
cout << "Inserted 9" << endl;
myTree.insert(2);
cout << "Inserted 2" << endl;
myTree.insert(4);
cout << "Inserted 4" << endl;
myTree.insert(10);
cout << "Inserted 10" << endl;
myTree.insert(5);
cout << "Inserted 5" << endl;
myTree.insert(14);
cout << "Inserted 14" << endl;
myTree.insert(13);
cout << "Inserted 13" << endl;
myTree.printTree(cout);
myTree.remove(13);
cout << "Removed 13" << endl;
myTree.printTree(cout);
myTree.remove(5);
cout << "Inserted 5" << endl;
myTree.printTree(cout);
cout << "Ending!" << endl;
return 0;
Homework Answers
#include <iostream>
using namespace std;
template<typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree()
{
root = NULL;
}
BinarySearchTree(const BinarySearchTree & rhs);
~BinarySearchTree()
{
makeEmpty();
}
const Comparable & findMin() const
{
return findMin(root);
}
const Comparable & findMax() const
{
return findMax(root);
}
bool contains(const Comparable & x) const
{
return contains(x, root);
}
bool isEmpty() const
{
return ((root == NULL) ? true : false);
}
bool replace(const Comparable & item, const Comparable & replacementItem){
return replace(item,replacementItem, root);
}
int getNumberOfNodes() const{
return getNumberOfNodes(root);
}
void printTree(ostream & out = cout) const
{
out << "Start Traversing" << endl;
if (isEmpty())
out << "Empty tree" << endl;
else
printTree(root, out);
out << "End Traversing" << endl;
}
void makeEmpty()
{
makeEmpty(root);
}
void insert(const Comparable & x)
{
insert(x, root);
}
void remove(const Comparable & x)
{
remove(x, root);
}
const BinarySearchTree & operator=(const BinarySearchTree & rhs)
{
if (this != &rhs)
{
makeEmpty();
root = clone(rhs.root);
}
return *this;
}
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const Comparable & theElement, BinaryNode *lt, BinaryNode *rt) :
element(theElement), left(lt), right(rt)
{
}
};
BinaryNode *root;
void insert(const Comparable & x, BinaryNode * & t)
{
if (t == NULL)
t = new BinaryNode(x, NULL, NULL);
else if (x < t->element)
insert(x, t->left);
else if (t->element < x)
insert(x, t->right);
else
; // Duplicate; do nothing
}
void remove(const Comparable & x, BinaryNode * & t)
{
if (t == NULL)
return; // Item not found; do nothing
if (x < t->element)
remove(x, t->left);
else if (t->element < x)
remove(x, t->right);
else if (t->left != NULL && t->right != NULL) // Two children
{
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else
{
BinaryNode *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
BinaryNode * findMin(BinaryNode *t) const
{
if (t == NULL)
return NULL;
if (t->left == NULL)
return t;
return findMin(t->left);
}
BinaryNode * findMax(BinaryNode *t) const
{
if (t != NULL)
while (t->right != NULL)
t = t->right;
return t;
}
bool contains(const Comparable & x, BinaryNode *t) const
{
if (t == NULL)
return false;
else if (x < t->element)
return contains(x, t->left);
else if (t->element < x)
return contains(x, t->right);
else
return true; // Match
}
void makeEmpty(BinaryNode * & t)
{
if (t != NULL)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
int height(BinaryNode *t)
{
if (t == NULL)
return -1;
else
return 1 + max(height(t->left), height(t->right));
}
bool replace(const Comparable & item, const Comparable & replacementItem, BinaryNode *t){
if (t == NULL)
return false;
else if (item < t->element)
return replace(item, replacementItem,t->left);
else if (t->element < item)
return replace(item, replacementItem,t->right);
else{
t->element = replacementItem;
return true; // Match
}
}
int getNumberOfNodes(BinaryNode *t) const{
if (t == NULL)
return 0;
else
return 1 + getNumberOfNodes(t->left) + getNumberOfNodes(t->right);
}
void printTree(BinaryNode *t, ostream & out) const
{
if (t != NULL)
{
// out << t->element << "\n";
printTree(t->left, out);
// out << t->element << "\n";
printTree(t->right, out);
out << t->element << "\n";
}
}
BinaryNode * clone(BinaryNode *t) const
{
if (t == NULL)
return NULL;
return new BinaryNode(t->element, clone(t->left), clone(t->right));
}
};
int main()
{
cout << "Starting!" << endl;
BinarySearchTree<int> myTree;
myTree.insert(11);
cout << "Inserted 11" << endl;
myTree.insert(12);
cout << "Inserted 12" << endl;
myTree.insert(6);
cout << "Inserted 6" << endl;
myTree.insert(8);
cout << "Inserted 8" << endl;
myTree.insert(7);
cout << "Inserted 7" << endl;
myTree.insert(9);
cout << "Inserted 9" << endl;
myTree.insert(2);
cout << "Inserted 2" << endl;
myTree.insert(4);
cout << "Inserted 4" << endl;
myTree.insert(10);
cout << "Inserted 10" << endl;
myTree.insert(5);
cout << "Inserted 5" << endl;
myTree.insert(14);
cout << "Inserted 14" << endl;
myTree.insert(13);
cout << "Inserted 13" << endl;
myTree.printTree(cout);
myTree.remove(13);
cout << "Removed 13" << endl;
myTree.printTree(cout);
myTree.remove(5);
cout << "Removed 5" << endl;
myTree.printTree(cout);
cout << "Number of Nodes: "<<myTree.getNumberOfNodes() <<endl;
myTree.replace(10,100);
cout << "Replaced 10 with 100" << endl;
myTree.printTree(cout);
cout << "Ending!" << endl;
return 0;
}
====================================================
DONE WITH BOTH THE METHOD, PLEASE CHECK, PLEASE UPVOTE
SEE OUTPUT
PLEASE COMMENT if there is any concern.
==========================================
Add Answer to:
Take the following code for a binary source tree and make it
include the following operations....
In C++ I need the printRange function, and the main.cpp program. Thanks. (Binary search tree) Write...
In C++ I need the printRange function, and the main.cpp program. Thanks. (Binary search tree) Write a function printRange that takes as input a binary search tree t and two keys, k1 and k2, which are ordered so that k1 < k2, and print all elements x in the tree such that k1 <= x <= k2. You can add this function in BinarySearchTree.h (click the link) that we used in the lecture and lab 7. public: void printRange(int k1,...
After the header, each line of the database file rebase210.txt contains the name of a restriction...
After the header, each line of the database file rebase210.txt contains the name of a restriction enzyme and possible DNA sites the enzyme may cut (cut location is indicated by a ‘) in the following format: enzyme_acronym/recognition_sequence/…/recognition_sequence// For instance the first few lines of rebase210.txt are: AanI/TTA'TAA// AarI/CACCTGCNNNN'NNNN/'NNNNNNNNGCAGGTG// AasI/GACNNNN'NNGTC// AatII/GACGT'C// AbsI/CC'TCGAGG// AccI/GT'MKAC// AccII/CG'CG// AccIII/T'CCGGA// Acc16I/TGC'GCA// Acc36I/ACCTGCNNNN'NNNN/'NNNNNNNNGCAGGT// … That means that each line contains one enzyme acronym associated with one or more recognition sequences. For example on line 2:The enzyme acronym...
Q. write the algorithm for each function in this code: void insert(int x, node*&p) { //cheak...
Q. write the algorithm for each function in this code: void insert(int x, node*&p) { //cheak if the pointer is pointing to null. if (p==NULL) { p = new node; p->key=x; p->left=NULL; p->right=NULL; } else { //Cheak if the element to be inserted is smaller than the root. if (x < p->key) { //call the function itself with new parameters. insert(x,p->left); } //cheak if the alement to be inserted...
Having code issues wth my C++ program. My program checks if two binary trees are similar...
Having code issues wth my C++ program. My program checks if two binary trees are similar and if they're not they return false. My program is return true with different binary trees. Could use some help thanks #include <iostream> #include <string> using namespace std; //Struct of Nodes struct BinarySearchTree { int data; BinarySearchTree *left; BinarySearchTree *right; }; // Inserting nodes into BST BinarySearchTree* insert( BinarySearchTree* node, int val) { if (node == NULL) { BinarySearchTree *newNode = new BinarySearchTree(); newNode->data...
Convert the TreeArray C++ source code(posted below) into a BinaryTree, using this TreeNode definition: class TreeNode<T>...
Convert the TreeArray C++ source code(posted below) into a BinaryTree, using this TreeNode definition: class TreeNode<T> T data TreeNode<T> left TreeNode<T> right Since this TreeNode is a generic Template, use any data file we've used this quarter to store the data in the BinaryTree. To do this will likely require writing a compare function or operator. Hint: Think LEFT if the index is calculate (2n+1) and RIGHT if index is (2n+2). Source code: #include<iostream> using namespace std;...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well. struct ListNode { int element; ListNode *next; } Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well. struct ListNode { int element; ListNode *next; } Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and...
public class Buildbst { private int data; private Buildbst left; private Buildbst right; //Set the binary...
public class Buildbst { private int data; private Buildbst left; private Buildbst right; //Set the binary search tree public Buildbst(int data) { this.data = data; this.left = null; this.right =null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Buildbst getLeft() { return left; } public void setLeft(Buildbst left) { this.left = left; } public Buildbst getRight() { return right; } public void setRight(Buildbst right) { this.right = right; } }...
Question - modify the code below so that for a node, the value of every node...
Question - modify the code below so that for a node, the value of every node of its right subtree is less the node, and the value of each node of its left subtree is greater than the node. - create such a binary tree in the Main method, and call the following method: InOrder(Node theRoot), PreOrder(Node theRoot), PostOrder(Node theRoot), FindMin(), FindMax(), Find(int key) using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;...
C++ (Using Binary Search Trees) other methods will result in downvote Implement the binary search tree...
C++ (Using Binary Search Trees) other methods will result in downvote Implement the binary search tree methods (bst.cpp) for the binary search tree provided in the header file. Test your implementation with the included test. bst.h bst_test.cpp Note: Your implementation must correspond to declarations in the header file, and pass the test. Do not modify these two. I will compile your code against these. If the compilation fails, you will get down vote. bst.h #ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H #include <string>...
Most questions answered within 3 hours.
-
The blues made its way into many kinds of music. Eric Clapton,
The Beatles, and Elvis...
asked 7 minutes ago -
If you’re standing at the bottom of a hill and asked to evaluate
it while being...
asked 1 hour ago -
1. Which region has taken the lead in the world of
e-waste handling?
a) European Union...
asked 56 minutes ago -
A 8.15- g bullet from a 9-mm pistol has a velocity of 366.0 m/s.
It strikes...
asked 2 hours ago -
The outstanding bonds of Alpha Extracts have a yield to maturity
of 7.4 percent and a...
asked 2 hours ago -
The Problem: The Case of the Harmonizing Vacations
Your CEO is exploring partnering with a European...
asked 3 hours ago -
A chemical equation is balanced by adding coefficients in front
of some formulas so that the...
asked 3 hours ago -
From the literature (reference your sources): What are the
lattice parameters of calcite and aragonite? Why...
asked 4 hours ago -
Your system is rejecting the question am asking which is
preceded by a case study. It...
asked 4 hours ago -
3. On January 2, 2000, Larry creates a trust with himself as
trustee. Larry as trustee...
asked 4 hours ago -
A member of the volleyball team spikes the ball. During this
process, she changes the velocity...
asked 4 hours ago -
Are adult gamers less likely to use a gaming console (Xbox,
PlayStation, Wii, etc...) than teen...
asked 5 hours ago