If the right answer is provided, I will give that person another link and they c
ID: 3554529 • Letter: I
Question
If the right answer is provided, I will give that person another link and they can write something there and I will rate their answer as best answer and get you can get total of 3000 points.
//library.h
//The library is implemented as a binary search tree
#include "book.h"
#ifndef _LIBRARY_
#define _LIBRARY_
class Library
{
public:
Library();
~Library();
int lengthIs() const;
void retrieveBook(ItemType item, bool & found) const;
void insertBook(ItemType item);
void deleteBook(ItemType item);
//Printing the entire tree in three different order
void printInOrder() const;
void printPreOrder() const;
void printPostOrder() const;
private:
Book * root;
};
#endif
=================================================================
//book.h
#include
using namespace std;
typedef int ItemType;
#ifndef _BOOK_
#define _BOOK_
class Book
{
public:
//constructors
Book();
Book( ItemType nm );
//destructor
~Book();
//public functions
ItemType getInfo();
Book * getLeftChild();
Book * getRightChild();
void setInfo( ItemType item );
void setLeftChild( Book * lc );
void setRightChild(Book * rc );
void print();
private:
ItemType info;
Book * leftChild;
Book * rightChild;
};
#endif
_____________________________________________________________________
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
____________________________________________________________________
//main_binary_search_tree.cpp
#include
#include "library.h"
using namespace std;
int main()
{
Library * lb = new Library();
lb->insertBook(5);
lb->insertBook(9);
lb->insertBook(7);
lb->insertBook(3);
lb->insertBook(8);
lb->insertBook(12);
lb->insertBook(6);
lb->insertBook(4);
lb->insertBook(20);
lb->insertBook(2);
cout << "Number of books in the library is " << lb->lengthIs() << endl;
lb->printInOrder();
lb->printPreOrder();
lb->printPostOrder();
bool fd = false;
lb->retrieveBook(8, fd);
if (fd)
cout << " Book with isbn of 8 has been found." << endl;
else
cout << " Book with isbn of 8 has not been found." << endl;
lb->retrieveBook(11, fd);
if (fd)
cout << "Book with isbn of 11 has been found." << endl;
else
cout << "Book with isbn of 11 has not been found." << endl;
cout << " After deleting the book with isbn of 4";
lb->deleteBook(4);
lb->printInOrder();
cout << " After deleting the book with isbn of 12";
lb->deleteBook(12);
lb->printInOrder();
cout << " After deleting the book with isbn of 9";
lb->deleteBook(9);
lb->printInOrder();
cout << endl;
delete lb;
return 0;
}
====================================================================
// library.cpp
#include "library.h"
//Implementation of the public functions of classes Book and Library
// cant use struct. have to use get
// code here
_______________________________________________________________________
Output should look like this:
//Output of binary search tree
Number of books in the library is 10
Print tree inorder:
2->3->4->5->6->7->8->9->12->20->
Print tree preorder:
5->3->2->4->9->7->6->8->12->20->
Print tree postorder:
2->4->3->6->8->7->20->12->9->5->
Book with isbn of 8 has been found.
Book with isbn of 11 has not been found.
After deleting the book with isbn of 4
Print tree inorder:
2->3->5->6->7->8->9->12->20->
After deleting the book with isbn of 12
Print tree inorder:
2->3->5->6->7->8->9->20->
After deleting the book with isbn of 9
Print tree inorder:
2->3->5->6->7->8->20->
Press any key to continue . . .
Explanation / Answer
LIBRARY.CPP
using namespace std;
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include "library.h"
#include "book.cpp"
Library :: Library()
{
root = NULL;
}
Library :: ~Library()
{
root = NULL;
delete(root);
}
int cal(Book * node)
{
if(node == NULL)
{
return 0;
}
return (1 + cal((*node).getLeftChild()) + cal((*node).getRightChild()) );
}
int Library :: lengthIs() const
{
return cal(root);
}
void Library :: retrieveBook(ItemType item, bool & found)
{
Book * node = root;
found = false;
while(node != NULL)
{
if(item == (*node).getInfo())
{
found = true;
break;
}
else if(item < (*node).getInfo())
{
node = (*node).getLeftChild();
}
else if(item > (*node).getInfo())
{
node = (*node).getRightChild();
}
}
}
void Library :: insertBook(ItemType item)
{
//cout<<" fafafa"<<endl;
Book * node,*temp;
node = new Book;
temp = new Book;
node = root;
if(root == NULL)
{
root = new Book;
(*root).setInfo(item);
(*root).setRightChild(NULL);
(*root).setLeftChild(NULL);
//cout<<" fafafa"<<endl;
return;
}
//cout<<" fafafa"<<endl;
while(node != NULL)
{
temp =node;
//cout<<" fafafa"<<endl;
if(item < (*node).getInfo())
{
node = (*node).getLeftChild();
}
else if(item > (*node).getInfo())
{
node = (*node).getRightChild();
}
}
if((*temp).getInfo() > item)
{
Book * temp1 = new Book;
(*temp1).setInfo(item);
(*temp1).setRightChild(NULL);
(*temp1).setLeftChild(NULL);
(*temp).setLeftChild(temp1);
}
else
{
Book * temp1 = new Book;
(*temp1).setInfo(item);
(*temp1).setRightChild(NULL);
(*temp1).setLeftChild(NULL);
(*temp).setRightChild(temp1);
}
}
Book* find_min(Book*N, Book * root)
{
while((*N).getRightChild()!=NULL)
{
N=(*N).getLeftChild();
}
return N;
}
Book* find_par(Book*M, Book *root)
{
Book*previous,*current;
previous=NULL;
current=root;
while(current!=NULL && (*M).getInfo()!=(*current).getInfo())
{
if((*M).getInfo() > (*current).getInfo())
{
previous=current;
current=(*current).getRightChild();
}
else if((*M).getInfo() < (*current).getInfo())
{
previous=current;
current=(*current).getLeftChild();
}
}
return previous;
}
Book* successor(int item, Book * root)
{
Book *node = root,*y;
while(node != NULL && item != (*node).getInfo())
{
if(item < (*node).getInfo())
{
node = (*node).getLeftChild();
}
else if(item > (*node).getInfo())
{
node = (*node).getRightChild();
}
else if(item == (*node).getInfo())
{
break;
}
}
if(node!=NULL && (*node).getRightChild()!=NULL)
{
return find_min((*node).getRightChild(),root);
}
y=find_par(node,root);
while(y!=NULL && node!=(*y).getRightChild())
{
node=y;
y=find_par(node,root);
}
if(y!=NULL)
return y;
else
return NULL;
}
void Library :: deleteBook(ItemType item)
{
Book * node = root,*y;
int found = 0;
while(node != NULL)
{
if(item != (*node).getInfo())
{
y = node;
}
if(item < (*node).getInfo())
{
node = (*node).getLeftChild();
}
else if(item > (*node).getInfo())
{
node = (*node).getRightChild();
}
else if(item == (*node).getInfo())
{
found = 1;
break;
}
}
Book * x = NULL;
if(found)
{
if((*node).getRightChild()==NULL && (*node).getLeftChild()==NULL)
{
if(item > (*y).getInfo())
{
(*y).setRightChild(x);
return;
}
if(item < (*y).getInfo())
{
(*y).setLeftChild(x);
return;
}
}
else if((*node).getRightChild()==NULL || (*node).getLeftChild()==NULL)
{
if(item > (*y).getInfo())
{
if((*node).getRightChild()!=NULL)
{
Book * t = (*node).getRightChild();
(*y).setRightChild(t);
}
else
(*y).setRightChild((*node).getLeftChild());
}
else
{
if((*node).getRightChild()!=NULL)
(*y).setLeftChild((*node).getRightChild());
else
(*y).setLeftChild((*node).getLeftChild());
}
return;
}
else
{
Book * s=successor(item,root);
Book * par=find_par(s,root);
(*node).setInfo((*s).getInfo());
if(s==(*node).getRightChild())
{
(*node).setRightChild((*s).getRightChild());
//(*s).~Book();
return;
}
(*par).setLeftChild((*s).getRightChild());
//(*s).~Book();
return;
}
}
}
void print_in( Book * p)
{
if(p!=NULL)
{
print_in((*p).getLeftChild());
cout<<(*p).getInfo()<<" ";
print_in((*p).getRightChild());
}
else
return;
}
void print_pre( Book * p)
{
if(p!=NULL)
{
cout<<(*p).getInfo()<<" ";
print_pre((*p).getLeftChild());
print_pre((*p).getRightChild());
}
else return;
}
void print_post(Book * p)
{
if(p!=NULL)
{
print_post((*p).getLeftChild());
print_post((*p).getRightChild());
cout<<(*p).getInfo()<<" ";
}
else return;
}
void Library :: printInOrder() const
{
cout<<" inoreder taversal ";
print_in(root);
}
void Library :: printPreOrder() const{
cout<<" preorder traversal ";
print_pre(root);
}
void Library :: printPostOrder() const{
cout<<" postorder traversal ";
print_post(root);
}
BOOK.CPP
using namespace std;
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include "book.h"
//constructors
Book :: Book()
{
leftChild = NULL;
rightChild = NULL;
}
Book :: Book( ItemType nm )
{
leftChild = NULL;
rightChild = NULL;
info = nm;
}
//destructor
Book :: ~Book()
{
leftChild = NULL;
rightChild = NULL;
delete(this);
}
//public functions
ItemType Book :: getInfo()
{
return info;
}
Book * Book :: getLeftChild()
{
return leftChild;
}
Book * Book :: getRightChild()
{
return rightChild;
}
void Book :: setInfo( ItemType item )
{
info = item;
}
void Book :: setLeftChild( Book * lc )
{
leftChild = lc;
}
void Book :: setRightChild(Book * rc )
{
rightChild = rc;
}
void Book :: print()
{
cout<<info<<" ";
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.