By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,605 Members | 1,370 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,605 IT Pros & Developers. It's quick & easy.

Awkward Error in C++ (Binary Tree)

P: 6
I'm using a binary tree, and each time I insert into it, it says that there is nothing there. here is my code:

Expand|Select|Wrap|Line Numbers
  1. #ifndef BST_H
  2. #define BST_H
  3.  
  4. #include <stdlib.h>
  5.  
  6. class Node{
  7.     int data;
  8. public:
  9.     Node(int d){data = d; left = NULL; right = NULL;}
  10.     ~Node(){}
  11.     Node * left;
  12.     Node * right;
  13.     int getData() {return data;}
  14. };
  15.  
  16. class BST{
  17. private:
  18.     Node * top;
  19.     void cleanup(Node * h);
  20. public:
  21.     BST(){top=NULL;}
  22.     ~BST(){cleanup(top);}
  23.     int Insert(const int& data);
  24.     int iinsert(Node * t, const int& data);
  25. };
  26.  
  27. void BST::cleanup(Node * t)
  28. {
  29.     if(t != NULL)
  30.     {
  31.         cleanup(t->left);
  32.         cleanup(t->right);
  33.         delete t;
  34.     }
  35. }
  36.  
  37. int BST::Insert(const int& data)
  38. {
  39.     return iinsert(top, data);
  40. }
  41.  
  42. int BST::iinsert(Node * t, const int& data)
  43. {
  44.     if(t == NULL)
  45.     {
  46.         t = new Node(data);
  47.         return 1;
  48.     }
  49.     else if(data == t->getData())
  50.     {
  51.         return 0;
  52.     }
  53.     else if(data < t->getData())
  54.     {
  55.         return iinsert(t->right, data);
  56.     }
  57.     else if(data > t->getData())
  58.     {
  59.         return iinsert(t->right, data);
  60.     }
  61. }
  62.  
  63. #endif
this is only the insert method. Does this look right, or did I do something wrong?
Nov 15 '06 #1
Share this Question
Share on Google+
5 Replies


Banfa
Expert Mod 5K+
P: 8,916
surely this

Expand|Select|Wrap|Line Numbers
  1.     else if(data > t->getData())
  2.     {
  3.         return iinsert(t->right, data);
  4.     }
  5.  
should be

Expand|Select|Wrap|Line Numbers
  1.     else if(data > t->getData())
  2.     {
  3.         return iinsert(t->left, data);
  4.     }
  5.  
i.e. at the moment you use the right pointer twice and the left pointer never.
Nov 15 '06 #2

P: 6
that's correct, I didn't even notice that. But each time I do an Insert, the top remains null afterwards.
Nov 15 '06 #3

P: 6
I've modified this code to include a different version of insert:

Expand|Select|Wrap|Line Numbers
  1. #ifndef BST1_H
  2. #define BST1_H
  3.  
  4. #include <stdlib.h>
  5.  
  6. class Node{
  7.     int data;
  8. public:
  9.     Node(int d){data = d; left = NULL; right = NULL;}
  10.     ~Node(){}
  11.     Node * left;
  12.     Node * right;
  13.     int getData() {return data;}
  14. };
  15.  
  16. class BST{
  17. private:
  18.     Node * top;
  19.     void cleanup(Node * h);
  20. public:
  21.     BST(){top=NULL;}
  22.     ~BST(){cleanup(top);}
  23.     int Insert(const int& data);
  24.     int Insert_2(const int& data);
  25.     int iinsert(Node * t, const int& data);
  26. };
  27.  
  28. int BST::Insert_2(const int& data)
  29. {
  30.     if(top == NULL)
  31.     {
  32.         top = new Node(data);
  33.     }
  34.     else{
  35.         Node * ptr = top;
  36.         while(ptr != NULL)
  37.         {
  38.             if(data == ptr->getData())
  39.             {
  40.                 return 0;
  41.             }
  42.             else if(data < ptr->getData())
  43.             {
  44.                 ptr = ptr->left;
  45.             }
  46.             else
  47.             {
  48.                 ptr = ptr->right;
  49.             }
  50.         }
  51.         ptr = new Node(data);
  52.     }
  53. }
  54.  
  55. void BST::cleanup(Node * t)
  56. {
  57.     if(t != NULL)
  58.     {
  59.         cleanup(t->left);
  60.         cleanup(t->right);
  61.         delete t;
  62.     }
  63. }
  64.  
  65. int BST::Insert(const int& data)
  66. {
  67.     return iinsert(top, data);
  68. }
  69.  
  70. int BST::iinsert(Node * t, const int& data)
  71. {
  72.     if(t == NULL)
  73.     {
  74.         t = new Node(data);
  75.         return 1;
  76.     }
  77.     else if(data == t->getData())
  78.     {
  79.         return 0;
  80.     }
  81.     else if(data < t->getData())
  82.     {
  83.         return iinsert(t->left, data);
  84.     }
  85.     else
  86.     {
  87.         return iinsert(t->right, data);
  88.     }
  89. }
  90.  
  91. #endif
But it still causes the same problem, so the code:

Expand|Select|Wrap|Line Numbers
  1. #include "bst1.h"
  2.  
  3. int main()
  4. {
  5.     BST t1;
  6.     BST t2;
  7.     t1.Insert(5);
  8.     t1.Insert(11);
  9.     t1.Insert(1);
  10.  
  11.     t2.Insert_2(5);
  12.     t2.Insert_2(11);
  13.     t2.Insert_2(1);
  14.     return 0;
  15. }
  16.  
just before the return, the debugger says:
t1->top = NULL
t1->top->left = NULL
t1->top->right = NULL
t2->top = (5)
t2->top->left = NULL
t2->top->right = NULL

does anyone have any idea why this is the case? Maybe I have some pointer issues? But I don't see any, and most sites says to do the insert recursively.
Nov 15 '06 #4

Banfa
Expert Mod 5K+
P: 8,916
Because this line

ptr = new Node(data);

in insert_2

assigns data to a local variable, ptr, but not to any of the pointers in the Node data structures hanging off top.

Actually insert_2 is a classic location for a pointer to pointer

[code]
Node **ptrptr;

ptrptr = &top;

while(*ptrptr != NULL)
{
if (data < (*ptrptr)->data)
{
ptrptr = &(*ptrptr)->left;
}
else if (data > (*ptrptr)->data)
{
ptrptr = &(*ptrptr)->left;
}
else
{
return 0;
}
}

(*ptrptr) = new Node;

if (*ptrptr != NULL)
{
(*ptrptr)->data = data;
}
[code]

By having a pointer to pointer we search for and find the location that we wish to allocate a new node to. Byt only having a pointer you search for and find the value of the pointer where you wish to allocate a new node (which is guaranteed to be NULL).

Assuming no dupicate is found then your loop in insert_2 is equivilent to the statement

ptr = NULL;
Nov 15 '06 #5

P: 6
thanks a lot
Nov 16 '06 #6

Post your reply

Sign in to post your reply or Sign up for a free account.