Binary tree coding please do c++ As you may recall, the implementation of the cs
ID: 3580947 • Letter: B
Question
Binary tree coding please do c++
As you may recall, the implementation of the cs20::BinaryTree< Object > data structure presented in class used a left-child/right-child node structure. Based on this data structure, write the following method:
template <class Object>
bool BinaryTree<Object>::cluster( Object o ) const throw( InvalidTreeArgument );
This method should determine if the tree has a cluster of Object o values. A cluster is when a node and both its immediate children have the same value. If the root of this BinaryTree is NULL, your code should throw an InvalidTreeArgument exception. Feel free to define any public or private methods or members on the class BinaryTree<Object> as you need. Please work with the code from class.
For example, please consider the tree show below:
cluster( 7 ) on this tree should return false because there are no nodes with the element value of seven.
However, when working with the following tree:
cluster( 5 ) on this tree should return true because the red-colored nodes are a cluster, all with the element value of five.
// Binary tree.cpp
#ifndef BINARYTREE_CPP
#define BINARYTREE_CPP
#include "BinaryTree.h"
namespace cs20 {
template <class Object>
BinaryTree<Object>::BinaryTree() {
root = nullptr;
}
template <class Object>
BinaryTreeNode<Object> * BinaryTree<Object>::getRoot() const {
return( root );
}
template <class Object>
BinaryTree<Object>::BinaryTree( const BinaryTree<Object>& rhs ) {
root = nullptr;
*this = rhs;
}
template <class Object>
BinaryTree<Object>::BinaryTree( const Object& rootElement ) {
root = new BinaryTreeNode<Object>( rootElement );
}
template <class Object>
BinaryTree<Object>::~BinaryTree() {
makeEmpty();
}
template <class Object>
bool BinaryTree<Object>::isEmpty() const {
return( root == nullptr );
}
template <class Object>
void BinaryTree<Object>::makeEmpty() {
makeEmpty( root );
}
template <class Object>
void BinaryTree<Object>::makeEmpty( NodePtr & node ) {
if (node != nullptr) {
NodePtr r = node->getRightSide();
NodePtr l = node->getLeftSide();
if (r != nullptr)
makeEmpty( r );
if (l != nullptr)
makeEmpty( l );
delete node;
node = nullptr;
}
}
template <class Object>
int BinaryTree<Object>::size() const {
return( BinaryTreeNode<Object>::size( root ) );
}
template <class Object>
int BinaryTree<Object>::height() const {
return( BinaryTreeNode<Object>::height( root ) );
}
template <class Object>
void BinaryTree<Object>::setRightSide( BinaryTree& theRightSide ) {
if (theRightSide.root == nullptr)
throw( InvalidTreeArgument() );
BinaryTreeNode<Object> *child = new BinaryTreeNode<Object>( theRightSide.root->getElement(),
theRightSide.root->getLeftSide(),
theRightSide.root->getRightSide() );
root->setRightSide( child );
if (child != theRightSide.root)
theRightSide.root = nullptr;
}
template <class Object>
void BinaryTree<Object>::setLeftSide( BinaryTree& theLeftSide ) {
if (theLeftSide.root == nullptr)
throw( InvalidTreeArgument() );
BinaryTreeNode<Object> *child = new BinaryTreeNode<Object>( theLeftSide.root->getElement(),
theLeftSide.root->getLeftSide(),
theLeftSide.root->getRightSide() );
root->setLeftSide( child );
if (child != theLeftSide.root)
theLeftSide.root = nullptr;
}
template <class Object>
void BinaryTree<Object>::merge( const Object& rootElement,
BinaryTree & left,
BinaryTree & right ) {
if ( left.root == right.root && left.root != nullptr ) {
std::cerr << "Cannot merge a tree with itself" << std::endl;
throw( InvalidTreeArgument() );
}
else {
NodePtr oldRoot = root;
root = new BinaryTreeNode<Object>( rootElement,
left.root,
right.root );
if (this != &left && this != &right)
makeEmpty( oldRoot );
if (this != &left)
left.root = nullptr;
if (this != &right)
right.root = nullptr;
}
}
// Deep copy of tree
template <class Object>
const BinaryTree<Object>& BinaryTree<Object>::operator =( const BinaryTree<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (rhs.root != nullptr)
root = rhs.root->duplicate();
}
return( *this );
}
template <class Object>
void BinaryTree<Object>::printTree( std::ostream& out ) const {
if (root == nullptr) {
out << "nullptr" << std::endl;
}
else {
printTree( root, out );
out << std::endl;
}
}
template <class Object>
void BinaryTree<Object>::printTree( NodePtr subtree, std::ostream & out ) const {
if (subtree == nullptr) {
out << "nullptr";
}
else {
out << subtree->getElement();
out << " ";
printTree( subtree->getLeftSide(), out );
out << " ";
printTree( subtree->getRightSide(), out );
out << " ";
}
}
}
#endif
// binarytree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <cstddef>
#include "BinaryTreeNode.h"
#include "InvalidTreeArgument.h"
namespace cs20 {
template <class Object>
class BinaryTreeIterator;
template <class Object>
class BinaryTree {
public:
BinaryTree();
BinaryTree( const Object& rootElement );
BinaryTree( const BinaryTree& rhs );
~BinaryTree();
bool isEmpty() const;
void makeEmpty();
int size() const;
int height() const;
void merge( const Object& rootElement,
BinaryTree& firstChild,
BinaryTree& nextSibling );
void setRightSide( BinaryTree& theRightSide );
void setLeftSide( BinaryTree& theLeftSide );
const BinaryTree& operator =( const BinaryTree& rhs );
// this is tremendously bad form but I had to do it
// to support the menu-based program
BinaryTreeNode<Object> * getRoot() const;
void printTree( std::ostream& out ) const;
private:
typedef BinaryTreeNode<Object>* NodePtr;
NodePtr root;
void makeEmpty( NodePtr &t );
friend class BinaryTreeIterator<Object>;
void printTree( NodePtr subtree, std::ostream & out ) const;
};
}
#endif
Explanation / Answer
#include <iostream>
#include <string.h>
#include "Binary_Tree.h"
using namespace std;
Binary_Tree::Binary_Tree()
{
root = NULL;
return;
}
Binary_Tree::~Binary_Tree()
{
ClearTree(root);
return;
}
void Binary_Tree::ClearTree(TreeNode *T)
{
if(T==NULL) return; // Nothing to clear
if(T->left != NULL) ClearTree(T->left); // Clear left sub-tree
if(T->right != NULL) ClearTree(T->right); // Clear right sub-tree
delete T; // Destroy this node
return;
}
/
bool Binary_Tree::isEmpty()
{
return(root==NULL);
}
TreeNode *Binary_Tree::DupNode(TreeNode * T)
{
TreeNode *dupNode;
dupNode = new TreeNode();
*dupNode = *T; // Copy the data structure
dupNode->left = NULL; // Set the pointers to NULL
dupNode->right = NULL;
return dupNode;
}
TreeNode *Binary_Tree::SearchTree(int Key)
{
int ValueInTree = false;
TreeNode *temp;
temp = root;
while((temp != NULL) && (temp->Key != Key))
{
if(Key < temp->Key)
temp = temp->left; // Search key comes before this node.
else
temp = temp->right; // Search key comes after this node
}
if(temp == NULL) return temp; // Search key not found
else
return(DupNode(temp)); // Found it so return a duplicate
}
bool Binary_Tree::Insert(TreeNode *newNode)
{
TreeNode *temp;
TreeNode *back;
temp = root;
back = NULL;
while(temp != NULL) // Loop till temp falls out of the tree
{
back = temp;
if(newNode->Key < temp->Key)
temp = temp->left;
else
temp = temp->right;
}
// Now attach the new node to the node that back points to
if(back == NULL) // Attach as root node in a new tree
root = newNode;
else
{
if(newNode->Key < back->Key)
back->left = newNode;
else
back->right = newNode;
}
return true ;
}
bool Binary_Tree::Insert(int Key, float f, int i, char *cA)
{
TreeNode *newNode;
// Create the new node and copy data into it
newNode = new TreeNode();
newNode->Key = Key;
newNode->fValue = f;
newNode->iValue = i;
strcpy(newNode->cArray, cA);
newNode->left = newNode->right = NULL;
// Call other Insert() to do the actual insertion
return(Insert(newNode));
}
bool Binary_Tree::Delete(int Key)
{
TreeNode *back;
TreeNode *temp;
TreeNode *delParent; // Parent of node to delete
TreeNode *delNode; // Node to delete
temp = root;
back = NULL;
// Find the node to delete
while((temp != NULL) && (Key != temp->Key))
{
back = temp;
if(Key < temp->Key)
temp = temp->left;
else
temp = temp->right;
}
if(temp == NULL) // Didn't find the one to delete
{
return false;
}
else
{
if(temp == root) // Deleting the root
{
delNode = root;
delParent = NULL;
}
else
{
delNode = temp;
delParent = back;
}
}
// Case 1: Deleting node with no children or one child
if(delNode->right == NULL)
{
if(delParent == NULL) // If deleting the root
{
root = delNode->left;
delete delNode;
return true;
}
else
{
if(delParent->left == delNode)
delParent->left = delNode->left;
else
delParent->right = delNode->left;
delete delNode;
return true;
}
}
else // There is at least one child
{
if(delNode->left == NULL) // Only 1 child and it is on the right
{
if(delParent == NULL) // If deleting the root
{
root = delNode->right;
delete delNode;
return true;
}
else
{
if(delParent->left == delNode)
delParent->left = delNode->right;
else
delParent->right = delNode->right;
delete delNode;
return true;
}
}
else // Case 2: Deleting node with two children
{
// Find the replacement value. Locate the node
// containing the largest value smaller than the
// key of the node being deleted.
temp = delNode->left;
back = delNode;
while(temp->right != NULL)
{
back = temp;
temp = temp->right;
}
// Copy the replacement values into the node to be deleted
delNode->Key = temp->Key;
delNode->fValue = temp->fValue;
delNode->iValue = temp->iValue;
strcpy(delNode->cArray, temp->cArray);
// Remove the replacement node from the tree
if(back == delNode)
back->left = temp->left;
else
back->right = temp->left;
delete temp;
return true;
}
}
}
void Binary_Tree::PrintOne(TreeNode *T)
{
cout << T->Key << " " << T->fValue << " " << T->iValue << " "
<< T->cArray << " ";
}
void Binary_Tree::PrintAll(TreeNode *T)
{
if(T != NULL)
{
PrintAll(T->left);
PrintOne(T);
PrintAll(T->right);
}
}
void Binary_Tree::PrintTree()
{
PrintAll(root);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.