I have these two functions that i have to do and then insert them into the code given. i have attempted to do the code so could come check for me whether its correct.
implement a function, countLeaves, that takes a parameter, a pointer to the root node of a binary search tree, and returns the number of leaves in a binary tree.
implement a function, nodeCount, that returns the number of nodes in the BST tree.
my codings done for functions
Code:
int CountLeaves(Node<Item>* tree)
{
if(tree == NULL)
return 0;
if (tree->left == NULL && tree->right == NULL)
return 1;
else
return (CountLeaves(tree->left) + CountLeaves(tree->right));
}
Code:
int NodeCount(TreeNode<ItemType>* root)
{
if(root == NULL) //base case - if the return 0 if node doesn't exist (don't count it)
return 0;
else
return 1 + NodeCount(root->left) + NodeCount(root->right); //return 1 for the current node, and add the amount of nodes in the left and right subtree
}
the code given which we have to put the functions
Code:
#include "BST.h"
using namespace std;
// BST public member functions
BST::BST()
{
root = NULL;
}
BST::~BST()
{
destroy(root);
}
void BST::insertIntoBST(const string s)
{
root = insert(s, root);
}
void BST::deleteFromBST(const string s)
{
// not in 3SFE504 course notes
// implemented on 17 October 2004 by Ping Brennan
if (!isEmptyBST())
{
deleteNode(s);
}
else
{
cout << "Cannot delete from the empty tree " << endl;
}
}
void BST::printBST() const
{
if (!isEmptyBST())
{
print(root);
}
else
{
cout << "Tree empty" << endl;
}
}
bool BST::isInBST(const string s) const
{
return search(s, root);
}
bool BST::isEmptyBST() const
{
return root==NULL;
}
// Private member functions
// recursive
/* inserts s into the tree pointed to by ptr */
Node* BST::insert(string s, Node* ptr)
{
/* if the pointer is pointing to nothing then we are at the end of
out branch, so allocate new space for a node, insert data, and
set its left and right offspring pointers to NULL otherwise
traverse the tree to find a place to insert the new data */
if (ptr == NULL)
{
ptr = new Node(s);
}
else
{
if (s < ptr->word)
{
ptr->left = insert(s, ptr->left);
}
else
{
ptr->right = insert(s, ptr->right);
}
}
return ptr;
}
void BST::deleteNode(string s)
{
/* finds the node containing the
string, s, (if any) to be deleted.
If the node containing s is found in the BST, this function
calls the function deleteFromTree to delete the node
*/
Node* current; // pointer to traverse the tree
Node* trailCurrent; // pointer behind current
bool found = false;
current = root;
trailCurrent = root;
/* searches for the node containing s (if any) */
while (current != NULL && !found)
{
if (current->word == s)
{
found = true;
}
else
{
trailCurrent = current;
if (current->word > s)
{
current = current->left;
}
else
{
current = current->right;
}
}
} // end while
if (current == NULL)
{
cout << "The delete item is not in the list."<< endl;
}
else if (found)
{
if (current == root)
{
deleteFromTree(root);
}
else if (trailCurrent->word > s)
{
deleteFromTree(trailCurrent->left);
}
else
{
deleteFromTree(trailCurrent->right);
}
}
} //end deleteNode
void BST::deleteFromTree(Node* &p)
{
Node* current; // pointer to traverse the tree
Node* trailCurrent; // pointer behind current
Node* temp; // pointer to delete the node
if (p == NULL)
cerr << "Error: The node to be deleted is NULL."
<< endl;
else if (p->left == NULL && p->right == NULL)
{
/* Case 1: the node to be deleted has no left and
right subtrees, i.e. the node to be deleted is a leaf
*/
temp = p;
p = NULL;
delete temp;
}
else if (p->left == NULL)
{
/* Case 2: the node to be deleted has no left subtree,
i.e. the left subtree is empty, but it has a
nonempty right subtree */
temp = p;
p = temp->right;
delete temp;
}
else if (p->right == NULL)
{
/* Case 3: the node to be deleted has no right
subtree, i.e. the right subtree is empty, but
it has a nonempty left subtree */
temp = p;
p = temp->left;
delete temp;
}
else
{
/* Case 4: the node to be deleted has nonempty
left and right subtrees. */
current = p->left;
trailCurrent = NULL;
while (current->right != NULL)
{
trailCurrent = current;
current = current->right;
} // end while
p->word = current->word;
if (trailCurrent == NULL) // current did not move;
// current == p->left; adjust p
{
p->left = current->left;
}
else
{
trailCurrent->right = current->left;
}
delete current;
} // end else
} //end deleteFromTree
/* deallocates the nodes in the tree pointed to by ptr
post order traversal used */
void BST::destroy(Node* ptr)
{
if (ptr != NULL)
{
destroy(ptr->left);
destroy(ptr->right);
// destructor test code:
//
delete ptr;
}
}
// displays the tree pointed to by ptr
// inorder traversal used
void BST::print(Node* ptr) const
{
if (ptr != NULL)
{
print(ptr->left);
cout << ptr->word << endl;
print(ptr->right);
}
}
// returns true if s is present in the tree pointed to by ptr
// otherwise returns false
bool BST::search(string s, Node* ptr) const
{
if (ptr == NULL)
{
return false;
}
else if (s == ptr->word)
{
return true;
}
else if (s < ptr->word)
{
return search(s, ptr->left);
}
else
{
return search(s, ptr->right);
}
}
could someone help me on this and check whether what i have done is correct. i can provide the header files if needed!