This program requires you to implement a Binary Search Tree with the following o

Question

This program requires you to implement a Binary Search Tree with the following operations to be executed on the tree: Insert a node in the tree Delete a node from the tree Search for an element in the tree Traverse the tree in Preorder, Inorder and Postorder fashion Print the contents of the tree in preorder fashion The program shall comprise of the following files: TreeNode.h BST.h BST.cpp Driver, cpp The file TreeNode.h shall consist of the class TreeNode. This class shall have BST as its friend class. In addition, this file should also contain the description of the class constructor and accessor functions (thus we avoid creating a TreeNode.cpp) The outline of this file is as follows: Class TreeNode { Friend class BST; Public: TreeNode();//default constructor TreeNode(int i, TreeNode* L = 0; TreeNode* R = 0);//explicit value constructor int getItem () const;//accessor function private: int item; TreeNode *Lchild; TreeNode *Rchild;}; TreeNode()::TreeNode() { Lchild = Rchild = NULL;} TreeNode::TreeNode(int i, TreeNode *L = 0, TreeNode *R = 0): item(i), Lchild(L), Rchild(R) {} int TreeNode::getItem() const { return item;} The file BST.h shall contain the class declaration of class BST. In addition to the public member functions, have 4 utility functions which will help you to perform the search, preorder, postorder and in order traversal operations. The file BST.cpp shall contain the public function descriptions that were declared in file BST.h. The file driver.cpp should test all the functionalities that you have incorporated for the BST.

Explanation / Answer

//TreeNode.h
#ifndef TREENODE_H
#define TREENODE_H

Class TreeNode
{
   Friend class BST;
public:
   TreeNode();
   TreeNode(int i,TreeNode *L=0,TreeNode *R=0);
   int getItem()const;

private:
   int item;
   TreeNode *Lchild;
   TreeNode *Rchild;
};
TreeNode::TreeNode ()
{
Lchild=Rchild=NULL;
}
TreeNode::TreeNode (int i,TreeNode *L=0,TreeNode *R=0):item(i),   Lchild(L),
   Rchild(R)

{}

int TreeNode ::getItem() const()
{
return item;
}

//BST.h
   #include <iostream>

   #include "TreeNode.h"

   using namespace std;

   #ifndef BINARY_SEARCH_TREE

   #define BINARY_SEARCH_TREE

   class BST

   {

   public:

   BST();

   ~BST();

   bool empty() const;

   void searchTree(TreeNode *) const;

   void preorder(TreeNode *) const;

   void inorder(TreeNode *) const;

   void postorder(TreeNode *) const;
       void display()

   private :
       TreeNode *tpter;
       tpter myroot;
  
};

//BST.Cpp
#include<iostream.h>
#include<stdio.h>
#include"BST.h"
BST::BST()
:myRoot(0)
{
}
bool BST::empty()const
{
return myRoot==0;
}
bool BST::searchTree(TreeNode *)const     
{
TreeNode locptr==myRoot;
   bool found =false;
   while(!found && locptr==myRoot)
{
       if(item<locptr->data)
   locptr=locptr->Lchild;
       else if(locptr->data <item)
{
           locptr=locptr->Rchild;
      
           }
   else found=true;
}

return found;
}
void BST:: preorder(TreeNode *temp)
{
if(temp!=NULL)
{
cout<<" "<<temp->item;
preorder(temp->left);
preorder(temp->right);

}
}
void BST::inorder(TreeNode *temp)
{
if(temp!=NULL)
{
    inorder(temp->left);
   cout<<" "<<temp->data;
inorder(temp->right);
}
}
void BST::postorder(NodeTree *temp)
{
if(temp!NULL)
{
postorder(temp->left);
   postorder(temp->right);
   cout<<""<<temp->item;
}
}
void BST:: display()
{
if(root==NULL)
{
cout<<" ***EMPTY TREE**** ";
return;
}
cout<<" THE PREORDER DISPLAY IS: ";
preorder(root);
}

Driver.cpp
#include <iostream.h>
#include<iomanip.h>
#include "BST.h"
#include "TreeNode.h"
int main()
{
BST tree;
cout<<" creating tree with " ;
for(i=0;i<10;i++)
{
NodeTree.insert(i);

}
  
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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