Attempting to get this interative binary tree insert to work.

[Eruditee]

Homework Statement

Binary Tree/ Insertion scheme

Homework Equations

N/A

The Attempt at a Solution

bool treeNodeADT::_insert(int item) {
    if(this->isRootted==false){
        this->root=new node;
        this->root->data=item;
        this->root->right=0;
        this->root->left=0;
        this->isRootted = true;
    }
    else if (item>this->root->data){
        nodep temp = this->root->right;
        while (temp!=0){
            if(temp->data>item)
                temp=temp->left;
            else if (temp->data<item)
                temp = temp->right;
            else return false;
        }
        temp = new node;
        temp->data=item;
        temp->left=0;
        temp->right=0;
    }
       else if (item<this->root->data){
        nodep temp = this->root->left;
        while (temp!=0){
            if(temp->data>item)
                temp=temp->left;
            else if (temp->data<item)
                temp = temp->right;
            else return false;
        }
        temp = new node;
        temp->data=item;
        temp->left=0;
        temp->right=0;
    }


}

In short, there's a static variable in which isRotted (mispelled) shows whether the root has been constructed. I then follows the root in either its left or right directions by the if/esls shceme. Then when it gets to a point in which the data shows contrast, it decides to move left or right until a blank node has been found.

I never get into the whiles. Help? I can do this iteratively, but after I found out that's more computationally expensive, I want to learn this way in the event I need to use it for time sensitive cases.

 

[Mark44]

Homework Statement

Binary Tree/ Insertion scheme

Homework Equations

N/A

The Attempt at a Solution

bool treeNodeADT::_insert(int item) {
    if(this->isRootted==false){
        this->root=new node;
        this->root->data=item;
        this->root->right=0;
        this->root->left=0;
        this->isRootted = true;
    }
    else if (item>this->root->data){
        nodep temp = this->root->right;
        while (temp!=0){
            if(temp->data>item)
                temp=temp->left;
            else if (temp->data<item)
                temp = temp->right;
            else return false;
        }
        temp = new node;
        temp->data=item;
        temp->left=0;
        temp->right=0;
    }
       else if (item<this->root->data){
        nodep temp = this->root->left;
        while (temp!=0){
            if(temp->data>item)
                temp=temp->left;
            else if (temp->data<item)
                temp = temp->right;
            else return false;
        }
        temp = new node;
        temp->data=item;
        temp->left=0;
        temp->right=0;
    }}

In short, there's a static variable in which isRotted (mispelled) shows whether the root has been constructed. I then follows the root in either its left or right directions by the if/esls shceme. Then when it gets to a point in which the data shows contrast, it decides to move left or right until a blank node has been found.

I never get into the whiles. Help? I can do this iteratively, but after I found out that's more computationally expensive, I want to learn this way in the event I need to use it for time sensitive cases.

It seems flaky to me that you are setting what appear to be pointer variables with the integer value 0.

A major problem that I see is that if the node is not rooted, a new node is created, with its data, left, and right fields set, and then the function exits without returning a boolean value. The way you have your code indented makes it a little harder to notice that in certain cases your function doesn't return a value.

The proper indentation would look similar to this:

bool treeNodeADT::_insert(int item) {
    if(this->isRootted==false){
      // body of if clause
    }
    else if (item>this->root->data){
      // body of else if clause
    }
    else if (item<this->root->data){
      // body of else if clause 
    }
}

Also, what happens if item == this->root->data? You don't have any logic to handle that case.

Some of your code is more difficult to follow than it should be; for example, item>this->root->data

Add some spaces to increase readability, especially for the inequality operators. Without extra spacing it's harder to distinguish them from the struct pointer dereference operators.

Finally, if you are working with pointers, and aren't using a debugger to single-step through your code and inspect the values of variables, start learning to use one right away. You didn't mention what compiler you're using, but I'm pretty sure that there is some debugger available in whatever system you're using.

BTW, "IsRootted" and "IsRotted" are both misspellings. What you should have is "IsRooted".

 

[Eruditee]

It seems flaky to me that you are setting what appear to be pointer variables with the integer value 0.

A major problem that I see is that if the node is not rooted, a new node is created, with its data, left, and right fields set, and then the function exits without returning a boolean value. The way you have your code indented makes it a little harder to notice that in certain cases your function doesn't return a value.

The proper indentation would look similar to this:

bool treeNodeADT::_insert(int item) {
    if(this->isRootted==false){
      // body of if clause
    }
    else if (item>this->root->data){
      // body of else if clause
    }
    else if (item<this->root->data){
      // body of else if clause 
    }
}

Also, what happens if item == this->root->data? You don't have any logic to handle that case.

Some of your code is more difficult to follow than it should be; for example, item>this->root->data

Add some spaces to increase readability, especially for the inequality operators. Without extra spacing it's harder to distinguish them from the struct pointer dereference operators.

Finally, if you are working with pointers, and aren't using a debugger to single-step through your code and inspect the values of variables, start learning to use one right away. You didn't mention what compiler you're using, but I'm pretty sure that there is some debugger available in whatever system you're using.




BTW, "IsRootted" and "IsRotted" are both misspellings. What you should have is "IsRooted".

Yes, isRooted. I'm in NetBeans, which uses gdb. The indentation is actually auto-formatted in NetBeans itself? It doesn't add spacing with operators. I should, however.

I'm using 0 to avoid preprocessor time. Apparently, NULL is just a C++ macro or #define NULL 0

This works:

bool TreeADT::_insert(int item, nodep& a) {
    if (a == 0) {
        a = new node;
        a->data = item;
        a->left = 0;
        a->right = 0;
        return true;
    }
    else if (a->data > item)
        _insert(item, a->left);

    else if (a->data < item)
        _insert(item, a->right);

    else
        return false;
}

This is how I understand it best because it's just sequential on a stack, then popped off etc. Also, it's easier to see a stack trace for this and follow it.

This does not work:

bool TreeADT::_insert(int item, nodep a) {
    if (a == 0) {
        a = new node;
        a->data = item;
        a->left = 0;
        a->right = 0;
        return true;
    } 
    else if (a->data > item)
        _insert(item, a->left);

    else if (a->data < item)
        _insert(item, a->right);

    else
        return false;
}

I think it's because in the while version, I am passing root by value. Uninitialized, it does nothing but most likely give it a null pointer, as root is null to begin with.

It's easier to circumvent this in the recursive version becaue each time it runs, it is instructed to work on the actual entity as opposed to a copy somewhere else in the heap.

I'm not sure how to really do these iteratively. It was just to test it out because I figured iterative processes would be much faster, but I don't think big trees are used in microprocessing or in places where memory is sparse?

This isn't homework. It's just a self-practice; I posted it here as it seemed the most appropos. As to style, I'm learning Python and will most likely use that indentation style in all of my programming, as it just nicely enforces very readable style to even compile.

Thankx