binary search trees

[cremo]

hey i'm trying to implement two functions that use binary search trees.

one of them is to search for a specific key value that is stored in a node.

here is the code for the node.

struct node 
    {
        int key; // value inside the node
        node * l; //pointer to the left child node
        node * r; //pointer to the right child node

         node()
        {
            key = -1;
            l = r = NULL;
        }

        node( int x, node * ll, node * rr)
        {
            key = x;
            l = ll;
            r = rr;
        }
    };

what i want to be able to do in my main is to have a boolean variable to say whether or not the value is part of the tree.

i have two functions to check to the value. one private and one public.

this is the public one:

bool binst::search(int key, node* leaf)
{
  if(leaf != NULL)
  {
    if(key == leaf->key)
      return true;
    if(key < leaf->key)
      return search(key, leaf->l);
    else
      return search(key, leaf->r);
  }
  else 
      return false;
}

here's the public function:

bool binst::search(int key)
{
  return search(key, head); //head relates to the root node.
}

so in my main i have this.

    binst t ; 
    //inserting values on to the tree
    t.insert(10); t.insert(3); t.insert(14);  t.insert(6);  t.insert(3);
    t.insert(6);  t.insert(12);  t.insert(20);
bool boo ;
    boo = t.search(20) ; 
    cout << "boo :" << boo ;

the above will give

boo: 1.

whereas if i have it like this

boo = t.search(34) ; //ie NOT on tree.

it doesn't print out the line

boo: 0

which it should


the second function i need to implement is to find the height of the tree t.
i have this piece of pseudocode written but can't figure out how to implement it.

int height( BinaryTree Node t) 
{
    if t is a null tree
        return -1;
    hl = height( left subtree of t);
    hr = height( right subtree of t);
    h = 1 + maximum of hl and hr;
    return h;
}

anyone help out a fellow fellow?

 

[cremo]

anyone?

 

[ByteJuggler]

anyone?

well you've nearly got the code there already, which part are you having trouble translating?

 

[cremo]

well you've nearly got the code there already, which part are you having trouble translating?

well when i do a search for a key value that isn't on the tree, it doesn't return 0 for false

so it's never getting to the outer else part (which should return false) of my code here

bool binst::search(int key, node* leaf)
{
  if(leaf != NULL)
  {
    if(key == leaf->key)
      return true;
    if(key < leaf->key)
      return search(key, leaf->l);
    else
      return search(key, leaf->r);
  }
  else 
      return false;
}

it returns true no problem if a key is found.

on the height this is what i have so far.

int binst::height()
{
    height(head->l) ; 
    
}

int binst::height(node * t)
{
    int h, hl, hr ;
    if(t == z) 
        return -1 ;
    else
    {
        hl = height(t->l) ; 
        hr = height(t->r) ; 
        h = 1 + hl + hr ; 
        cout <<"height:" << h ; 
    }
    return h ; 
}

then from my main() i have:

int h ; //to store height
binst t ; 

h = t.height() ; 
cout << "height is : " << h << endl ;

this always returns -1.

 

[ByteJuggler]

Ah ok I'm sorry, I hadn't read the first part properly - I thought that was working OK and you were just explaining. (My comment pertained to the pseudo code question.) Sorry! I'll have a lookee...

Edit: Well, I'd guess the insert method might be at fault, can you post that? Also, if you use the node constructor that takes 2 other nodes, it doesn't check whether the left and right nodes are the smaller and greater (or whatever) nodes, it *assumes* they are. If you use that constructor incorrectly badness will result. That constructor should really check which node is smaller and ensure it gets assigned to the appropriate reference etc.

 

[cremo]

this is the insert function:

void binst::insert( int x)
{
    node * t = new node(x, z, z); //z is a null pointer
    node * p = head;
    node * c = head->r;

    // find the path down through the tree to a terminal
    // node where the new node t can be inserted.
    while(c != z)
    {
        p = c;
        if(x < c->key)
            c = c->l;
        else
            c = c->r;
    }

    // insert the node by making a link from the previous
    // node to it.
    if(x < p->key)
        p->l = t;
    else
        p->r = t;
}

.