Thread: Recursion and new operator

You could allocate and create your node in the insert function and then pass it to the insertLeaf function, rather than allocating it there.

...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).

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;
}

The pointers refer to values. However, copies of the actual pointer are sent by default.