Sunday, 16 April 2017

inserting into a binary tree using empty sentinel nodes

Rather than the us of NULL to represent no present nodes we(class) are using empty_nodes and the function isEmpty() is a bool return true if it is "empty_node" and false if it is a "normal_node". The code compiles, but when I test this tree:

      5
    /   \
   X     17
        /
       10 //X represent empty node

it asserts the right of 17 is not 10. I believe it is screwy because of I may need a left and right variable for my tempr and templ, but I think that may be inefficient What is the problem

node * normal_node::insert(int k)
    {
        //temp variables holds right and left of tree
        node* tempr = this->getRight();
        node* templ = this->getLeft();
        if (this -> getData() == k)
        {
            return this;
        }
        if (k > this -> getData())
        {
            if (tempr -> isEmpty())
            {
                right = getRight() -> insert(k);
                delete tempr;
            }
            return this;

        }
        else
        {
            if (templ -> isEmpty())
            {
                left = getLeft() -> insert(k);
                delete templ;
            }
            return this;
        }
    }



via Terriyon Veasy

No comments:

Post a Comment