This is the header file for a Recursive Binary Search Tree

- I have never used recursion, not sure if I'm, using it right...
If you could tell me if this is the correct algorithm for recursion for this code, that would help alot.

-- also, I am not sure how to write the functions for the different styles for the print, any help with that would be great

--- finally, if you find any errors, if you could point them out to me that would be awesome

Thanks alot,
Ben

``````#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using namespace std;

template <class ItemType>
struct TreeNode
{
ItemType info;
TreeNode* left;
TreeNode* right;
};

template <class ItemType>
class TreeType
{
public:
TreeType();                                             // constructor
~TreeType();                                            // destructor
TreeType(const TreeType& originalTree);                 // copy constructor
void operator=(const TreeType& originalTree);           // assignment operator
void Clear();                                           // clear the 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 Find(ItemType& item, bool& found) const;                           // retrieve an item
void InsertItem(ItemType item);                         // insert an item
void DeleteItem(ItemType item);                         // delete an item
void PrintInOrder(std::ostream& outFile) const;         // print the tree in order
void PrintPreOrder(std::ostream& outFile) const;        // print the tree in preorder
void PrintPostOrder(std::ostream& outFile) const;       // print the tree in post order

private:
TreeNode* root;
void Destroy(TreeNode*& tree);
void CopyTree(TreeNode*& copy, const TreeNode* originalTree);
void Insert(TreeNode*& tree, ItemType item);
void DeleteNode(TreeNode*& tree);
void Delete(TreeNode*& tree, ItemType item);
int CountNodes(TreeNode* tree);
void Retrieve(TreeNode* tree, ItemType& item, bool& found);
}

//-----------------------------------------------------------------------------
//CONSTRUCTOR
//-----------------------------------------------------------------------------
template <class ItemType>
TreeType<ItemType>::TreeType()
{
root = NULL;
}

//-----------------------------------------------------------------------------
//DECONSTRUCTOR
//-----------------------------------------------------------------------------
void Destroy(TreeNode*& tree);

template <class ItemType>
TreeType<ItemType>::~TreeType()
{
destroy(root);
}

void Destroy(TreeNode*& tree)
{
if (tree != NULL)
{
Destroy(tree->left);
Destroy(tree->right);
delete tree;
}
}

//------------------------------------------------------------------------------
//COPY CONSTRUCTOR
//-----------------------------------------------------------------------------
void CopyTree(TreeNode*& copy, const TreeNode* originalTree);

template <class ItemType>
TreeType<ItemType>::TreeType(const TreeType& originalTree)
{
CopyTree(root, originalTree.root);
}

template <class ItemType>
void TreeType<ItemType>::operator=(const TreeType& originalTree)
{
if (&originalTree == this)
return;
Destroy(root);
CopyTree(root, originalTree.root);
}

void CopyTree(TreeNode*& copy, const TreeNode* originalTree)
{
if (originalTree == NULL)
copy = NULL;
else
{
copy = new TreeNode;
copy->info=originalTree->info;
CopyTree(copy->left, originalTree->left);
CopyTree(copy->right, originalTree->right);
}
}

//-----------------------------------------------------------------------------
//INSERT ITEM
//-----------------------------------------------------------------------------
void Insert(TreeNode*& tree, ItemType item);

template <class ItemType>
void TreeType<ItemType>::InsertItem(ItemType item)
{
Insert(root, item);
}

void Insert(TreeNode*& tree, ItemType item)
{
if (tree == NULL)
{
tree = new TreeNode;
tree->right = NULL;
tree->left = NULL;
tree->info = item;
}
else if (item < tree->info)
Insert(tree->left, item);
else
Insert(tree->right, item);
}

//-----------------------------------------------------------------------------
//DELETE ITEM
//-----------------------------------------------------------------------------
void DeleteNode(TreeNode*& tree);

void Delete(TreeNode*& tree, ItemType item);

template <class ItemType>
void TreeType<ItemType>::DeleteItem(ItemType item)
{
Delete(root, item);
}

void Delete(TreeNode*& tree, ItemType item)
{
if (item < tree->info)
Delete(tree->left, item);
else if (item > tree->info)
Delete(tree->right, item);
else
DeleteNode(tree);
}

//-----------------------------------------------------------------------------
//IS FULL
//-----------------------------------------------------------------------------
template <class ItemType>
bool TreeType<ItemType>::IsFull() const
{
TreeNode* location;

try
{
location = new TreeNode;
delete location;
return false;
}
{
return true;
}
}

//-----------------------------------------------------------------------------
//IS EMPTY
//-----------------------------------------------------------------------------
template <class ItemType>
bool TreeType<ItemType>::IsEmpty() const
{
return root == NULL;
}

//-----------------------------------------------------------------------------
//LENGTH IS
//-----------------------------------------------------------------------------
int CountNodes(TreeNode* tree);

template <class ItemType>
int TreeType<ItemType>::LengthIs() const
{
return CountNodes(root);
}

int CountNodes(TreeNode* tree)
{
if (tree == NULL)
return 0;
else
return CountNodes(tree->left)+CountNodes(tree->right)+1;
}
//-----------------------------------------------------------------------------
//FIND
//-----------------------------------------------------------------------------
void Retrieve(TreeNode* tree, ItemType& item, bool& found);
template <class ItemType>
void TreeType<ItemType>::Find(ItemType& item, bool& found) const
{
Retrieve(root, item, found)
}

void Retrieve(TreeNode* tree, ItemType& item, bool& found)
{
if (tree == NULL)
found = false;
else if (item < tree->info)
Retrieve(tree->left, item, found);
else if (item > tree->info)
Retrieve(tree->right, item, found);
else
{
item = tree->info;
found = true;
}
}
//-----------------------------------------------------------------------------
//Clear
//-----------------------------------------------------------------------------
template <class ItemType>
void TreeType<ItemType>::Clear()
{
~TreeType():
}

#endif``````

Well ! I don't think you don't know recursion, otherwise you wouldn't have such a good implementation :).

good efforts :).

let's have a expert look on that implementation, hope you'd agree.

I don't like you Copy Constructor's Syntax.

``void TreeType<ItemType>::operator=(const TreeType& originalTree);``

``````TreeType t1;
....// do some inserting in tree.
TreeType t2;
.... // do some insertion in tree2
TreeType t3;
// now the interesting part.
t3 = t2 = t1;               // what happened here? (if you require description post it).``````

next is the implementation. don't you think we need to swap these two calls.

``````92:    CopyTree(root, originalTree.root);
93:    Destroy(root);``````

The Code of isFull () doesn't check whether the tree is full or not.
Full tree has two childs or no childs. (its simple).

change the implementation of clear.

``````template <class ItemType>
void TreeType<ItemType>::Clear()
{
//         ~TreeType():
destroy(root);
}``````

why you are calling destructor in member function ?.
simply replace it with destroy(...).

few more check points are there but first change the above ones ?.
Hope it would help and again printing is simple
pre-order (check your copyTree Implementation (you are traversing the tree in pre-order)).
post-order (check your deleteTree implemenation (you are traversing the tree in post-order)).
last one is in-order. you can do it urself I guess.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.