Re: binary search tree insert()

Discussion in 'C++' started by John Harrison, Jul 28, 2003.

  1. "Andrew Edwards" <> wrote in message
    news:MW%Ua.279988$...
    > When working with ADTs, data types are provided at runtime and can be of

    any
    > legal data type, to include classes.
    >
    > Obviously my ADT should handle all data types but I've encountered a
    > roadblock at first attempt. I really have no how to handle inserting a

    leaf
    > into a binary search tree when its data type is a class.
    >
    > How do I check for equality within a class data type in which relational
    > operators are NOT overloaded.
    >
    > This is my attempt at an insert function:
    >
    > ===========================================================
    > template < class DT, class KF >
    > void BSTree<DT,KF>:: insertSub ( BSTreeNode<DT,KF>*& p,
    > const DT &newDataItem ) throw ( bad_alloc )
    >
    > // Inserts newDataItem into a binary search tree. If a data
    > // item with the same key as newDataItem already exists in
    > // the tree, then updates that data item's nonkey fields
    > // with newDataItem's nonkey fields.
    >
    > {
    > if ( p == NULL )
    > {
    > p = new BSTreeNode<DT,KF>(newDataItem,NULL,NULL);
    > }
    > else if (newDataItem < p->dataItem )
    > {
    > insertSub(p->left, newDataItem);
    > }
    > else
    > {
    > insertSub(p->right, newDataItem);
    > }
    > }
    >
    > Any "HELP" is greatly appreciated,
    > Andrew
    >


    What is KF? Is that your Key Function? I.e. what you are requiring for key
    comparisons instead of the usual relational operators? Obviously the way you
    use that depends on how you are expecting the users of your class to define
    it. Typical would be this

    else if (key_func(newDataItem, p->dataItem) < 0)

    where key_func is an object of type KF supplied by the user of this class
    (e.g. in the constructor).

    I might be completely off beam here, perhaps you should explain what KF is,
    or how you expect comparisons to be done in the absence of relational
    operators.

    john
    John Harrison, Jul 28, 2003
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joris Gillis
    Replies:
    2
    Views:
    1,522
    Joris Gillis
    Jun 16, 2006
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,091
  3. Replies:
    4
    Views:
    557
  4. sharan
    Replies:
    4
    Views:
    674
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,030
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page