Inserting into an Ordered Binary Search Tree

Question

I'm having trouble creating a C++ function that will insert an item into a binary tree that is sorted alphabetically.

The insert function is supposed to work like this: The user is prompted to enter a number. This number will refer to how many books to enter. Then the title and url of the book (defined as a struct) are entered and the book is inserted into the tree alphabetically based on the first letter of the title.

I've defined a book like this, where the title and url are arrays of chars:

struct bookNode {
    char title[30];
    char url[40];
    char key;
    bookNode *left;
    bookNode *right;
} book;

And this is what I have so far for the insert function:

void insertBook () {
    struct bookNode *p, *q;
    int i, n;
    char key;
    cout << "Enter the number of books you want to add" << endl;
    cin >> n;
    for(i=0;i<n;i++) {
        p = (struct bookNode *)malloc(sizeof(struct bookNode));
        if(p==0)
            cout << "Out of Memory" << endl;
        cout << "Enter the title of the book" << endl;
        cin.getline(book.title, 30);
        key = book.title[0];
        cout << "Enter the url of the book" << endl;
        cin.getline(book.url, 40);
        p->key;                        //I'm not sure if these next 3 lines are right
        p->left=0;
        p->right=0;
        ...
    }
}

I'm thinking that I might have to declare some sort of pointer to the root of the tree also, but I'm not sure where to put it. And I also realize I will need to write a separate "search" function, that I will call in this insert function, to find where to actually insert the book, but I'm just looking for help to finish this insert function.

Answer 1

  bookNode* closest = search(p); //find closest node to where p goes
  if (p->key < closest->key) //if p goes to the left
     closest->left = p; //put it on the left
  else //otherwise
     closest->right = p; //put it on the right


bookNode* search(bookNode* findme) {
    //The search should traverse the tree 
    //and return a pointer to the "bottom" bookNode 
    //that is closest in value to p->title
}

Also you don't want to refer to book anywhere in your insert function, you want to read into p->title and p->url, otherwise you're erasing whatever was in book every single time you make a new bookNode.

----------NOTES---------------
I highly recommend not using char*, and using std::string instead:

struct bookNode {
    std::string title;  //unlimited space
    //other members
} book;

int main() {
   std::string name = "Fred"; //easy to make
   std::getline(cin, name); //read in entire title, no matter how long
   if (name < "Fred") //easy to compare entire strings
       std::cout << name;  //easy to use
} //deletes itself automagically

Answer 2

traversing a tree is one of the things that recursion is very good at.

What I would do, is write a recursive function that takes a sub-tree, and a value to insert, and inserts that value into the proper place in the sub-tree.