CompE260: Programming Assignment on BST This program requires you to implement a

Question

CompE260: Programming Assignment on BST This program requires you to implement a Binary Search Tree with the following operations to be executed on the tree 1) Insert a node in the tree 2) Delete a node from the tree 3) Search for an element in the tree 4) Traverse the tree in Preorder, Inorder and Postorder fashion 5) 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 getltem 0 const; // accessor function

Explanation / Answer

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

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

BST.h

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

class BST{

};

BST::BST()
{
// constructor  
}

// C function to search a given key in a given BST
struct TreeNode* search(struct TreeNode* , int );

/* A utility function to insert a new TreeNode with given key in BST */
struct TreeNode* insert(struct TreeNode* , int);

/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct TreeNode* TreeNode);

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct TreeNode* TreeNode);

/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct TreeNode* TreeNode);

struct TreeNode * minValueNode(struct TreeNode* TreeNode)
{
struct TreeNode* current = TreeNode;

/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;

return current;
}

/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
struct TreeNode* deleteNode(struct TreeNode* root, int key)
{
// base case
if (root == NULL) return root;

// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is the TreeNode
// to be deleted
else
{
// TreeNode with only one child or no child
if (root->left == NULL)
{
struct TreeNode *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct TreeNode *temp = root->left;
free(root);
return temp;
}

// TreeNode with two children: Get the inorder successor (smallest
// in the right subtree)
struct TreeNode* temp = minValueNode(root->right);

// Copy the inorder successor's content to this TreeNode
root->key = temp->key;

// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}

BST.cpp

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

// C function to search a given key in a given BST
struct TreeNode* search(struct TreeNode* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
  
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);

// Key is smaller than root's key
return search(root->left, key);
}

/* A utility function to insert a new TreeNode with given key in BST */
struct TreeNode* insert(struct TreeNode* TreeNode, int key)
{
/* If the tree is empty, return a new TreeNode */
if (TreeNode == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < TreeNode->key)
TreeNode->left = insert(TreeNode->left, key);
else if (key > TreeNode->key)
TreeNode->right = insert(TreeNode->right, key);

/* return the (unchanged) TreeNode pointer */
return TreeNode;
}

/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct TreeNode* TreeNode)
{
if (TreeNode == NULL)
return;

// first recur on left subtree
printPostorder(TreeNode->left);

// then recur on right subtree
printPostorder(TreeNode->right);

// now deal with the TreeNode
printf("%d ", TreeNode->data);
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct TreeNode* TreeNode)
{
if (TreeNode == NULL)
return;

/* first recur on left child */
printInorder(TreeNode->left);

/* then print the data of TreeNode */
printf("%d ", TreeNode->data);  

/* now recur on right child */
printInorder(TreeNode->right);
}

/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct TreeNode* TreeNode)
{
if (TreeNode == NULL)
return;

/* first print data of TreeNode */
printf("%d ", TreeNode->data);  

/* then recur on left sutree */
printPreorder(TreeNode->left);  

/* now recur on right subtree */
printPreorder(TreeNode->right);
}

driver.cpp

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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