Recursion and new operator

This is a discussion on Recursion and new operator within the C++ Programming forums, part of the General Programming Boards category; I'm writing a BST class and have a very strange (at least to me) problem. I can't insert a key ...

  1. #1
    Registered User
    Join Date
    Dec 2001
    Posts
    2

    Recursion and new operator

    I'm writing a BST class and have a very strange (at least to me) problem. I can't insert a key in tree using recursion. Iteration works fine, but I would really like to know why recursive way doesn't work.
    The code I wrote seems to be fine, so if anyone could point me in right direction...

    My code is:
    Code:
    struct sData
    {
    	long key;
    	char name[20];
    };
    
    struct sTINode
    {
    	sData data;
    	sTINode* left;
    	sTINode* right;
    };
    
    class cBST :
    	public cAbsTelefonskiImenik
    {
    public:
    	cTelefonskiImenikBST(void);
    	~cTelefonskiImenikBST(void);
    	bool insert(long key, char name[20]);
    private:
    	// root
    	sTINode *root;
    	void insertLeaf(long key, char name[20], char, sTINode *node);
    };
    
    cBST::cTelefonskiImenikBST(void)
    {
    	root=NULL;	
    }
    
    bool cBST::insert(long key, char name[20]);
    {
    	insertLeaf(key, name, root);
    	return true;
    }
    
    void cTelefonskiImenikBST::insertLeaf(long key, char name[20], sTINode *node)
    {
    	if (node==NULL)
    	{
    		node=new sTINode;
    		node->data.key=key;
    		strcpy(node->data.name, name);
    		node->left=NULL;
    		node->right=NULL;
    		return;
    	}
    	else
    	{
    		if (node->data.key>key)
    			insertLeaf(key, name, node->left);
    		else if (node->data.key<key)
    			insertLeaf(key, name, node->right);
    	}
    }

  2. #2
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    You could allocate and create your node in the insert function and then pass it to the insertLeaf function, rather than allocating it there.
    zen

  3. #3
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    ...and your code isn't working because you've got to insert it to the right or left of an existing node, so you should be checking whether node->left==NULL or node->right==NULL, not whether the node itself is NULL (otherwise your new node is never attached and has no parent).
    zen

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    Heh, I had to do so much crap just to get this to compile, and so little to actually fix what was wrong with your code. Basically, you have to remember that pointers are passed by value by default. In making the pointers sent by reference to the insertLeaft code, the code worked fine.

    Code:
    struct sData
    {
    	long key;
    	char name[20];
    };
    
    struct sTINode
    {
    	sData data;
    	sTINode* left;
    	sTINode* right;
    };
    
    class cBST 
    {
    public:
    	cBST(void);
    	~cBST(void);
    	bool insert(long key, char* name);
        void print();
    private:
        void print(sTINode *node);
    	// root
    	sTINode *root;
    	void insertLeaf(long key, char* name, sTINode *&node);
        void remove(sTINode* node);
    };
    
    #include <iostream>
    
    void cBST::print() {
        print(root);
    }
    
    void cBST::print(sTINode* node) {
        if (node != 0 ) {
            std::cout << '\t' << node->data.key << ' ' << node->data.name ;
            print(node->left);
            print(node->right);
        }
    }        
    
    cBST::cBST(void)
    {
    	root=NULL;	
    }
    
    cBST::~cBST(void)
    {
        remove(root);
    }
    
    void cBST::remove(sTINode* node) {
        if (node != 0) {
            remove(node->left);
            remove(node->right);
            delete node;
        }
    }
    
    bool cBST::insert(long key, char* name)
    {
    	insertLeaf(key, name, root);
    	return true;
    }
    
    void cBST::insertLeaf(long key, char name[20], sTINode *&node)
    {
    	if (node==NULL)
    	{
    		node=new sTINode;
    		node->data.key=key;
    		strcpy(node->data.name, name);
    		node->left=NULL;
    		node->right=NULL;
    		return;
    	}
    	else
    	{
    		if (node->data.key>key)
    			insertLeaf(key, name, node->left);
    		else if (node->data.key<key)
    			insertLeaf(key, name, node->right);
    	}
    }
    
    int main() {
        cBST tree;
        tree.insert(1, "rob");
        tree.insert(2, "blah");
        tree.insert(3, "dan");
        tree.insert(0, "otherthing");
        tree.print();
        char wait; cin >> wait;
    }
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    Registered User
    Join Date
    Dec 2001
    Posts
    2
    Many thanks, SilentStrike.
    I though that pointer are always passed by reference (I am Delphi programmer and what little of what I know abot C++ I learned at university)...so I have some reading to do about the subject.

  6. #6
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    The pointers refer to values. However, copies of the actual pointer are sent by default.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

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