C++: PLEASE HELP Implement the insert(V x) method- The tree should be sorted, th
ID: 3712871 • Letter: C
Question
C++: PLEASE HELP
Implement the insert(V x) method-
The tree should be sorted, the values of left subtree are smaller than the root; the values of the right subtree are larger than the root
treenode.h(given)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
template <class T>
class TreeNode{
T datum;
TreeNode<T>* left, * right;
public:
// constructor with datum value, left and right are nullptr
TreeNode(T x){
datum=x;
left = nullptr;
right = nullptr;
}
// constructor with datum value, left and right values
TreeNode(T x, TreeNode<T>* lft, TreeNode<T>* rgt){
datum = x;
left = lft;
right = rgt;
}
//destructor releases left and right nodes, if not nullptr
~TreeNode(){
if (left) {
delete left;
}
if (right) {
delete right;
}
}
// get datum value
T getDatum(){
return datum;
}
// get left pointer
TreeNode<T>* getLeft(){
return left;
}
// get right pointer
TreeNode<T>* getRight(){
return right;
}
// set the left pointer
void setLeft(TreeNode<T>* p){
left = p;
}
// set the right pointer
void setRight(TreeNode<T>* p){
right = p;
}
};
tree.h (implement insert method here)
#include "treeNode.h"
#include <iomanip>
template <class V>
class tree {
TreeNode<V> * root;
int size;
public:
// default constructor
// by default, the tree is empty
tree(){
root = nullptr;
size = 0;
}
// search value x in tree rooted at node t
bool treeSearch(V x, TreeNode<V>* t){
if(t == nullptr) return false;
if(t->getDatum() == x) return true;
return treeSearch(x, t->getLeft()) || treeSearch(x, t->getRight());
}
bool treeSearch(V x){
treeSearch(x, root);
}
// binary search value x in tree rooted at node t
bool treeBSearch(V x, TreeNode<V>* t){
if(t == nullptr) return false;
if(t->getDatum() == x) return true;
if(t->getDatum() > x)
return treeBSearch(x, t->getLeft());
else
return treeBSearch(x, t->getRight());
}
bool treeBSearch(V x){
return treeBSearch(x, root);
}
// check node t is leaf
bool isLeaf(TreeNode<V>* t){
return t!= nullptr && t->getLeft() == nullptr && t->getRight() == nullptr;
//implement this method
//return t!= nullptr && t->getLeft() == nullptr && t->getRight() == nullptr;
}
// find the height of the tree rooted at node t
int height(TreeNode<V>* t){
//implement this method
if(t == nullptr) return -1;
if(isLeaf(t)) return 0;
return 1 + std::max(height(t->getLeft()),height(t->getRight()));
}
int height(){
return height(root);
}
// find the number of nodes of tree rooted at t
int nNodes(TreeNode<V>* t){
if(t == nullptr) return 0;
return 1 + nNode(t->getLeft() + nNode(t->getRight()));
}
int nNodes(){
return nNodes(root);
}
// insert value x to the current tree object
void insert(V x){
~~~~~~~~~~
}
Explanation / Answer
Give below is the completed code for the question.
Please do rate the answer if it helped. Thank you
#include "treeNode.h"
#include <iomanip>
template <class V>
class tree {
TreeNode<V> * root;
int size;
public:
// default constructor
// by default, the tree is empty
tree(){
root = nullptr;
size = 0;
}
// search value x in tree rooted at node t
bool treeSearch(V x, TreeNode<V>* t){
if(t == nullptr) return false;
if(t->getDatum() == x) return true;
return treeSearch(x, t->getLeft()) || treeSearch(x, t->getRight());
}
bool treeSearch(V x){
treeSearch(x, root);
}
// binary search value x in tree rooted at node t
bool treeBSearch(V x, TreeNode<V>* t){
if(t == nullptr) return false;
if(t->getDatum() == x) return true;
if(t->getDatum() > x)
return treeBSearch(x, t->getLeft());
else
return treeBSearch(x, t->getRight());
}
bool treeBSearch(V x){
return treeBSearch(x, root);
}
// check node t is leaf
bool isLeaf(TreeNode<V>* t){
return t!= nullptr && t->getLeft() == nullptr && t->getRight() == nullptr;
//implement this method
//return t!= nullptr && t->getLeft() == nullptr && t->getRight() == nullptr;
}
// find the height of the tree rooted at node t
int height(TreeNode<V>* t){
//implement this method
if(t == nullptr) return -1;
if(isLeaf(t)) return 0;
return 1 + std::max(height(t->getLeft()),height(t->getRight()));
}
int height(){
return height(root);
}
// find the number of nodes of tree rooted at t
int nNodes(TreeNode<V>* t){
if(t == nullptr) return 0;
return 1 + nNode(t->getLeft() + nNode(t->getRight()));
}
int nNodes(){
return nNodes(root);
}
// insert value x to the current tree object
void insert(V x){
TreeNode<V>* t = new TreeNode<V>(x);
if(root == nullptr)
{
root = t;
size = 1;
return;
}
TreeNode<V> *curr = root;
while(curr != nullptr)
{
if(x < curr->getDatum())
{
if(curr->getLeft() == nullptr)
{
curr->setLeft(t);
size++;
break;
}
else
curr = curr->getLeft();
}
else
{
if(curr->getRight() == nullptr)
{
curr->setRight(t);
break;
}
else
curr = curr->getRight();
}
}
size++;
}
void printInOrder(TreeNode<V>* t)
{
if(t == nullptr)
return;
printInOrder(t->getLeft());
cout << t->getDatum() << endl;
printInOrder(t->getRight());
}
void printInOrder()
{
printInOrder(root);
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.