I feel ready to show you my work on creating BST in C++ using double linked list and 3 more functions for manipulating the tree. There is also one more function checking if the tree is real or not.
Declaring the Node:
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
struct BstNode
{ //structuring a node
std::string data;
BstNode* left;
BstNode* right;
int frequ;
};
Node creator func:
BstNode* NewNodeCreator(std::string data) //creating a new node, pointing left and right to null
{
/*I make a pointer, pointing to a new space in memory. To allocate that memory I am using new operator, taking sizeof(BstNode) struct*/
BstNode* newNode = new BstNode();
newNode->data = data;
newNode->left = newNode->right = NULL; // left and right poiners to NULL
newNode->frequ = 1; //for first time in BST
return newNode;
}
Opening the text file and read it's content ( a simple sentence ) :
std::vector<std::string> readFromTxt()
{ //extracting words for a text file
std::ifstream book("text.txt"); //open and read txt file
std::string word;
std::vector<std::string> list;
if (!book.is_open())
{
std::cout << "Unable to open file";
system("pause");
exit(1);
}
while (book >> word)
{
list.emplace_back(word); //store the words in a vector
}
return list;
}
Inserting the new node into the BST:
BstNode* InsertNode(BstNode* root, std::string data)
{ //inserting node and creating a binary tree
if (root == NULL)
{
return NewNodeCreator(data);
}
if (data == root->data) // If the string already exists in BST, count+1 and return
{
(root->frequ)++;
return root;
}
else if (root->data > data)
{
root->left = InsertNode(root->left, data);
}
else
{
root->right = InsertNode(root->right, data);
}
return root;
}
Display the BST in preorder:
void InPreorder(BstNode* root) //function for ptinting the BST in pre-order
{
if (root == NULL)
return;
// print data of node
std::cout << "<" << root->frequ << ">" << " " << root->data << "\n";
//going to left node
InPreorder(root->left);
//going to right
InPreorder(root->right);
}
Searching algorithm:
void Search(BstNode* root, std::string data) //serching through the BST for specific word
{
if (root == NULL)
{
std::cout << "Not found\n";
return;
}
else if (root->data == data)
{
std::cout << "Found\n";
}
else if (data < root->data)
{
std::cout << "Goind left\n";
return Search(root->left, data);
}
else {
std::cout << "Goind right\n";
return Search(root->right, data);
}
}
The delete function and simple func to find the smallest value in the right root:
BstNode* minValue(BstNode* root) //easy way to find the min value in the leftmost leaf
{
BstNode* minData = root;
while (minData->left != NULL)
{
minData = minData->left;
}
return minData;
}
BstNode* NodeDestructor(BstNode* root, std::string data) //deleting a node in BST
{
if (root == NULL)
{
return root;
}
if (data < root->data) // Searching in BST for the value
{
root->left = NodeDestructor(root->left, data);
}
else if (data > root->data)
{
root->right = NodeDestructor(root->right, data);
}
else //when the value is found
{
if (root->left == NULL && root->right == NULL) //for node with no child
{
delete root;
root = NULL;
}
else if (root->left == NULL)//only one child
{
BstNode *temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL)
{
BstNode *temp = root->left;
delete root;
return temp;
}
else //for node with two children
{
BstNode* minData = root->right;
while (minData->left != NULL)
{
minData = minData->left;
}
return minData;
BstNode *temp = minData;
root->data = temp->data;
root->right = NodeDestructor(root->right, temp->data);
}
}
return root;
}
Here I test the BST:
bool isBST(BstNode* root, BstNode* left = NULL, BstNode* right = NULL) //funciton for checking if the tree is properly created
{ // Base condition
if (root == NULL)
{
return true;
}
if (left != NULL and root->data < left->data)
{
return false;
}
if (right != NULL and root->data > right->data)
{
return false;
}
// check recursively for every node.
return isBST(root->left, left, root) and isBST(root->right, root, right);
}
And finally the main function:
int main()
{
BstNode* root = NULL;
int i, note, j;
std::vector<std::string> test; //define a vector to store words from txt file
test = readFromTxt();
for (j = 0; j < test.size(); j++) //This loop is bulding the three passing english words
{
std::string str1 = test[j];
root = InsertNode(root, str1);
}
if (isBST(root, NULL, NULL)) //calling BST check function
{
std::cout << "Is BST\n";
}
else
{
std::cout << "Not a BST\n";
}
InPreorder(root);
Search(root, "in");
NodeDestructor(root, "in");
InPreorder(root);
Search(root, "in");
delete root;
return 0;
}
I hope It's useful for programmers who are trying to implement a BST using C++. I'm open for critical comments.