home study engineering computer science questions and an

home / study / engineering / computer science / questions and answers / n this assignment you are asked to write a simple ...

Your question has been posted.

We\'ll notify you when a Chegg Expert has answered. Post another question.

Question: N this assignment you are asked to write a simple ...

Bookmark

EDIT QUESTION

n this assignment you are asked to write a simple driver program and set of functions (maybein a library) that can be performed on a binary search tree.

Your program should allow user to insert/delete integer values into the binary search tree along with several other operations on the binary search tree. You can use the code given in slides. But this time your key will be int! Specifically, your program will ask user to enter a command and related parameters (if any) in a loop, and then perform the given commands. Here is the list of commands that your program must implement:

* insert

*find\'

*delete

*list inorder

*list preorder

*list postorder

*list levelorder

* max

* min

* height

*count

* sum

*quit

Solution

#include <iostream>
using namespace std;

int sum1=0;
// A generic tree node class
class Node {
int key;
Node* left;
Node* right;
Node* parent;
public:
Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
void setKey(int aKey) { key = aKey; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
void setParent(Node* aParent) { parent = aParent; };
int Key() { return key; };
Node* Left() { return left; };
Node* Right() { return right; };
Node* Parent() { return parent; };
};

// Binary Search Tree class
class Tree {
Node* root;
public:
Tree();
~Tree();
Node* Root() { return root; };
void addNode(int key);
Node* findNode(int key, Node* parent);
void Preorder(Node* node);
void Inorder(Node* node);
void Postorder(Node* node);
void deleteNode(int key);
Node* min(Node* node);
Node* max(Node* node);
Node* successor(int key, Node* parent);
Node* predecessor(int key, Node* parent);
int Height(Node* node);
int count(Node* node);
void sum(Node* node);
private:
void addNode(int key, Node* leaf);
void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
root = NULL;
}

// Destructor
Tree::~Tree() {
freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
if ( leaf != NULL )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}

// Add a node [O(height of tree) on average]
void Tree::addNode(int key)
{
// No elements. Add the root
if ( root == NULL ) {
cout << \"add root node ... \" << key << endl;
Node* n = new Node();
n->setKey(key);
root = n;
}
else {
cout << \"add other node ... \" << key << endl;
addNode(key, root);
}
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() )
{
if ( leaf->Left() != NULL )
addNode(key, leaf->Left());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setLeft(n);
}
}
else
{
if ( leaf->Right() != NULL )
addNode(key, leaf->Right());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setRight(n);
}
}
}

// Find a node [O(height of tree) on average]
Node* Tree::findNode(int key, Node* node)
{
if ( node == NULL )
return NULL;
else if ( node->Key() == key )
return node;
else if ( key <= node->Key() )
findNode(key, node->Left());
else if ( key > node->Key() )
findNode(key, node->Right());
else
return NULL;
}

