Inserting a node into a binary search tree/linked list?

Question

Ok, I am beyond exhausted with this problem, so I figured I would get some outside help. The program holds a "database" of Personnel which include Employees and Students. Each student has a binary tree of "books" that the user can insert and search through. I need to take in a name of a student, find the Personnel node that corresponds to that particular student, and add a book to that student's bookTree.

The error message I'm getting is "Unhandled exception at 0x013c53a0 in Homework4.exe: 0xC0000005: Access violation reading location 0xcccccd1c.", which I assume means I'm messing up a pointer somewhere. The callstack shows line 512 (and therefore the book_traverse() ) as the problem maker. This is what I have so far (omitting the unnecessary code): Thanks in advance!

class PersonnelNode {       // This is a container class
private:
    Personnel       *pNode; // It contains a Personnel class
    PersonnelNode   *pNext; // pointer used to form a linked list
public:
    void setNode(Personnel *pNode) { this->pNode = pNode; }
    void setNext(PersonnelNode *pNext) { this->pNext = pNext; }
    Personnel* getNode() { return pNode; }
    PersonnelNode* getNext() { return pNext; }

    PersonnelNode() {       // constructor
        pNode = NULL;
        pNext = NULL;
    }
} *head = NULL; // declare a global pointer variable head

....

struct Book {
  char title[75];
  char url[75];
  char key;
  Book *left;
  Book *right;  

  Book(char *title, char *url) { // Constructor
    strcpy_s(this->title, title);
    strcpy_s(this->url, url);
    key = title[0];
    left = NULL;
    right = NULL;
  }
};

....

class Student : public Personnel { //inherit from Personnel
   ... (omitted the unnecessary code)
   Book *bookTree;


   //BookTree = NULL in constructor
}

....

int insert_book() {
   PersonnelNode *temp, *prev;
   Personnel *person;
   Student *student;
   Book *newBook;
   char title[75], url[75], sName[75];
   temp = head;

   cout << endl << "@Inserting book node.........." << endl;
   cout << "Enter the student name: ";
   cin.ignore();
   cin.getline(sName, 75);
       //*****My error is probably below here?
   while (temp != NULL) {
       person = temp->getNode();
       if (sName != person->getName()) {
           prev = temp;
           temp = temp->getNext();
       }
       else {
           student = (Student *) person;
       }
   }
   cout << "Enter the book title: ";
   cin.getline(title, 75);
   cout << "Enter the URL: ";
   cin.getline(url, 75);
   newBook = new Book(title, url);
   book_traverse(student->bookTree, newBook); //LINE 512
   return 0;
}

....

//***Recursive function to insert book
void book_traverse(Book* root, Book* newBook) { //Is this right?
   if (root == NULL)                           //I tried Book* &root, but then
    root = newBook;                        //the compiler doesn't like root==NULL
   else if (newBook->key < root->key)
    book_traverse(root->left, newBook);
   else
    book_traverse(root->right, newBook);
}

Answer 1

Declare and initialize necessary variables

1. List item
2. Read the data item to be inserted in the tree say x.
3. Create a new node with its left and right pointers to null.
4. Assign data x to info field of new node.
5. If (tree == NULL) then tree = address of new node else if (x < tree -> info) if(tree->left == NULL) then tree->left = new node else tree = tree->left repeat step 5. else if(x>tree->info) if(tree->right == NULL) then tree->right = new node else tree = tree->right repeat step 5 else if(x == tree->info) print "Duplicated data" and exit
6. For next insertion, goto step 5.

ref:http://www.programmers-point.blogspot.in

Answer 2

I think you need Book**

void book_traverse(Book** root, Book* newBook) 

and then use *root instead of root everywhere, e.g.

*root = newBook

Otherwise in book_traverse you are changing the local copy of root.