Recursive function

This is a discussion on Recursive function within the C++ Programming forums, part of the General Programming Boards category; I am using this function to remove a node from a binary tree. It works fine in most situations. Often ...

  1. #1
    Still A Registered User DISGUISED's Avatar
    Join Date
    Aug 2001
    Posts
    499

    Recursive function

    I am using this function to remove a node from a binary tree. It works fine in most situations. Often though it will leave either the left or right pointer from a parent null. So when I go to display it the program just blows up. Thanks for any ideas.

    Code:
     
    Node *Btree::remove(Node *root,int key)
    {
    	Node *index = NULL;
    	Node *index2 = NULL;
    	if(!root)
    	   return root;
    	if((root->getData())== key)
    	{
    		if(root->getLeft() == root->getRight())
    		{
    			delete root;
    			return NULL;
    		}
    		else if(!root->getLeft())
    		{
    			index = root->getRight();
    			delete root;
    			return index;
    		}
    		else if(!root->getRight())
    		{
    			index = root->getLeft();
    			delete root;
    			return index;
    		}
    		else
    		{
    			index2 = root->getRight();
    			index = root->getRight();
    			while(index->getLeft())
    			       index = index->getLeft();
    			index->setLeft(root->getLeft());
    			delete root;
    			return index2;
    		}
    	}
    	if(root->getData() < key)
    	   root->setRight(remove(root->getRight(),key));
    	else
               root->setLeft(remove(root->getLeft(),key));
    	return root;
    }

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,701
    Can't really tell, myself ( though I'm not a b-tree expert ).
    But is it safe to just delete a node without 'reconnecting' it's neighbors? (Set me straight if I'm being ignorant)

    Anyhow, have you tried the tried and true printf dubug?
    Code:
    bool fun(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() > 0;
    }

  3. #3
    Still A Registered User DISGUISED's Avatar
    Join Date
    Aug 2001
    Posts
    499
    But is it safe to just delete a node without 'reconnecting' it's neighbors? (Set me straight if I'm being ignorant)

    Anyhow, have you tried the tried and true printf dubug?
    Yeah I know what you are saying and that's the problem. It does reset the pointers in most situations. In one particular set of test data I am using it doesn't work. I don't know I have looked at it for a while now. Is this a problem that is best solved some other way than recursion?

  4. #4
    Still A Registered User DISGUISED's Avatar
    Join Date
    Aug 2001
    Posts
    499
    YES!!!! For those of you who may care (haha) I FINALLY!! got my function working beautifully. Although it looks completely different now (still recursive). Anyways, I'm happy.

  5. #5
    Banned frenchfry164's Avatar
    Join Date
    Oct 2001
    Posts
    1,552
    I never have used binary trees. I don't want to learn em unless I have to either.

  6. #6
    Still A Registered User DISGUISED's Avatar
    Join Date
    Aug 2001
    Posts
    499
    The binary tree is a structure that is completely dynamic. Not only that, but it basically sorts itself as it is constructed at run time. It is also quite easy to ensure that you don't add duplicate data to your structure. But man oh man was it hard for me to figure out how to remove certain nodes recursively without losing the whole structure. Now that I got it I got it. If that makes sense. So yeah, it's a nice structure. My professor told me that when I take a test to get a job in this language most of the questions will be on trees and linked lists so I would have to say it's pretty important.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function
    By Fork in forum C Programming
    Replies: 3
    Last Post: 10-26-2006, 11:27 AM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 09:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21