//library.h //The library is implemented as a binary search tree #include \"book

Question

//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 <iostream>

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 <string>

#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;

}

Explanation / Answer

/* program for construction of full binary tree */
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node *left;
struct node *right;
};

// A utility function to create a node
struct node* newNode (int data)
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );

temp->data = data;
temp->left = temp->right = NULL;

return temp;
}

// A recursive function to construct Full from pre[] and post[].
// preIndex is used to keep track of index in pre[].
// l is low index and h is high index for the current subarray in post[]
struct node* constructTreeUtil (int pre[], int post[], int* preIndex,
int l, int h, int size)
{
// Base case
if (*preIndex >= size || l > h)
return NULL;

// The first node in preorder traversal is root. So take the node at
// preIndex from preorder and make it root, and increment preIndex
struct node* root = newNode ( pre[*preIndex] );
++*preIndex;

// If the current subarry has only one element, no need to recur
if (l == h)
return root;

// Search the next element of pre[] in post[]
int i;
for (i = l; i <= h; ++i)
if (pre[*preIndex] == post[i])
break;

// Use the index of element found in postorder to divide postorder array in
// two parts. Left subtree and right subtree
if (i <= h)
{
root->left = constructTreeUtil (pre, post, preIndex, l, i, size);
root->right = constructTreeUtil (pre, post, preIndex, i + 1, h, size);
}

return root;
}

// The main function to construct Full Binary Tree from given preorder and
// postorder traversals. This function mainly uses constructTreeUtil()
struct node *constructTree (int pre[], int post[], int size)
{
int preIndex = 0;
return constructTreeUtil (pre, post, &preIndex, 0, size - 1, size);
}

// A utility function to print inorder traversal of a Binary Tree
void printInorder (struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}

// Driver program to test above functions
int main ()
{
int pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7};
int post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1};
int size = sizeof( pre ) / sizeof( pre[0] );

struct node *root = constructTree(pre, post, size);

printf("Inorder traversal of the constructed tree: ");
printInorder(root);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.