Solved

C++ recursive templated Binary Tree help

Posted on 2007-11-20
9
436 Views
Last Modified: 2010-04-01
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
Comment
Question by:PMG76
9 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 20321918
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
 
LVL 20

Accepted Solution

by:
ikework earned 300 total points
ID: 20322160
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
 

Author Comment

by:PMG76
ID: 20322268
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
 
LVL 20

Assisted Solution

by:ikework
ikework earned 300 total points
ID: 20322462
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
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 20

Expert Comment

by:ikework
ID: 20322487
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
 

Author Comment

by:PMG76
ID: 20322511
it's a utility function.  Once I get the base code down I have to write two other programs from this code.
0
 
LVL 20

Expert Comment

by:ikework
ID: 20322533
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
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 200 total points
ID: 20322576
>>>> 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
 

Author Comment

by:PMG76
ID: 20322655
This is the code I have to implement.  I do as I'm told.
0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now