C++ Binary Search Tree Problem

Discussion in 'Mac Programming' started by steelphantom, Oct 18, 2007.

  1. steelphantom macrumors 6502a

    steelphantom

    Joined:
    Oct 15, 2005
    #1
    I'm trying to write a simple binary search tree in C++, and I'm getting hung up on the insert function, more specifically, where the program checks to see if my node is NULL. The if statement evaluates as false and nothing gets inserted. Could anyone give me a hint as to what I'm doing wrong? Thanks!

    Here's my code:

    Code:
    #include <iostream>
    
    using namespace std;
    
    struct Node
    {
    	int value;
    	Node *left;
    	Node *right;
    };
    
    void visit(Node *ptr)
    {
    	if (ptr->left == NULL)
    		visit(ptr->left);
    		
    	cout << ptr->value;
    	
    	if (ptr->right == NULL)
    		visit(ptr->right);
    }
    
    void insert(int data, Node *ptr)
    {
    	if (ptr == NULL)
    	{
    		ptr = new Node;
    		ptr->value = data;
    		ptr->left = NULL;
    		ptr->right = NULL;
    	}
    	else if (data < ptr->value)
    		insert(data, ptr->left);
    	else if (data > ptr->value)
    		insert(data, ptr->right);
    }
    
    int main()
    {
    	Node *myTree = new Node;
    	insert (5, myTree);
    	cout << myTree->value << endl;
    	return 0;
    }
     
  2. saltyzoo macrumors 65816

    saltyzoo

    Joined:
    Oct 4, 2007
    #2
    You haven't initialized a root node. So the line "else if (data < ptr->value)" is going to puke on you as value in the ptr node is null.
     
  3. fimac macrumors member

    Joined:
    Jan 18, 2006
    Location:
    Finland
    #3
    Given test data of { 5, 3, 8, 4, 7 } do you expect to see this?

    Code:
          5
         / \
        /   \
       3     8
      /\     /\
     /  \   /  \
        4   7
    If so, then this is a good use-case for pointer-to-pointers :) This allows us to simplify the insert() function: it simply allocates a new node, or recurses.

    Code:
    #include <iostream>
    
    using namespace std;
    
    struct Node
    {
      int   value;
      Node *left;
      Node *right;
    };
    
    static void
    visit(Node const *ptr)
    {
      if (NULL != ptr)
        {
          visit(ptr->left);
          cout << ptr->value << endl;
          visit(ptr->right);
        }
    }
    
    static void
    insert(int value, Node **pp)
    {
      if (NULL == *pp)
        {
          *pp          = new Node;
          (*pp)->value = value;
          (*pp)->left  = NULL;
          (*pp)->right = NULL;
        }
      else if (value < (*pp)->value)
        {
          insert(value, &(*pp)->left);
        }
      else if (value > (*pp)->value)
        {
          insert(value, &(*pp)->right);
        }
      else
        {
          // ignore duplicates
        }
    }
    
    int
    main(void)
    {
      Node *root = NULL;
    
      insert(5, &root);
      insert(3, &root);
      insert(8, &root);
      insert(7, &root);
      insert(4, &root);
    
      visit(root);
    
      return 0;
    }
     
  4. lazydog macrumors 6502a

    Joined:
    Sep 3, 2005
    Location:
    Cramlington, UK
    #4
    Hi
    I think I can see a few problems with your code:-

    Your Node struct does not have any constructors. You really need to initialise the left and right poitners to null. Somthing like this…

    Code:
    struct Node
    {
    	int value;
    	Node *left;
    	Node *right;
    
    };
    
     
  5. lazydog macrumors 6502a

    Joined:
    Sep 3, 2005
    Location:
    Cramlington, UK
    #5
    Hi
    I think I can see a few problems with your code:-

    Your Node struct does not have any constructors. You really need to initialise the left and right pointers to null. Something like this…

    Code:
    struct Node
    {
    	int value;
    	Node *left;
    	Node *right;
    
         Node() : left( 0L ), right( 0L ) {}
    
    };
    
    Also in visit() change the if condition to:-

    Code:
    if (ptr->left != NULL) 
    
    Since you're using C++ why not make visit() and insert() member functions of Node?

    b e n
     
  6. fimac macrumors member

    Joined:
    Jan 18, 2006
    Location:
    Finland
    #6
    Yes. "new" is not guaranteed this automatically for us.

    Good point about this being C code -- IMHO that's ok; I sometimes use C++ as simply a better C ;)
     
  7. saltyzoo macrumors 65816

    saltyzoo

    Joined:
    Oct 4, 2007
    #7
    No, in fact, it doesn't. That is the problem here.
     
  8. Lyle macrumors 68000

    Lyle

    Joined:
    Jun 11, 2003
    Location:
    Madison, Alabama
    #8
    saltyzoo is right; you can't count on those members being initialized automatically. Even if one C++ compiler happens to do this for you, you shouldn't count on that behavior to portable to other C++ implementations.

    By the way, I think Java does guarantee that those members will be initialized to zero (for the value) or null (for the pointers), which can lead to some confusion if you have to switch back and forth between those languages.
     
  9. steelphantom thread starter macrumors 6502a

    steelphantom

    Joined:
    Oct 15, 2005
    #9
    OK, does this take care of the initialization step?

    Code:
    int main()
    {
    	Node *myTree = new Node;
    	myTree->left = myTree->right = NULL;
    	insert (5, myTree);
    	cout << myTree->value << endl;
    	return 0;
    }
    It still doesn't work correctly, so I'm obviously doing something wrong.

    Thanks lazydog for pointing out my stupid error in the visit() function.

    fimac, your solution works, but I think pointers to pointers are even more confusing for me. I'd like to get this to work without using them.

    Also, this will eventually be implemented into a class, but I want to get the basics working first. Thanks everyone for your help! Pointers have become a real stumbling block for me.
     
  10. Lyle macrumors 68000

    Lyle

    Joined:
    Jun 11, 2003
    Location:
    Madison, Alabama
    #10
    I'd also initialize myTree->value to zero. As your code is currently written, its value is undefined.

    Once you've done that, the initial call to insert() should drop into the third if-branch, because ptr is not NULL and the data (which is 5) is greater than the current node's value (which is zero). So that will trigger a call to insert(5, NULL).

    On this call to insert(), ptr is NULL and so you'll construct a new Node and initialize its value to 5. Unfortunately, you haven't provided any way for the parent node (myTree) to link to this. That is, at some point you want to assign this newly constructed node to the "right" pointer for myTree.

    Hang in there. Pointers are hard to get the hang of. :D
     
  11. madmoose macrumors newbie

    Joined:
    Oct 5, 2007
    #11
    Here's how I'd solve it. The separate Tree-class helps to manage the initialization problems and cleanup.

    Code:
    #include <iostream>
    
    class Node
    {
    	friend class Tree;
    
    	int value;
    	Node *left;
    	Node *right;
    
    	Node(int value) : value(value), left(0), right(0)
    	{
    	}
    
    	~Node()
    	{
    		delete left;
    		delete right;
    	}
    
    	void insert(int newValue);
    	void visit();
    };
    
    void Node::insert(int newValue)
    {
    	// This could also be written non-recursively
    
    	if (newValue < value)
    	{
    		if (left)
    			left->insert(newValue);
    		else
    			left = new Node(newValue);
    	}
    	else if (newValue > value)
    	{
    		if (right)
    			right->insert(newValue);
    		else
    			right = new Node(newValue);
    	}
    	// else value already exists
    }
    
    void Node::visit()
    {
    	if (left)
    		left->visit();
    
    	std::cout << value;
    
    	if (right)
    		right->visit();
    }
    
    class Tree
    {
    	Node *root;
    
    public:
    	Tree() : root(0)
    	{
    	}
    
    	~Tree()
    	{
    		delete root;
    	}
    	
    	void insert(int newValue);
    	void visit();
    };
    
    void Tree::insert(int newValue)
    {
    	if (root)
    		root->insert(newValue);
    	else
    		root = new Node(newValue);
    }
    
    void Tree::visit()
    {
    	if (root)
    	{
    		root->visit();
    		std::cout << std::endl;
    	}
    }
    
    int main()
    {
    	Tree t;
    	const int data[] = { 5, 3, 8, 7, 4 };
    
    	for (unsigned int i = 0; i < sizeof(data)/sizeof(data[0]); ++i)
    		t.insert(data[i]);
    
    	t.visit();
    }
    
     
  12. lazydog macrumors 6502a

    Joined:
    Sep 3, 2005
    Location:
    Cramlington, UK
    #12
    Your code doesn't actually set the value of myTree.value. myTree is acting as the root node of your tree and so you should be initialising it's value. Your original insert() function needs fixing too. The pointer you pass should be a pointer of the parent node. That way when insert() creates a new node the parent can be set to point to it, either by setting the parent's left or right values. Here's how I see your insert function working:-

    Code:
    void insert( int value, Node* parent )
    {
        if ( value == parent->value )
         //
         // Nothing to do.
         // 
         return ;
    
      if ( value < parent->value )
        if ( parent->left == NULL )
          parent->left = create_new_node( value ) ;
       else
          insert( value, parent->left ) ;
      else
         same for right!
    }
    
    Node* create_new_node( int value )
    {
       Node* node = new Node() ;
       node->left = node->right = NULL ;
       node->value = value ;
    
      return node ;
    }
    

    Since you're not using constructors I've added a create node function. This initialises the node and set's its value.

    b e n
     

Share This Page