Bookmark Please use the linked approach implement the BST ADT, implement all the

Question

Bookmark

Please use the linked approach implement the BST ADT, implement all the functions in the BSTree.cpp. Add the ouput of the implementation.

Please use C++ programming

//////////////////////////////////////////////////////////////

#include "BSTree.h"

template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )
{
}

template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ()
{
   root = 0;
}

template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ( const BSTree<DataType,KeyType>& other )
{
}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>:: copyTree(const BSTree<DataType, KeyType> &otherTree)
{
   copyTreeHelper(root, otherTree.root);
}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>:: copyTreeHelper(BSTreeNode *&p, const BSTreeNode *otherPtr)
{
   if (p != 0)
   {
       p = new BSTreeNode(otherPtr->dataItem, 0, 0);
       copyTreeHelper(p->left, otherPtr->left);
       copyTreeHelper(p->right, otherPtr->right);
   }
}

template < typename DataType, class KeyType >
BSTree<DataType, KeyType>& BSTree<DataType, KeyType>:: operator= ( const BSTree<DataType,KeyType>& other )
{

}

template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::~BSTree ()
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insert ( const DataType& newDataItem )
{

}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const
{
   return false;
}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::remove ( const KeyType& deleteKey )
{
   return false;
}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::removeHelper(BSTreeNode *&p, const KeyType& deleteKey)
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeys () const
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLTHelper(BSTreeNode *p, const KeyType& searchKey) const
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clear ()
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clearHelper(BSTreeNode *p)
{

}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::isEmpty () const
{
   return false;
}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeight () const
{
   return -1;
}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeightHelper(BSTreeNode *p) const
{

}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCount () const
{
   return -1;
}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCountHelper(BSTreeNode *p) const
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLessThan ( const KeyType& searchKey ) const
{
}

#include "show9.cpp"

/////////////////////////////////////////////////////////////////////////////////////////

Class declarations for the linked implementation of the Binary
// Search Tree ADT -- including the recursive helpers of the
// public member functions
//
//--------------------------------------------------------------------

#ifndef BSTREE_H
#define BSTREE_H

#include <stdexcept>
#include <iostream>

using namespace std;

template < typename DataType, class KeyType > // DataType : tree data item
class BSTree // KeyType : key field
{
public:

   // Constructor
   BSTree(); // Default constructor
   BSTree(const BSTree<DataType, KeyType>& other); // Copy constructor
   BSTree& operator= (const BSTree<DataType, KeyType>& other);
   // Overloaded assignment operator

   // Destructor
   ~BSTree();

   // Binary search tree manipulation operations
   void insert(const DataType& newDataItem); // Insert data item
   bool retrieve(const KeyType& searchKey, DataType& searchDataItem) const;
   // Retrieve data item
   bool remove(const KeyType& deleteKey); // Remove data item
   void writeKeys() const; // Output keys
   void clear(); // Clear tree

   // Binary search tree status operations
   bool isEmpty() const; // Tree is empty
   // !! isFull() has been retired. Not very useful in a linked structure.

   // Output the tree structure -- used in testing/debugging
   void showStructure() const;

   // In-lab operations
   int getHeight() const; // Height of tree
   int getCount() const;           // Number of nodes in tree
   void writeLessThan(const KeyType& searchKey) const; // Output keys < searchKey

protected:

   class BSTreeNode // Inner class: facilitator for the BSTree class
   {
   public:

       // Constructor
       BSTreeNode(const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr);

       // Data members
       DataType dataItem; // Binary search tree data item
       BSTreeNode *left, // Pointer to the left child
           *right; // Pointer to the right child
   };

   // Recursive helpers for the public member functions -- insert
   // prototypes of these functions here.
   void insertHelper(BSTreeNode *&p, const DataType &newDataItem);
   bool retrieveHelper(BSTreeNode *p, const KeyType& searchKey, DataType &searchDataItem) const;
   bool removeHelper(BSTreeNode *&p, const KeyType& deleteKey);
   // cutRightmose used in one implementation of remove.
   void cutRightmost(BSTreeNode *&r, BSTreeNode *&delPtr);
   void writeKeysHelper(BSTreeNode *p) const;
   void clearHelper(BSTreeNode *p);
   void showHelper(BSTreeNode *p, int level) const;
   int getHeightHelper(BSTreeNode *p) const;
   int getCountHelper(BSTreeNode *p) const;
   void writeLTHelper(BSTreeNode *p, const KeyType& searchKey) const;
   void copyTree(const BSTree<DataType, KeyType> &otherTree);
   void copyTreeHelper(BSTreeNode *&p, const BSTreeNode *otherPtr);

   // Data member
   BSTreeNode *root; // Pointer to the root node
};

#endif   // define BSTREE_H

Explanation / Answer

#include using namespace std; #include struct tree { tree *l, *r; int data; }*root = NULL, *p = NULL, *np = NULL, *q; void create() { int value,c = 0; while (c < 7) { if (root == NULL) { root = new tree; coutroot->data; root->r=NULL; root->l=NULL; } else { p = root; coutvalue; while(true) { if (value data) { if (p->l == NULL) { p->l = new tree; p = p->l; p->data = value; p->l = NULL; p->r = NULL; coutl; } } else if (value > p->data) { if (p->r == NULL) { p->r = new tree; p = p->r; p->data = value; p->l = NULL; p->r = NULL; coutr; } } } } c++; } } void inorder(tree *p) { if (p != NULL) { inorder(p->l); cout

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.