Binary Tree question

RDH37 (5)

Iv been trying to understand programing of a binary tree from the code I found here. http://www.cplusplus.happycodings.com/Algorithms/code5.html

I'm confused about how the


while(curr)

loop works in this insert function.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

void BinarySearchTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;
  // is this a new tree?
  if(isEmpty()) root = t;
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* curr;
    curr = root;
    // Find the Node's parent
    while(curr)
    {
        parent = curr;
        if(t->data > curr->data) curr = curr->right;
        else curr = curr->left;
    }

    if(t->data < parent->data)
       parent->left = t;
    else
       parent->right = t;
  }
}

could someone walk me through what is going on? Thanks.

roblf (10)

the


while (curr)

line is a little misleading, as it is actually a shorthand. There are two facts you need to know to understand this. First, in C and C++, boolean values (ie true or false) are actually represented by an integer. The number 0 always represents False, but all other numbers represent True. Second, NULL is usually (there is some debate over this, but for now assume always!) shorthand for 0. The result of this is that


while (curr)

will loop until


curr

is equal to 0, at which point it will terminate, and since


curr

is a pointer, it will equal 0 once curr becomes NULL. So basically, the line


while (curr)

is a slightly sneaky way of saying "While the pointer curr is not NULL".

Hope that helps :)

firedraco (847)

Actually, boolean values ARE NOT represented by integers.

They are only represented by true or false. The C++ Standard says something to the effect of:

Bools are NOT enufs, typedefs, ints, strings etc...they are true or false.

It is just that an when an int is implicitly converted to a bool, 0 is false, everything else is true. Other then that, you are basically correct.

RDH37 (5)

Alright I understand it now, thanks.

This topic is archived - New replies not allowed.


		C++ : Forums : Beginners : Binary Tree question Search: