My Work/BST/BinarySearchTree.cpp
#include
#include
#include "Node.cpp"
using namespace std;
//class to represent the tree
class BinarySearchTree
{
private:
Node* root;//base node of the tree
public:
BinarySearchTree()//default constuctor
{
root=NULL;
}
//function to add a word into the tree
void addWord(string w)
{
if(root==NULL)//if tree is empty
{
root = new Node(w);//create a new word at teh root of the tree
}
else//if tree is not empty then we find the location where the new word should be added
{
Node* temp=root;//set a temp variable at teh root, we will move this variable down the tree till it finds an empty space
Node* parent;//this variable will store the location of the parent of the empty space where a new word can be added
while(temp)//loop to run while temp is not empty/NULL
{
parent=temp;//storing the parent location
if(w.compare(temp->getWord())<0)//if given word is lexograqphically smaller than the word present in this location
{
temp=temp->getLeftChild();//move pointer to the left child of the current location
}
else if(w.compare(temp->getWord())>0)//if given word is lexograqphically greater than the word present in this location
{
temp=temp->getRightChild();//move pointer to the right child of the current location
}
else//if the word is the same as the word in the present location, we dont need to add it again, just increase its count and end function
{
temp->addCount();
temp=NULL;
parent=NULL;
}
}
if(parent!=NULL)//if a parent location found for the new owrd to be added
{
if(w.compare(parent->getWord())<0)//if given word is lexograqphically smaller than the word present in this location
{
parent->setLeftChild(new Node(w));//add word as the left child
}
else//if given word is lexograqphically greater than the word present in this location
{
parent->setRightChild(new Node(w));//add word as the right child
}
}
}
}
void printTree()//function to call the recursive pre order printing function
{
printPreOrder(root);//start the function from the root node
}
void printPreOrder(Node* node)//function to print word at given location and recursively call on its children
{
if(node!=NULL)//if given node is not empty
{
cout<
getWord()<<" : "<getCount()< printPreOrder(node->getLeftChild());//call function for left child
printPreOrder(node->getRightChild());//call function for right child
}
}
bool findWord(string w)//function to check if word is present in the tree and to print the path of the search
{
cout< if(root==NULL)//if tree is empty
{
return false;
}
else//if tree is not empty
{
Node* temp=root;//set a temp variable at teh root, we will move this variable down the tree till it finds an empty
while(temp)//loop to run while temp is not empty/NULL
{
cout<getWord();//print current word to show as path
if(w.compare(temp->getWord())<0)//if given word is lexograqphically smaller than the word present in this location
{
cout<<"->";
temp=temp->getLeftChild();//move pointer to the left child of the current location
}
else if(w.compare(temp->getWord())>0)//if given word is lexograqphically greater than the word present in this
{
cout<<"->";
temp=temp->getRightChild();//move pointer to the right child of the current location
}
else//if the word is the same as the word in the present location
{
return true;
}
}
//if in the while loop the word was not found that means it doesnt exist in teh tree
return false;
}
}
//function to find out the minimum value present in the given subtree
Node* minValueNode(Node* parent)
{
Node* temp = parent;//set temp as given node
//move to he left child, till there is no left child left
while(temp->getLeftChild()!=NULL)
{
temp=temp->getLeftChild();
}
//the left most child will have the smallest value in a binary tree, return it
return temp;
}
void deleteWord(string w)//function to delete a word from the tree
{
cout< root=deleteWord(root,w);//delete the given word and set the new root node
}
//fcuntion to delete a given word from the tree and return the new root note
Node* deleteWord(Node* root, string w)
{
if(root==NULL)//if given node is empty
{
cout< return root;
}
if(w.compare(root->getWord())<0)//given word is in the left side
{
root->setLeftChild(deleteWord(root->getLeftChild(),w));//recursive call to delete from left side
}
else if(w.compare(root->getWord())>0)//given word is in the right side
{
root->setRightChild(deleteWord(root->getRightChild(),w));//recursive call to delete from right side
}
else//if the given word is at the current node
{
if(root->getLeftChild()==NULL)//if the current node has no left child and maybe has a right child then we just replace the current node with its right child
{
Node* temp = root->getRightChild();//store link to right child
delete(root);//delete current node
cout< return temp;//return link to right child to be stored in place of the current node
}
else if(root->getRightChild()==NULL)//if the current node has a left child but no right child then we just replace the current node with its left child
{
Node* temp = root->getLeftChild();//store link to left child
delete(root);//delete current node
cout< return temp;//return link to left child to be stored in place of the current node
}
else//if the current node has two children then we have to find the in-order successor of the node and replace it with it
{
Node* temp = minValueNode(root->getRightChild());//find the in-order successor (minimum value int the right side of the sub-tree)
root->setWordAndCount(temp->getWord(),temp->getCount());//set the in-order successor values to the current location
root->setRightChild(deleteWord(root->getRightChild(),temp->getWord()));//delete the in-order successor node from the tree
}
}
return root;//return the current locatiion
}
};
My Work/BST/bin/Debug/BST.exe
My Work/BST/BST.cbp
My Work/BST/BST.depend
# depslib dependency file v1.0
1544494728 source:c:\programming\tfth\35886\my work\bst\node.cpp
1544494749 source:c:\programming\tfth\35886\my work\bst\binarysearchtree.cpp
"Node.cpp"
1544494728 c:\programming\tfth\35886\my work\bst\node.cpp
1544586337 source:c:\programming\tfth\35859\my work\bst\node.cpp
1544588062 source:c:\programming\tfth\35859\my work\bst\driver.cpp
"BinarySearchTree.cpp"
1544587783 c:\programming\tfth\35859\my work\bst\binarysearchtree.cpp
"Node.cpp"
1544586337 c:\programming\tfth\35859\my work\bst\node.cpp
1544587783 source:c:\programming\tfth\35859\my work\bst\binarysearchtree.cpp
"Node.cpp"
My Work/BST/BST.layout
My Work/BST/Driver.cpp
#include
#include
#include
#include
#include "BinarySearchTree.cpp"
using namespace std;
void findWord(BinarySearchTree bst, string w);
int main()
{
BinarySearchTree bst;//create a new tree
ifstream fin("para.txt");//open file to be read
string word;
while(fin >> word)//while the file has a word, store it into the variable
{
for (auto c : word)//for each...