Given the following code: #ifndef TREE_H #define TREE_H #include <iostream> #include "TreeNode.h" template< typename NODETYPE > class Tree { public: Tree() : rootPtr( nullptr ) {}...
Given the following code:
#ifndef TREE_H
#define TREE_H
#include <iostream>
#include "TreeNode.h"
template< typename NODETYPE >
class Tree
{
public:
Tree()
: rootPtr( nullptr ) {}
void insertNode( const NODETYPE &value )
{
insertNodeHelper( &rootPtr, value );
}
void preOrderTraversal() const
{
preOrderHelper( rootPtr );
}
void inOrderTraversal() const
{
inOrderHelper( rootPtr );
}
private:
TreeNode< NODETYPE > *rootPtr;
void insertNodeHelper(
TreeNode< NODETYPE > **ptr, const NODETYPE
&value )
{
if ( *ptr == nullptr )
* ptr = new TreeNode< NODETYPE >( value );
else
{
if ( value < ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
{
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
else
std::cout << value << " dup" << std::endl;
}
}
}
void preOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != nullptr )
{
std::cout << ptr->data << ' ';
preOrderHelper( ptr->leftPtr );
preOrderHelper( ptr->rightPtr );
}
}
void inOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != nullptr )
{
inOrderHelper( ptr->leftPtr );
std::cout << ptr->data << ' ';
inOrderHelper( ptr->rightPtr );
}
}
};
#endif
#ifndef TREENODE_H
#define TREENODE_H
template< typename NODETYPE > class Tree;
template< typename NODETYPE >
class TreeNode
{
friend class Tree< NODETYPE >;
public:
TreeNode( const NODETYPE &d )
: leftPtr( nullptr ),
data( d ),
rightPtr( nullptr )
{
}
NODETYPE getData() const
{
return data;
}
private:
TreeNode< NODETYPE > *leftPtr;
NODETYPE data;
TreeNode< NODETYPE > *rightPtr;
};
#endif
1. Add the following functions:
Post order traversal
countNodes
countLevels
Test your code in main.
Create a binary tree of type strings and test your code
Create a binary tree of type integers and test your code
Create a binary tree of cars and test your code
Homework Answers
// TreeNode.h
#ifndef TREENODE_H
#define TREENODE_H
template< typename NODETYPE > class Tree;
template< typename NODETYPE >
class TreeNode
{
friend class Tree< NODETYPE >;
public:
TreeNode( const NODETYPE &d )
: leftPtr( nullptr ),
data( d ),
rightPtr( nullptr )
{
}
NODETYPE getData() const
{
return data;
}
private:
TreeNode< NODETYPE > *leftPtr;
NODETYPE data;
TreeNode< NODETYPE > *rightPtr;
};
#endif
//end of TreeNode.h
// Tree.h
#ifndef TREE_H
#define TREE_H
#include <iostream>
#include "TreeNode.h"
template< typename NODETYPE >
class Tree
{
public:
Tree()
: rootPtr( nullptr ) {}
void insertNode( const NODETYPE &value )
{
insertNodeHelper( &rootPtr, value );
}
void preOrderTraversal() const
{
preOrderHelper( rootPtr );
}
void inOrderTraversal() const
{
inOrderHelper( rootPtr );
}
void postOrderTraversal() const
{
postOrderHelper(rootPtr);
}
int countNodes() const
{
return nodeCount(rootPtr);
}
int countLevels() const
{
return levels(rootPtr);
}
private:
TreeNode< NODETYPE > *rootPtr;
void insertNodeHelper(
TreeNode< NODETYPE > **ptr, const NODETYPE
&value )
{
if ( *ptr == nullptr )
* ptr = new TreeNode< NODETYPE >( value );
else
{
if ( value < ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
{
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
else
std::cout << value << " dup" << std::endl;
}
}
}
void preOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != nullptr )
{
std::cout << ptr->data << ' ';
preOrderHelper( ptr->leftPtr );
preOrderHelper( ptr->rightPtr );
}
}
void inOrderHelper( TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != nullptr )
{
inOrderHelper( ptr->leftPtr );
std::cout << ptr->data << ' ';
inOrderHelper( ptr->rightPtr );
}
}
void postOrderHelper(TreeNode< NODETYPE > *ptr ) const
{
if(ptr != nullptr)
{
postOrderHelper(ptr->leftPtr);
postOrderHelper(ptr->rightPtr);
std::cout << ptr->data << ' ';
}
}
int nodeCount(TreeNode<NODETYPE> *ptr) const
{
if (ptr == nullptr)
return 0;
else
return 1 + nodeCount(ptr->leftPtr) + nodeCount(ptr->rightPtr);
}
int levels(TreeNode<NODETYPE> *ptr) const
{
if (ptr == nullptr)
return 0;
else
{
int leftLevel = 1+levels(ptr->leftPtr);
int rightLevel = 1+ levels(ptr->rightPtr);
if(leftLevel > rightLevel)
return leftLevel;
else
return rightLevel;
}
}
};
#endif
//end of Tree.h
// main.cpp: C++ program to test the Tree class
#include "Tree.h"
#include <iostream>
using namespace std;
int main()
{
Tree<string> tree1;
tree1.insertNode("bob");
tree1.insertNode("phillip");
tree1.insertNode("alice");
tree1.insertNode("charlie");
cout<<"Inorder traversal : "<<endl;
tree1.inOrderTraversal();
cout<<"\nPreorder traversal : "<<endl;
tree1.preOrderTraversal();
cout<<"\nPostorder traversal : "<<endl;
tree1.postOrderTraversal();
cout<<"\nNumber of nodes : "<<tree1.countNodes()<<endl;
cout<<"\nNumber of levels : "<<tree1.countLevels()<<endl;
return 0;
}
//end of main.cpp
Output:
Add Answer to:
Given the following code: #ifndef TREE_H #define TREE_H #include <iostream> #include "TreeNode.h" template< typename NODETYPE > class Tree { public: Tree() : rootPtr( nullptr ) {}...
#ifndef HEAP_H_ #define HEAP_H_ namespace cse { template<typename dtype> class heap { public: /** TO DO::...
#ifndef HEAP_H_ #define HEAP_H_ namespace cse { template<typename dtype> class heap { public: /** TO DO:: default constructor perform new to reserve memory of size INITIAL_CAPACITY. set num_items = 0; */ heap() { // write your code here }; /** Create a heap from a given array */ heap(dtype *other, size_t len) { // write your code here }; /** copy constructor copy another heap to this heap. */ heap(const heap<dtype> &other) { //write your code here }; /** Accessor...
vector.h: #ifndef VECTOR_H #define VECTOR_H #include <algorithm> #include <iostream> #include <cassert> template <typename T> class Vector...
vector.h: #ifndef VECTOR_H #define VECTOR_H #include <algorithm> #include <iostream> #include <cassert> template <typename T> class Vector { public: Vector( int initsize = 0 ) : theSize( initsize ), theCapacity( initsize + SPARE_CAPACITY ) { objects = new T[ theCapacity ]; } Vector( const Vector & rhs ) : theSize( rhs.theSize), theCapacity( rhs.theCapacity ), objects( 0 ) { objects = new T[ theCapacity ]; for( int k = 0; k < theSize; ++k) objects[ k ] = rhs.objects[ k...
Binary Tree Template Write your own version of a class template that will create a binary...
Binary Tree Template Write your own version of a class template that will create a binary tree that can hold values of any data type. Demonstrate the class with a driver program. Place your binary tree template in it's own header file, Btree.h. Include methods for the following: inserting new values into the tree removing nodes from the tree searching the tree returning the number of nodes in the tree displaying the contents of the tree using preorder traversal Your...
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...
Consider the class specifications for the Binary Tree class and BinarySearch Tree class below: // Binary...
Consider the class specifications for the Binary Tree class and BinarySearch Tree class below: // Binary Tree.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 Binary Tree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); -Binary Tree(): bool is Empty() const; virtual bool search(const elemTypes searchItem) const = 0; virtual void insert(const elemTypek insertItem) =...
Use a B-Tree to implement the set.h class. #ifndef MAIN_SAVITCH_SET_H #define MAIN_SAVITCH_SET_H #include <cstdlib> // Provides...
Use a B-Tree to implement the set.h class. #ifndef MAIN_SAVITCH_SET_H #define MAIN_SAVITCH_SET_H #include <cstdlib> // Provides size_t namespace main_savitch_11 { template <class Item> class set { public: // TYPEDEFS typedef Item value_type; // CONSTRUCTORS and DESTRUCTOR set( ); set(const set& source); ~set( ) { clear( ); } // MODIFICATION MEMBER FUNCTIONS void operator =(const set& source); void clear( ); bool insert(const Item& entry); std::size_t erase(const Item& target); // CONSTANT MEMBER FUNCTIONS std::size_t count(const Item& target) const; bool empty( ) const...
Double linked list implementation of PutItem function. How to fix my code to get desired output b...
Double linked list implementation of PutItem function. How to fix my code to get desired output below: Output: 2 5 8 #ifndef ITEMTYPE_H #define ITEMTYPE_H enum RelationType { LESS, GREATER, EQUAL}; class ItemType { public: ItemType(); void setValue(int newValue); int getValue() const; RelationType ComparedTo(ItemType newItem); private: int value; }; #endif // ITEMTYPE_H // ItemType.cpp #include "ItemType.h" ItemType::ItemType() { value = 0; } void ItemType::setValue(int newValue) { value = newValue; } int ItemType::getValue() const { return value; } RelationType ItemType::ComparedTo(ItemType newItem)...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to...
What is the specific answer for 1. and 2. Thanks! Add a new method, find, to class SinglyLinkedList (defined here) that takes as input a “data” value and returns a pointer to a node. If the input data is present in the linked list, the returned pointer should point to that node; if not, the returned pointer is nullptr. Write the (single line) method declaration/specification. Write the method definition/implementation. Test by running the main() function below and capture the console...
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)...
In C++, for the provided template linked list class create a derived class of it which...
In C++, for the provided template linked list class create a derived class of it which adds the functionality to it to find the high and low value of any given data stored in the list. The derived class must be a template. LinkedList.h #pragma once #include <iostream> using namespace std; template <class T> class ListNode { public: T data; ListNode<T>* next; ListNode(T data) { this->data = data;...
Consider the class specifications for the Binary Tree class and BinarySearch Tree class below: // Binary Tree.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 Binary Tree { protected: TreeNode<elemType> *root; public: BinaryTree(); BinaryTreel const BinaryTree<elemType>& otherTree); -Binary Tree(): bool is Empty() const; virtual bool search(const elemTypes searchItem) const = 0; virtual void insert(const elemTypek insertItem) =...
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.
-
284 mL of a 0.52 M potassium hydroxide solution is added to 467
mL of a...
asked 5 minutes ago -
exercise on VSEPR and molecular structrue.
octahedral
SeCl62-
TeCl62-
ClF62-
distorted
SeF62–
IF6–
asked 6 minutes ago -
Little’s Law: Val d’Costa is a world famous ski village in the
French Alps. Because of...
asked 58 minutes ago -
Find the absolute error D for the calculation if A + B/C=D A=
9.4 +/- 0.4...
asked 1 hour ago -
New Air Heating and Cooling, manufactures furnaces and central
air units. The company pride itself on...
asked 1 hour ago -
A coach uses a new technique to train gymnasts. Seven
gymnasts were randomly selected and their...
asked 3 hours ago -
While rotating the tires on your car you notice a rock [mass =
0.1 Kg] stuck...
asked 5 hours ago -
Using MARS simulator, write MIPS programs according to
the following scenarios: Receive a positive integer number...
asked 7 hours ago -
An object in front of a concave mirror has a real image that is
11.5 cm...
asked 7 hours ago -
Consider the reaction, C3 H8 + O2 --> CO2 + H2O. How many
moles of O2...
asked 9 hours ago -
You and your opponent both roll a fair die. If you both roll the
same number,...
asked 9 hours ago -
In a study of the accuracy of fast food drive-through orders,
Restaurant A had 257 accurate...
asked 9 hours ago