[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 447
  • Last Modified:

C++ recursive templated Binary Tree help

OK, this program is HW and I know the rules that go with that.  Needless to say, I'm completely stumped right now. I have most of my functions blocked out that I think I'll need.  A few were provided, but the rest I had to dream up.  I'm lost of where to start at this point.  I've never had a program with so many methods to test.  I'd appreciate any help in getting this started because I'm sure it's not going to be a fun task.

Here is what I have no far, not a whole lot actually written.  But it's a start.


#ifndef RTREE_TYPE
#define RTREE_TYPE

#include <iomanip>
using std::setw;
using std::endl;
#include <fstream>
using std::ofstream;
using std::ifstream;
#include <iostream>
using std::cin;
using std::cout;

template <class ItemType>
class RTreeType
{
        public:
                RTreeType();                                // constructor
                ~RTreeType();                               // destructor
                RTreeType(const RTreeType& originalTree);   // copy constructor
                void operator=(const RTreeType& originalTree); // assignment operator
                void MakeEmpty();                           // Clears tree
                bool IsEmpty() const;                       // test for empty tree
                bool IsFull() const;                        // test for full tree
                int  LengthIs() const;                      // return number of items in tree
                void RetrieveItem(ItemType& item, bool& found); // retrieve an item

                void InsertItem(ItemType item);             // insert an item
                void DeleteItem(ItemType item);             // delete an item
                void PrintTree(std::ostream& outFile) const; // print the tree in order
                void PrintPreOrder(std::ostream& outFile) const; // print the tree in pre-order
                void PrintPostOrder(std::ostream& outFile) const; // print the tree in post-order

                // Program 5:------------------------------------
                void OutputTree (std::ostream& outFile) const;
                // display the tree on the screen in tree form

                bool SaveToFile ();                         // save tree to file
                bool BuildFromFile();                       // build tree from file

        private:

                struct NodeType {
                        ItemType info;
                        NodeType* left;
                        NodeType* right;
                };
                NodeType * root;

                // Utility functions
                void Insert(NodeType*& tree, ItemType item);
                int  CountNodes(NodeType* tree) const;
                void Retrieve(NodeType* tree, ItemType& item, bool& found);
                void GetPredecessor(NodeType* tree, ItemType& data);
                void Delete(NodeType*& tree, ItemType item);
                void Destroy(NodeType*& tree);
                void CopyTree(NodeType*& copy, const NodeType* originalTree);
                void FindNode(NodeType* tree, ItemType item,
                                NodeType*& nodePtr, NodeType*& parentPtr);
                void DeleteNode(NodeType*& tree);
                void Print( NodeType* tree, std::ostream& outFile) const;
                void PreOrder (NodeType * tree, std::ostream& outFile) const;
                void PostOrder (NodeType * tree, std::ostream& outFile) const;

                // Program 5
                void ScreenPrint (std::ostream& outFile, NodeType* tree, int spaces) const;
};


//----------------------------------------------------------------------------------
//

                RTreeType();                                // constructor
               
                //
                ~RTreeType();                               // destructor
               
                //
                RTreeType(const RTreeType& originalTree);   // copy constructor
               
               
                //void operator=(const RTreeType& originalTree); // assignment operator
               
               
                //
                void MakeEmpty();                           // Clears tree
               
               
                //
                bool IsEmpty() const;                       // test for empty tree
               
               
                //
                bool IsFull() const;                        // test for full tree
               
               
               
                //
                int  LengthIs() const;                      // return number of items in tree
               
               
               
               
               
                //
                void RetrieveItem(ItemType& item, bool& found); // retrieve an item

               
               
                //
                void InsertItem(ItemType item);             // insert an item
               
               
               
                //
                void DeleteItem(ItemType item);             // delete an item
               
               
                //
                void PrintTree(std::ostream& outFile) const; // print the tree in order
               
               
               
                //
                void PrintPreOrder(std::ostream& outFile) const; // print the tree in pre-order
               
               
               
                //
                void PrintPostOrder(std::ostream& outFile) const; // print the tree in post-order

                // Program 5:------------------------------------
                void OutputTree (std::ostream& outFile) const;
                // display the tree on the screen in tree form

               
               
                //
                bool SaveToFile ();                         // save tree to file
               
               
               
                //
                bool BuildFromFile();                       // build tree from file



                // Utility functions
                //
                void Insert(NodeType*& tree, ItemType item);
               
               
               
                //
                int  CountNodes(NodeType* tree) const;
               
               
               
               
                //
                void Retrieve(NodeType* tree, ItemType& item, bool& found);
               
               
               
               
               
               
                //
                void GetPredecessor(NodeType* tree, ItemType& data);
               
               
               
               
               
                //
                void Delete(NodeType*& tree, ItemType item);
               
               
               
               
               
                //
                void Destroy(NodeType*& tree);
               
               
               
                //
                void CopyTree(NodeType*& copy, const NodeType* originalTree);
               
               
               
               
                //                
                void FindNode(NodeType* tree, ItemType item,
                                NodeType*& nodePtr, NodeType*& parentPtr);
               

               
                //
                void DeleteNode(NodeType*& tree);
               
               
               
                //void Print( NodeType* tree, std::ostream& outFile) const;
               
               
               
                //
                void PreOrder (NodeType * tree, std::ostream& outFile) const;
               
               
               
               
                //
                void PostOrder (NodeType * tree, std::ostream& outFile) const;

                // Program 5
                void ScreenPrint (std::ostream& outFile, NodeType* tree, int spaces) const;


#endif
0
PMG76
Asked:
PMG76
3 Solutions
 
Infinity08Commented:
One piece of advice : take one method at a time, and test it before moving on. Start with the most basic ones (like constructors, destructors, output methods, etc.), then tackle the functional methods (like insert, delete etc.).

Let us know where exactly you are stuck, and we'll help you with that.
0
 
ikeworkCommented:
dont worry .. most of the funcs are basically implemented in the same way .. once you understood how to traverse the tree its not a big deal anymore and you jump from one func to another .. ;)

