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);
}

Irit Katriel · Accepted Answer · 2012-03-11 11:57:56Z

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.

answered Mar 11, 2012 at 11:57

Irit Katriel

3,5741 gold badge18 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vance Over a year ago

Thanks for the response! That is indeed a problem. However, I think I still need more help. How do I access the ->key of *root, or recursively call the function with the left and right nodes of *root? I feel as if it should be *root->key and *(root->right), but that's not working. Similarly, how does the call to the book_traverse() on Line 512 change with this?

Irit Katriel Over a year ago

(*root)->key and (*root)->right should work. And it would probably be book_traverse(student->bookTree, &newBook)

anil kumar · Accepted Answer · 2013-09-16 12:05:49Z

1

Declare and initialize necessary variables

List item
Read the data item to be inserted in the tree say x.
Create a new node with its left and right pointers to null.
Assign data x to info field of new node.
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
For next insertion, goto step 5.

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

edited Sep 16, 2013 at 12:05

answered Sep 7, 2013 at 8:20

anil kumar

551 gold badge1 silver badge8 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related