1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Attempting to get this interative binary tree insert to work.

  1. Mar 30, 2014 #1
    1. The problem statement, all variables and given/known data

    Binary Tree/ Insertion scheme

    2. Relevant equations
    N/A


    3. The attempt at a solution
    Code (Text):
    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.
     
  2. jcsd
  3. Mar 30, 2014 #2

    Mark44

    Staff: Mentor

    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:
    Code (Text):
    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".
     
  4. Mar 30, 2014 #3
    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:
    Code (Text):
    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:
    Code (Text):
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Attempting to get this interative binary tree insert to work.
  1. Binary trees (Replies: 1)

  2. Binary Search tree (Replies: 5)

Loading...