and keep im mind what infinity said, one after another .. so lets start with insert, you can show us your idea ..
0
 
PMG76Author Commented:
Here's where I'm at right now:

#ifndef RTREE_TYPE
#define RTREE_TYPE

#include <iomanip>
using std::setw;
using std::endl;
#include <fstream>
using std::ofstream;
using std::ifstream;
#include <iostream>
using std::cin;
using std::cout;

template <class ItemType>
class RTreeType
{
    public:
        RTreeType();                                // constructor
        ~RTreeType();                               // destructor
        RTreeType(const RTreeType& originalTree);   // copy constructor
        void operator=(const RTreeType& originalTree); // assignment operator
        void MakeEmpty();                           // Clears tree
        bool IsEmpty() const;                       // test for empty tree
        bool IsFull() const;                        // test for full tree
        int  LengthIs() const;                      // return number of items in tree
        void RetrieveItem(ItemType& item, bool& found); // retrieve an item

        void InsertItem(ItemType item);             // insert an item
        void DeleteItem(ItemType item);             // delete an item
        void PrintTree(std::ostream& outFile) const; // print the tree in order
        void PrintPreOrder(std::ostream& outFile) const; // print the tree in pre-order
        void PrintPostOrder(std::ostream& outFile) const; // print the tree in post-order

        // Program 5:------------------------------------
        void OutputTree (std::ostream& outFile) const;
        // display the tree on the screen in tree form

        bool SaveToFile ();                         // save tree to file
        bool BuildFromFile();                       // build tree from file

    private:

        struct NodeType {
            ItemType info;
            NodeType* left;
            NodeType* right;
        };
        NodeType * root;

        // Utility functions
        void Insert(NodeType*& tree, ItemType item);
        int  CountNodes(NodeType* tree) const;
        void Retrieve(NodeType* tree, ItemType& item, bool& found);
        void GetPredecessor(NodeType* tree, ItemType& data);
        void Delete(NodeType*& tree, ItemType item);
        void Destroy(NodeType*& tree);
        void CopyTree(NodeType*& copy, const NodeType* originalTree);
        void FindNode(NodeType* tree, ItemType item,
                NodeType*& nodePtr, NodeType*& parentPtr);
        void DeleteNode(NodeType*& tree);
        void Print( NodeType* tree, std::ostream& outFile) const;
        void PreOrder (NodeType * tree, std::ostream& outFile) const;
        void PostOrder (NodeType * tree, std::ostream& outFile) const;

        // Program 5
        void ScreenPrint (std::ostream& outFile, NodeType* tree, int spaces) const;
};


//----------------------------------------------------------------------------------
//

    template <class ItemType>
RTreeType<ItemType>::RTreeType()                                // constructor
{
    root == NULL ;                
}

template <class ItemType>
//RTreeType<ItemType>::~RTreeType()                               // destructor


template <class ItemType>
//RTreeType<ItemType>::RTreeType(const RTreeType& originalTree)   // copy constructor


template <class ItemType>
//void RTreeType<ItemType>::operator=(const RTreeType& originalTree) // assignment operator



template <class ItemType>
//void RTreeType<ItemType>::MakeEmpty()                           // Clears tree


template <class ItemType>
bool RTreeType<ItemType>::IsEmpty() const                       // test for empty tree
{
    return ( root == NULL)
}

//   template <class ItemType>
//   bool RTreeType<ItemType>::IsFull() const                        // test for full tree




template <class ItemType>
int RTreeType<ItemType>::LengthIs() const                      // return number of items in tree
{
    int count = CountNodes(root);
    return count;
}



// template <class ItemType>
//void RTreeType<ItemType>::RetrieveItem(ItemType& item, bool& found) // retrieve an item




    template <class ItemType>
