My Work/BST/BinarySearchTree.cpp
#include
#include
#include "Node.cpp"
using namespace std;
class to represent the tree
class BinarySearchTree
{
private:
Node* root;
ase node of the tree
public:
BinarySearchTree()
default constucto
{
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 cu
ent 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 cu
ent 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
node->getWord()
" : "
node->getCount()
endl;
print word and its count
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
endl;
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
temp->getWord();
print cu
ent 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 cu
ent 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 cu
ent 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
endl;
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
w
" not found";
word not in the tree
return root;
}
if(w.compare(root->getWord())<0)
given word is in the left side
{
root->setLeftChild(deleteWord(root->getLeftChild(),w));
ecursive 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));
ecursive call to delete from right side
}
else
if the given word is at the cu
ent node
{
if(root->getLeftChild()==NULL)
if the cu
ent node has no left child and maybe has a right child then we just replace the cu
ent node with its right child
{
Node* temp = root->getRightChild();
store link to right child
delete(root);
delete cu
ent node
cout
w
" deleted";
return temp;
eturn link to right child to be stored in place of the cu
ent node
}
else if(root->getRightChild()==NULL)
if the cu
ent node has a left child but no right child then we just replace the cu
ent node with its left child
{
Node* temp = root->getLeftChild();
store link to left child
delete(root);
delete cu
ent node
cout
w
" deleted";
return temp;
eturn link to left child to be stored in place of the cu
ent node
}
else
if the cu
ent 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 cu
ent location
root->setRightChild(deleteWord(root->getRightChild(),temp->getWord()));
delete the in-order successor node from the tree
}
}
return root;
eturn the cu
ent locatiion
}
};
My Work/BST
in/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...