?
Solved

C++ recursive templated Binary Tree help

Posted on 2007-11-20
9
Medium Priority
?
444 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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 1200 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 20

Assisted Solution

by:ikework
ikework earned 1200 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
 
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 800 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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

765 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