Recursive Binary Search Tree Header File

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Apr 2008
Posts: 11
Reputation: kse989 is an unknown quantity at this point 
Solved Threads: 0
kse989 kse989 is offline Offline
Newbie Poster

Recursive Binary Search Tree Header File

 
0
  #1
May 1st, 2008
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

CPP Syntax (Toggle Plain Text) 
  1. #ifndef QUEUE_H
  2. #define QUEUE_H
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. template <class ItemType>
  7. struct TreeNode
  8. {
  9.         ItemType info;
  10.         TreeNode* left;
  11.         TreeNode* right;
  12. };
  13.  
  14.  
  15. template <class ItemType>
  16. class TreeType
  17. {
  18.     public:
  19.         TreeType();                                             // constructor
  20.         ~TreeType();                                            // destructor
  21.         TreeType(const TreeType& originalTree);                 // copy constructor
  22.         void operator=(const TreeType& originalTree);           // assignment operator
  23.         void Clear();                                           // clear the tree
  24.         bool IsEmpty() const;                                   // test for empty tree
  25.         bool IsFull() const;                                    // test for full tree
  26.         int  LengthIs() const;                                  // return number of items in tree
  27.         void Find(ItemType& item, bool& found) const;                           // retrieve an item
  28.         void InsertItem(ItemType item);                         // insert an item
  29.         void DeleteItem(ItemType item);                         // delete an item
  30.         void PrintInOrder(std::ostream& outFile) const;         // print the tree in order
  31.         void PrintPreOrder(std::ostream& outFile) const;        // print the tree in preorder
  32.         void PrintPostOrder(std::ostream& outFile) const;       // print the tree in post order
  33.  
  34.    private:
  35.         TreeNode* root;
  36.         void Destroy(TreeNode*& tree);
  37.         void CopyTree(TreeNode*& copy, const TreeNode* originalTree);
  38.         void Insert(TreeNode*& tree, ItemType item);
  39.         void DeleteNode(TreeNode*& tree);
  40.         void Delete(TreeNode*& tree, ItemType item);
  41.         int CountNodes(TreeNode* tree);
  42.         void Retrieve(TreeNode* tree, ItemType& item, bool& found);
  43. }
  44.  
  45. //-----------------------------------------------------------------------------
  46.         //CONSTRUCTOR
  47. //-----------------------------------------------------------------------------
  48. template <class ItemType>
  49. TreeType<ItemType>::TreeType()
  50. {
  51.         root = NULL;
  52. }
  53.  
  54.  
  55. //-----------------------------------------------------------------------------
  56.         //DECONSTRUCTOR
  57. //-----------------------------------------------------------------------------
  58. void Destroy(TreeNode*& tree);
  59.  
  60. template <class ItemType>
  61. TreeType<ItemType>::~TreeType()
  62. {
  63.         destroy(root);
  64. }
  65.  
  66. void Destroy(TreeNode*& tree)
  67. {
  68.         if (tree != NULL)
  69.         {
  70.                 Destroy(tree->left);
  71.                 Destroy(tree->right);
  72.                 delete tree;
  73.         }
  74. }
  75.  
  76. //------------------------------------------------------------------------------
  77.         //COPY CONSTRUCTOR
  78. //-----------------------------------------------------------------------------
  79. void CopyTree(TreeNode*& copy, const TreeNode* originalTree);
  80.  
  81. template <class ItemType>
  82. TreeType<ItemType>::TreeType(const TreeType& originalTree)
  83. {
  84.         CopyTree(root, originalTree.root);
  85. }
  86.  
  87. template <class ItemType>
  88. void TreeType<ItemType>::operator=(const TreeType& originalTree)
  89. {
  90.         if (&originalTree == this)
  91.                 return;
  92.         Destroy(root);
  93.         CopyTree(root, originalTree.root);
  94. }
  95.  
  96. void CopyTree(TreeNode*& copy, const TreeNode* originalTree)
  97. {
  98.         if (originalTree == NULL)
  99.                 copy = NULL;
  100.         else
  101.         {
  102.                 copy = new TreeNode;
  103.                 copy->info=originalTree->info;
  104.                 CopyTree(copy->left, originalTree->left);
  105.                 CopyTree(copy->right, originalTree->right);
  106.         }
  107. }
  108.  
  109. //-----------------------------------------------------------------------------
  110.         //INSERT ITEM
  111. //-----------------------------------------------------------------------------
  112. void Insert(TreeNode*& tree, ItemType item);
  113.  
  114. template <class ItemType>
  115. void TreeType<ItemType>::InsertItem(ItemType item)
  116. {
  117.         Insert(root, item);
  118. }
  119.  
  120. void Insert(TreeNode*& tree, ItemType item)
  121. {
  122.         if (tree == NULL)
  123.         {
  124.                 tree = new TreeNode;
  125.                 tree->right = NULL;
  126.                 tree->left = NULL;
  127.                 tree->info = item;
  128.         }
  129.         else if (item < tree->info)
  130.                 Insert(tree->left, item);
  131.         else
  132.                 Insert(tree->right, item);
  133. }
  134.  
  135. //-----------------------------------------------------------------------------
  136.         //DELETE ITEM
  137. //-----------------------------------------------------------------------------
  138. void DeleteNode(TreeNode*& tree);
  139.  
  140. void Delete(TreeNode*& tree, ItemType item);
  141.  
  142. template <class ItemType>
  143. void TreeType<ItemType>::DeleteItem(ItemType item)
  144. {
  145.         Delete(root, item);
  146. }
  147.  
  148. void Delete(TreeNode*& tree, ItemType item)
  149. {
  150.         if (item < tree->info)
  151.                 Delete(tree->left, item);
  152.         else if (item > tree->info)
  153.                 Delete(tree->right, item);
  154.         else
  155.                 DeleteNode(tree);
  156. }
  157.  
  158. //-----------------------------------------------------------------------------
  159.         //IS FULL
  160. //-----------------------------------------------------------------------------
  161. template <class ItemType>
  162. bool TreeType<ItemType>::IsFull() const
  163. {
  164.         TreeNode* location;
  165.  
  166.         try
  167.         {
  168.                 location = new TreeNode;
  169.  delete location;
  170.                 return false;
  171.         }
  172.         catch(std::bad_alloc exception)
  173.         {
  174.                 return true;
  175.         }
  176. }
  177.  
  178. //-----------------------------------------------------------------------------
  179.         //IS EMPTY
  180. //-----------------------------------------------------------------------------
  181. template <class ItemType>
  182. bool TreeType<ItemType>::IsEmpty() const
  183. {
  184.         return root == NULL;
  185. }
  186.  
  187. //-----------------------------------------------------------------------------
  188.         //LENGTH IS
  189. //-----------------------------------------------------------------------------
  190. int CountNodes(TreeNode* tree);
  191.  
  192. template <class ItemType>
  193. int TreeType<ItemType>::LengthIs() const
  194. {
  195.         return CountNodes(root);
  196. }
  197.  
  198. int CountNodes(TreeNode* tree)
  199. {
  200.         if (tree == NULL)
  201.                 return 0;
  202.         else
  203.                 return CountNodes(tree->left)+CountNodes(tree->right)+1;
  204. }
  205. //-----------------------------------------------------------------------------
  206.         //FIND
  207. //-----------------------------------------------------------------------------
  208. void Retrieve(TreeNode* tree, ItemType& item, bool& found);
  209. template <class ItemType>
  210. void TreeType<ItemType>::Find(ItemType& item, bool& found) const
  211. {
  212.         Retrieve(root, item, found)
  213. }
  214.  
  215. void Retrieve(TreeNode* tree, ItemType& item, bool& found)
  216. {
  217.         if (tree == NULL)
  218.                 found = false;
  219.         else if (item < tree->info)
  220.                 Retrieve(tree->left, item, found);
  221.         else if (item > tree->info)
  222.                 Retrieve(tree->right, item, found);
  223.         else
  224.         {
  225.                 item = tree->info;
  226.                 found = true;
  227.         }
  228. }
  229. //-----------------------------------------------------------------------------
  230.         //Clear
  231. //-----------------------------------------------------------------------------
  232. template <class ItemType>
  233. void TreeType<ItemType>::Clear()
  234. {
  235.         ~TreeType():
  236. }
  237.  
  238. #endif
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2006
Posts: 147
Reputation: Laiq Ahmed will become famous soon enough Laiq Ahmed will become famous soon enough 
Solved Threads: 20
Laiq Ahmed Laiq Ahmed is offline Offline
Junior Poster

