pointers

[cppnoob25]

Why doesn't my insert function work correctly?

My print function is purposely done this way for simple testing. I will fix that after my insert works correctly.

class Btree{

private:

    struct Node{
        int data;
        Node * left;
        Node * right;
    };

    Node * root;
    Node * current;

public:

    Btree();
    //~Btree();
    void insert(int x);
    void remove(int value);
    void print();
};

Btree::Btree()
{
    root = 0;
}
/*
void Btree::insert(int x)
{
    insert(&root, x);
}
*/

void Btree::print()
{
    Node * current;

        cout << root->data << endl;
        current = root->right;
        cout << current->data;

}


void Btree::insert(int x)
{
    Node * n = new Node;
    n->data = x;
    n->left = 0;
    n-> right = 0;

    current = root;

    if(root != 0)
    {
        current = root;
        while(current != 0)
        {
            if(current->data < x)
            {
                current = current->left;
            }
            else
            {
                current = current->right;
            }
        }
        n = current;
    }
    else
    {
        root = n;
    }
}

int main()
{
    Btree one;

    one.insert(3);
    one.insert(4);
    //one.insert(2);

    one.print();
}

[keskiverto]

Line 69?

[xenovia12]

looks like you have also problem in inserting trees even if you fix the print function

line 69 doesnt make sense, it looks like you mistyped it from current = n;

[andywestken]

Well, line 69 does look wrong...

And I think line 58 is wrong, too.

Why doesn't my insert function work correctly?

See comments in code...

void Btree::insert(int x)
{
    Node * n = new Node; // create a new node and init it
    n->data = x;
    n->left = 0;
    n-> right = 0;

    current = root; // set current node to root

    if(root != 0)
    {
        current = root;  // set current node to root again
        while(current != 0) // loop until current is null
        {
            if(current->data < x)
            {
                current = current->left;
            }
            else
            {
                current = current->right;
            }
        }
        n = current; // set new node pointer to null (the value we know current to be) :-(
    }                // so the new node hasn't been added to tree; instead memory has been leaked
    else
    {
        root = n; // set root to point at new node :-)
    }
}

I take it that you want your new node to be added to the existing tree? If so, you need to find an unused left or right member to point at your new node (so exiting the while loop when current == 0 is too late.)

And current prob shouldn't be a member variable given the way it's being used in your insert method. (Based on current code it should be declared on line 57)

Oh, and if you're compiler is up to date enough, you should use nullptr rather than 0 to test if a pointer against null.

Andy

[dhayden]

Create a constructor for your Node class:
Node(int d) : data(d), left(NULL), right(NULL) {}
Instead of keeping a pointer to the current node, keep a pointer to the current link - in other words, a pointer to root, or the left/right pointer of a node. If you do this, then you don't need a special case for when root == NULL

void
Btree::insert(int x)
{
    Node *n = new Node(x);  // use new constructor

    Node **link = &root;
    Node *cur;
    while (cur = *link) {
	if (cur->data < x) {
	    link = &cur->left;
	} else {
	    link = &cur->right;
	}
    }
    *link = n;
}