int Tree::Height(Node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = Height(node->Left());
int rDepth = Height(node->Right());

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

// Print the tree
void Tree::Preorder(Node* node)
{
if ( node )
{
cout << node->Key() << \" \";
Preorder(node->Left());
Preorder(node->Right());
}
}

void Tree::sum(Node* node)
{
if ( node )
{
sum1=sum1+node->Key();
sum(node->Left());
sum(node->Right());
}
}

void Tree::Inorder(Node* node)
{
if ( node )
{
  
Preorder(node->Left());
cout << node->Key() << \" \";
Preorder(node->Right());
}
}

void Tree::Postorder(Node* node)
{
if ( node )
{
  
Preorder(node->Left());
  
Preorder(node->Right());
cout << node->Key() << \" \";
}
}

// Find the node with min key
// Traverse the left sub-tree recursively
// till left sub-tree is empty to get min
Node* Tree::min(Node* node)
{
if ( node == NULL )
return NULL;

if ( node->Left() )
min(node->Left());
else
return node;
}

// Find the node with max key
// Traverse the right sub-tree recursively
// till right sub-tree is empty to get max
Node* Tree::max(Node* node)
{
if ( node == NULL )
return NULL;

if ( node->Right() )
max(node->Right());
else
return node;
}

int Tree::count(Node* node)
{
if ( node == NULL )
return 0;

  
int i=1+count(node->Left())+count(node->Right());
return i;
}

// Find successor to a node
// Find the node, get the node with max value
// for the right sub-tree to get the successor
Node* Tree::successor(int key, Node *node)
{
Node* thisKey = findNode(key, node);
if ( thisKey )
return max(thisKey->Right());
}

// Find predecessor to a node
// Find the node, get the node with max value
// for the left sub-tree to get the predecessor
Node* Tree::predecessor(int key, Node *node)
{
Node* thisKey = findNode(key, node);
if ( thisKey )
return max(thisKey->Left());
}

// Delete a node
// (1) If leaf just delete
// (2) If only one child delete this node and replace
// with the child
// (3) If 2 children. Find the predecessor (or successor).
// Delete the predecessor (or successor). Replace the
// node to be deleted with the predecessor (or successor).
void Tree::deleteNode(int key)
{
// Find the node.
Node* thisKey = findNode(key, root);

// (1)
if ( thisKey->Left() == NULL && thisKey->Right() == NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(NULL);
else
thisKey->Parent()->setLeft(NULL);

delete thisKey;
}

// (2)
if ( thisKey->Left() == NULL && thisKey->Right() != NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(thisKey->Right());
else
thisKey->Parent()->setLeft(thisKey->Right());

delete thisKey;
}
if ( thisKey->Left() != NULL && thisKey->Right() == NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(thisKey->Left());
else
thisKey->Parent()->setLeft(thisKey->Left());

delete thisKey;
}

// (3)
if ( thisKey->Left() != NULL && thisKey->Right() != NULL )
{
Node* sub = predecessor(thisKey->Key(), thisKey);
if ( sub == NULL )
sub = successor(thisKey->Key(), thisKey);

if ( sub->Parent()->Key() <= sub->Key() )
sub->Parent()->setRight(sub->Right());
else
sub->Parent()->setLeft(sub->Left());

thisKey->setKey(sub->Key());
delete sub;
}
}

// Test main program
int main() {
Tree* tree = new Tree();

  

  
  
  

while(1)
{

cout<<\"Enter Choice\ \";

int d;
cout<<\"1)Insert node\ 2)Delete node\ 3)Find node\ 4)List Preorder\ 5)List Inorder\ 6)List Postorder\ 7)MAx\ 8)Min\ 9)Height\ 10)Count\ 11)Sum\ 12)Quit\ \";
int n;
cin>>n;
switch(n)
{
case 1:
cout<<\"Enter data\ \";
  
cin>>d;
tree->addNode(d);break;

case 2:
cout<<\"Enter data to delete\ \";
  
cin>>d;
tree->deleteNode(d);break;

case 3:
cout<<\"Enter data to Search\ \";
  
cin>>d;

if ( tree->findNode(d, tree->Root()) )
cout << \"Node \"<<d<<\" found\" << endl;
else
cout << \"Node \"<<d<<\" not found\" << endl;
break;

case 4:
tree->Preorder(tree->Root());
cout << endl;
break;

case 5:
tree->Inorder(tree->Root());
cout << endl;
break;
case 6:
tree->Postorder(tree->Root());
cout << endl;
break;

case 7:
cout << \"Max=\" << tree->max(tree->Root())->Key() << endl;
break;

case 8:
cout << \"Min=\" << tree->min(tree->Root())->Key() << endl;
break;

case 9:
cout<<\"Height \"<<tree->Height(tree->Root())<<endl;
break;
case 10:
cout<<\"Count is \"<<tree->count(tree->Root())<<endl;
break;
case 11:
  
tree->sum(tree->Root());
cout<<\"Sum is \"<<sum1<<endl;
break;

case 12:return 0;

break;

}
}
return 0;
}

=================================================