void RTreeType<ItemType>::InsertItem(ItemType item)             // insert an item
{
    Insert(root, item)
    {


        //  template <class ItemType>
        //void RTreeType<ItemType>::DeleteItem(ItemType item)             // delete an item



        //template <class ItemType>
        //void RTreeType<ItemType>::PrintTree(std::ostream& outFile) const // print the tree in order




        //template <class ItemType>
        //void RTreeType<ItemType>::PrintPreOrder(std::ostream& outFile) const // print the tree in pre-order




        // template <class ItemType>
        // void RTreeType<ItemType>::PrintPostOrder(std::ostream& outFile) const // print the tree in post-order

        // Program 5:------------------------------------
        //template <class ItemType>
        //void RTreeType<ItemType>::OutputTree (std::ostream& outFile) const
        // display the tree on the screen in tree form




        // template <class ItemType>
        //bool RTreeType<ItemType>::SaveToFile ()                         // save tree to file




        //  template <class ItemType>
        //bool RTreeType<ItemType>::BuildFromFile()                       // build tree from file



        // Utility functions
       
         template <class ItemType>
        void RTreeType<ItemType>::Insert(NodeType*& tree, ItemType item)
        {
            if(tree == NULL)
            {
                tree = new TreeNode;
                tree->right = NULL;
                tree->left==NULL;
                tree->info=Item;
            }
            else if ( item ==tree->info)
                return;
            else if (item < tree->info)
                Insert(tree_.left, item);
            else
                Insert(tree->right, item);
        }


        //  
        template <class ItemType>
            int RTreeType<ItemType>::CountNodes(NodeType* tree) const
            {


                //
                //template <class ItemType>
                //void RTreeType<ItemType>::Retrieve(NodeType* tree, ItemType& item, bool& found)





                //
                //  template <class ItemType>
                //void RTreeType<ItemType>::GetPredecessor(NodeType* tree, ItemType& data)





                //
                //  template <class ItemType>
                //void RTreeType<ItemType>::Delete(NodeType*& tree, ItemType item)





                //
                //  template <class ItemType>
                //void RTreeType<ItemType>::Destroy(NodeType*& tree)



                //
                //  template <class ItemType>
                //void RTreeType<ItemType>::CopyTree(NodeType*& copy, const NodeType* originalTree)




                //                
                //  template <class ItemType>
                //void RTreeType<ItemType>::FindNode(NodeType* tree, ItemType item,
                //      NodeType*& nodePtr, NodeType*& parentPtr)



                //
                //template <class ItemType>
                //void RTreeType<ItemType>::DeleteNode(NodeType*& tree)


                //
                //  template <class ItemType>
                //void RTreeType<ItemType>::Print( NodeType* tree, std::ostream& outFile) const



                //
                //template <class ItemType>
                //void RTreeType<ItemType>::PreOrder (NodeType * tree, std::ostream& outFile) const




                //
                //template <class ItemType>
                //void RTreeType<ItemType>::PostOrder (NodeType * tree, std::ostream& outFile) const

                // Program 5
                //template <class ItemType>
                // void RTreeType<ItemType>::ScreenPrint (std::ostream& outFile, NodeType* tree, int spaces) const


#endif
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
ikeworkCommented:
you dont have to paste the full-code .. the block of interest is just fine .. :)

start with:

void InsertItem(ItemType item);             // insert an item

inserting the first is easy, you can detect its the first, when "NULL == root". then you just have to allocate memory for a new node and assign it to "root". set the members of the node properly (next,prev and item) .. thats it .. ;)
0
 
ikeworkCommented:
is

void Insert(NodeType*& tree, ItemType item);

meant to be on the global scope or a member of class RTreeType? if its a member, why do you have two insert-functions?
0
 
PMG76Author Commented:
it's a utility function.  Once I get the base code down I have to write two other programs from this code.
0
 
ikeworkCommented:
what do you mean with "it's a utility function. "  you have two insert-functions ..

what are they supposed to do? the first in contrast to the second?
0
 
itsmeandnobodyelseCommented:
>>>> I've never had a program with so many methods to test.
It is not so dramatic. Try to find a non-trivial comment for each function and all will solve easily ;-)

e. g.

  // find out whether the list is empty by checking the root node for NULL
  bool isEmpty()
  {
         return root == NULL;
  }

The above tells you some more details, e. g. that the constructor has to initialize the 'root' with NULL. Or that when removing the last node in MakeEmpty() or DeleteItem() you have to set it to NULL.

After that you maybe should start with the most important func, which undoubtedly is the 'insert' function. You will have to iterate the existing tree to find the node where you have to add a new left or right node. You'll see that it can be done by using a outer while loop and an if statement:

       while (currentnode != NULL)
       {
              parentnode = currentnode;
              if (newnode->data  <  currentnode->data)
                     currentnode = currentnode->left;
              else
                     currentnode = currentnode->right;
        }

and that this kind of iteration is used for 'find' and 'delete' and 'iterative' functions as well ....

Regards, Alex
0
 
PMG76Author Commented:
This is the code I have to implement.  I do as I'm told.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now