Re: Recursive Binary Search Tree Header File

 
0
  #2
May 2nd, 2008
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.
C++ Syntax (Toggle Plain Text) 
  1. void TreeType<ItemType>::operator=(const TreeType& originalTree);
why? would be your question, let me give your short answer try to find long answer yourself it would definitely improve your concept of copy constructor.
cpp Syntax (Toggle Plain Text) 
  1. TreeType t1;
  2. ....// do some inserting in tree.
  3. TreeType t2;
  4. .... // do some insertion in tree2
  5. TreeType t3;
  6. // now the interesting part.
  7. 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.
C++ Syntax (Toggle Plain Text) 
  1. 92:    CopyTree(root, originalTree.root);
  2. 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.

C++ Syntax (Toggle Plain Text) 
  1. template <class ItemType>
  2. void TreeType<ItemType>::Clear()
  3. {        
  4.  //         ~TreeType():
  5.              destroy(root);
  6. }

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.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C++ Forum
Thread Tools Search this Thread



Tag cloud for C++
api application array arrays assignment beginner binary bitmap c++ c/c++ calculator char char* class classes code coding compile compiler console conversion convert count data database delete developer display dll email encryption error file forms fstream function functions game generator getline givemetehcodez graph homeworkhelper iamthwee ifstream image input int java lazy lib loop looping loops map math matrix memory multidimensional multiple newbie news node number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference return sorting string strings struct template templates text tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC