Binary search tree in C++, and display, search and delete functions
up vote
3
down vote
favorite
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 foundn";
return;
}
else if (root->data == data)
{
std::cout << "Foundn";
}
else if (data < root->data)
{
std::cout << "Goind leftn";
return Search(root->left, data);
}
else {
std::cout << "Goind rightn";
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 BSTn";
}
else
{
std::cout << "Not a BSTn";
}
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.
c++ tree functional-programming binary-search
New contributor
add a comment |
up vote
3
down vote
favorite
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 foundn";
return;
}
else if (root->data == data)
{
std::cout << "Foundn";
}
else if (data < root->data)
{
std::cout << "Goind leftn";
return Search(root->left, data);
}
else {
std::cout << "Goind rightn";
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 BSTn";
}
else
{
std::cout << "Not a BSTn";
}
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.
c++ tree functional-programming binary-search
New contributor
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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 foundn";
return;
}
else if (root->data == data)
{
std::cout << "Foundn";
}
else if (data < root->data)
{
std::cout << "Goind leftn";
return Search(root->left, data);
}
else {
std::cout << "Goind rightn";
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 BSTn";
}
else
{
std::cout << "Not a BSTn";
}
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.
c++ tree functional-programming binary-search
New contributor
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 foundn";
return;
}
else if (root->data == data)
{
std::cout << "Foundn";
}
else if (data < root->data)
{
std::cout << "Goind leftn";
return Search(root->left, data);
}
else {
std::cout << "Goind rightn";
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 BSTn";
}
else
{
std::cout << "Not a BSTn";
}
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.
c++ tree functional-programming binary-search
c++ tree functional-programming binary-search
New contributor
New contributor
edited Nov 16 at 23:03
Cris Luengo
2,389319
2,389319
New contributor
asked Nov 16 at 14:33
Mitko Donchev
406
406
New contributor
New contributor
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
Overview
Your biggest issue is encapsulation (there is none).
Start writing classes with methods.
Only allow the class methods to modify the internal members.
I would note that std::map
has the same characteristics as a balanced binary search tree (this implies its implementation is a Red/Black tree).
I don't mention it in the code below. But when passing object you usally pass by const reference. This will avoid unneeded copies being created. You pass the strings around by value which cause a copy of the string to be created with each function call (that's expensive).
If you re-write to include all the above advice we can discuss the opportunities that come with using move semantics.
Code Review
Why is this a function?
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;
}
This should be the constructor of BstNode
There is a much simpler way to read a text file into a vector.
std::vector<std::string> list;
...
while (book >> word)
{
list.emplace_back(word); //store the words in a vector
}
I would write this as:
// Iterate over a stream and build a vector.
std::vector<std::string> list(std::istream_iterator<std::string>(book),
std::istream_iterator());
I would avoid using exit().
if (!book.is_open())
{
std::cout << "Unable to open file";
system("pause");
exit(1);
}
This is an unexpected (otherwise you would not exit). So throw an exception. You can catch exceptions in main and display an error message. By doing it this way your code to display error messages is in a single location and not spread around the code. This makes the error messages (or the way the application exits consistent across all errors).
if (!book.is_open()) {
throw std::runtime_error("Unable to open file");
}
Another place where you have a function rather than a method:
BstNode* InsertNode(BstNode* root, std::string data);
The trouble here is that you call your insert like this
root = InsertNode(root, "Blob");
But there is nothing to stop a person modifying the variable root
. What happens if they modify the tress pointed at by root so that it is no longer consistent with a BST?
What you should do is make root
a private member of a class. The only way to modify root
is to call the InsertNode()
method. That way you know that your tree is always going to be a BST.
class BSTTree
{
private:
BSTNode* root;
void InsertNode(BSTNode* node, std::string data);
public:
BSTTree()
: root(nullptr)
{}
void InsertNode(std::string data) {
root = InsertNode(root, data);
}
}
You are definitely going in the correct direction here. But you need to fix a couple of bugs here:
else //for node with two children
{
BstNode* minData = root->right;
while (minData->left != NULL)
{
minData = minData->left;
}
return minData; // This return is wrong.
BstNode *temp = minData;
root->data = temp->data;
root->right = NodeDestructor(root->right, temp->data);
}
I think you want:
else //for node with two children
{
BstNode* minData = minValue(root->right);
root->data = minData->data;
root-> frequ= minData-> frequ;
root->right = NodeDestructor(root->right, root->data);
}
You might yet mention that it is not the application's task to keep a console window open, so one shouldn't dosystem("pause");
or alternatively callgetchar
,fgetc
or similar. Doing so makes the application unusable in script files.
– Aconcagua
Nov 17 at 1:14
Also, mention (and/or demonstrate) thatstd::cerr
is preferable tostd::cout
for error messages.
– Toby Speight
15 hours ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
Overview
Your biggest issue is encapsulation (there is none).
Start writing classes with methods.
Only allow the class methods to modify the internal members.
I would note that std::map
has the same characteristics as a balanced binary search tree (this implies its implementation is a Red/Black tree).
I don't mention it in the code below. But when passing object you usally pass by const reference. This will avoid unneeded copies being created. You pass the strings around by value which cause a copy of the string to be created with each function call (that's expensive).
If you re-write to include all the above advice we can discuss the opportunities that come with using move semantics.
Code Review
Why is this a function?
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;
}
This should be the constructor of BstNode
There is a much simpler way to read a text file into a vector.
std::vector<std::string> list;
...
while (book >> word)
{
list.emplace_back(word); //store the words in a vector
}
I would write this as:
// Iterate over a stream and build a vector.
std::vector<std::string> list(std::istream_iterator<std::string>(book),
std::istream_iterator());
I would avoid using exit().
if (!book.is_open())
{
std::cout << "Unable to open file";
system("pause");
exit(1);
}
This is an unexpected (otherwise you would not exit). So throw an exception. You can catch exceptions in main and display an error message. By doing it this way your code to display error messages is in a single location and not spread around the code. This makes the error messages (or the way the application exits consistent across all errors).
if (!book.is_open()) {
throw std::runtime_error("Unable to open file");
}
Another place where you have a function rather than a method:
BstNode* InsertNode(BstNode* root, std::string data);
The trouble here is that you call your insert like this
root = InsertNode(root, "Blob");
But there is nothing to stop a person modifying the variable root
. What happens if they modify the tress pointed at by root so that it is no longer consistent with a BST?
What you should do is make root
a private member of a class. The only way to modify root
is to call the InsertNode()
method. That way you know that your tree is always going to be a BST.
class BSTTree
{
private:
BSTNode* root;
void InsertNode(BSTNode* node, std::string data);
public:
BSTTree()
: root(nullptr)
{}
void InsertNode(std::string data) {
root = InsertNode(root, data);
}
}
You are definitely going in the correct direction here. But you need to fix a couple of bugs here:
else //for node with two children
{
BstNode* minData = root->right;
while (minData->left != NULL)
{
minData = minData->left;
}
return minData; // This return is wrong.
BstNode *temp = minData;
root->data = temp->data;
root->right = NodeDestructor(root->right, temp->data);
}
I think you want:
else //for node with two children
{
BstNode* minData = minValue(root->right);
root->data = minData->data;
root-> frequ= minData-> frequ;
root->right = NodeDestructor(root->right, root->data);
}
You might yet mention that it is not the application's task to keep a console window open, so one shouldn't dosystem("pause");
or alternatively callgetchar
,fgetc
or similar. Doing so makes the application unusable in script files.
– Aconcagua
Nov 17 at 1:14
Also, mention (and/or demonstrate) thatstd::cerr
is preferable tostd::cout
for error messages.
– Toby Speight
15 hours ago
add a comment |
up vote
6
down vote
accepted
Overview
Your biggest issue is encapsulation (there is none).
Start writing classes with methods.
Only allow the class methods to modify the internal members.
I would note that std::map
has the same characteristics as a balanced binary search tree (this implies its implementation is a Red/Black tree).
I don't mention it in the code below. But when passing object you usally pass by const reference. This will avoid unneeded copies being created. You pass the strings around by value which cause a copy of the string to be created with each function call (that's expensive).
If you re-write to include all the above advice we can discuss the opportunities that come with using move semantics.
Code Review
Why is this a function?
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;
}
This should be the constructor of BstNode
There is a much simpler way to read a text file into a vector.
std::vector<std::string> list;
...
while (book >> word)
{
list.emplace_back(word); //store the words in a vector
}
I would write this as:
// Iterate over a stream and build a vector.
std::vector<std::string> list(std::istream_iterator<std::string>(book),
std::istream_iterator());
I would avoid using exit().
if (!book.is_open())
{
std::cout << "Unable to open file";
system("pause");
exit(1);
}
This is an unexpected (otherwise you would not exit). So throw an exception. You can catch exceptions in main and display an error message. By doing it this way your code to display error messages is in a single location and not spread around the code. This makes the error messages (or the way the application exits consistent across all errors).
if (!book.is_open()) {
throw std::runtime_error("Unable to open file");
}
Another place where you have a function rather than a method:
BstNode* InsertNode(BstNode* root, std::string data);
The trouble here is that you call your insert like this
root = InsertNode(root, "Blob");
But there is nothing to stop a person modifying the variable root
. What happens if they modify the tress pointed at by root so that it is no longer consistent with a BST?
What you should do is make root
a private member of a class. The only way to modify root
is to call the InsertNode()
method. That way you know that your tree is always going to be a BST.
class BSTTree
{
private:
BSTNode* root;
void InsertNode(BSTNode* node, std::string data);
public:
BSTTree()
: root(nullptr)
{}
void InsertNode(std::string data) {
root = InsertNode(root, data);
}
}
You are definitely going in the correct direction here. But you need to fix a couple of bugs here:
else //for node with two children
{
BstNode* minData = root->right;
while (minData->left != NULL)
{
minData = minData->left;
}
return minData; // This return is wrong.
BstNode *temp = minData;
root->data = temp->data;
root->right = NodeDestructor(root->right, temp->data);
}
I think you want:
else //for node with two children
{
BstNode* minData = minValue(root->right);
root->data = minData->data;
root-> frequ= minData-> frequ;
root->right = NodeDestructor(root->right, root->data);
}
You might yet mention that it is not the application's task to keep a console window open, so one shouldn't dosystem("pause");
or alternatively callgetchar
,fgetc
or similar. Doing so makes the application unusable in script files.
– Aconcagua
Nov 17 at 1:14
Also, mention (and/or demonstrate) thatstd::cerr
is preferable tostd::cout
for error messages.
– Toby Speight
15 hours ago
add a comment |
up vote
6
down vote
accepted
up vote
6
down vote
accepted
Overview
Your biggest issue is encapsulation (there is none).
Start writing classes with methods.
Only allow the class methods to modify the internal members.
I would note that std::map
has the same characteristics as a balanced binary search tree (this implies its implementation is a Red/Black tree).
I don't mention it in the code below. But when passing object you usally pass by const reference. This will avoid unneeded copies being created. You pass the strings around by value which cause a copy of the string to be created with each function call (that's expensive).
If you re-write to include all the above advice we can discuss the opportunities that come with using move semantics.
Code Review
Why is this a function?
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;
}
This should be the constructor of BstNode
There is a much simpler way to read a text file into a vector.
std::vector<std::string> list;
...
while (book >> word)
{
list.emplace_back(word); //store the words in a vector
}
I would write this as:
// Iterate over a stream and build a vector.
std::vector<std::string> list(std::istream_iterator<std::string>(book),
std::istream_iterator());
I would avoid using exit().
if (!book.is_open())
{
std::cout << "Unable to open file";
system("pause");
exit(1);
}
This is an unexpected (otherwise you would not exit). So throw an exception. You can catch exceptions in main and display an error message. By doing it this way your code to display error messages is in a single location and not spread around the code. This makes the error messages (or the way the application exits consistent across all errors).
if (!book.is_open()) {
throw std::runtime_error("Unable to open file");
}
Another place where you have a function rather than a method:
BstNode* InsertNode(BstNode* root, std::string data);
The trouble here is that you call your insert like this
root = InsertNode(root, "Blob");
But there is nothing to stop a person modifying the variable root
. What happens if they modify the tress pointed at by root so that it is no longer consistent with a BST?
What you should do is make root
a private member of a class. The only way to modify root
is to call the InsertNode()
method. That way you know that your tree is always going to be a BST.
class BSTTree
{
private:
BSTNode* root;
void InsertNode(BSTNode* node, std::string data);
public:
BSTTree()
: root(nullptr)
{}
void InsertNode(std::string data) {
root = InsertNode(root, data);
}
}
You are definitely going in the correct direction here. But you need to fix a couple of bugs here:
else //for node with two children
{
BstNode* minData = root->right;
while (minData->left != NULL)
{
minData = minData->left;
}
return minData; // This return is wrong.
BstNode *temp = minData;
root->data = temp->data;
root->right = NodeDestructor(root->right, temp->data);
}
I think you want:
else //for node with two children
{
BstNode* minData = minValue(root->right);
root->data = minData->data;
root-> frequ= minData-> frequ;
root->right = NodeDestructor(root->right, root->data);
}
Overview
Your biggest issue is encapsulation (there is none).
Start writing classes with methods.
Only allow the class methods to modify the internal members.
I would note that std::map
has the same characteristics as a balanced binary search tree (this implies its implementation is a Red/Black tree).
I don't mention it in the code below. But when passing object you usally pass by const reference. This will avoid unneeded copies being created. You pass the strings around by value which cause a copy of the string to be created with each function call (that's expensive).
If you re-write to include all the above advice we can discuss the opportunities that come with using move semantics.
Code Review
Why is this a function?
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;
}
This should be the constructor of BstNode
There is a much simpler way to read a text file into a vector.
std::vector<std::string> list;
...
while (book >> word)
{
list.emplace_back(word); //store the words in a vector
}
I would write this as:
// Iterate over a stream and build a vector.
std::vector<std::string> list(std::istream_iterator<std::string>(book),
std::istream_iterator());
I would avoid using exit().
if (!book.is_open())
{
std::cout << "Unable to open file";
system("pause");
exit(1);
}
This is an unexpected (otherwise you would not exit). So throw an exception. You can catch exceptions in main and display an error message. By doing it this way your code to display error messages is in a single location and not spread around the code. This makes the error messages (or the way the application exits consistent across all errors).
if (!book.is_open()) {
throw std::runtime_error("Unable to open file");
}
Another place where you have a function rather than a method:
BstNode* InsertNode(BstNode* root, std::string data);
The trouble here is that you call your insert like this
root = InsertNode(root, "Blob");
But there is nothing to stop a person modifying the variable root
. What happens if they modify the tress pointed at by root so that it is no longer consistent with a BST?
What you should do is make root
a private member of a class. The only way to modify root
is to call the InsertNode()
method. That way you know that your tree is always going to be a BST.
class BSTTree
{
private:
BSTNode* root;
void InsertNode(BSTNode* node, std::string data);
public:
BSTTree()
: root(nullptr)
{}
void InsertNode(std::string data) {
root = InsertNode(root, data);
}
}
You are definitely going in the correct direction here. But you need to fix a couple of bugs here:
else //for node with two children
{
BstNode* minData = root->right;
while (minData->left != NULL)
{
minData = minData->left;
}
return minData; // This return is wrong.
BstNode *temp = minData;
root->data = temp->data;
root->right = NodeDestructor(root->right, temp->data);
}
I think you want:
else //for node with two children
{
BstNode* minData = minValue(root->right);
root->data = minData->data;
root-> frequ= minData-> frequ;
root->right = NodeDestructor(root->right, root->data);
}
edited 15 hours ago
Toby Speight
21.9k536108
21.9k536108
answered Nov 16 at 22:16
Martin York
71.9k481253
71.9k481253
You might yet mention that it is not the application's task to keep a console window open, so one shouldn't dosystem("pause");
or alternatively callgetchar
,fgetc
or similar. Doing so makes the application unusable in script files.
– Aconcagua
Nov 17 at 1:14
Also, mention (and/or demonstrate) thatstd::cerr
is preferable tostd::cout
for error messages.
– Toby Speight
15 hours ago
add a comment |
You might yet mention that it is not the application's task to keep a console window open, so one shouldn't dosystem("pause");
or alternatively callgetchar
,fgetc
or similar. Doing so makes the application unusable in script files.
– Aconcagua
Nov 17 at 1:14
Also, mention (and/or demonstrate) thatstd::cerr
is preferable tostd::cout
for error messages.
– Toby Speight
15 hours ago
You might yet mention that it is not the application's task to keep a console window open, so one shouldn't do
system("pause");
or alternatively call getchar
, fgetc
or similar. Doing so makes the application unusable in script files.– Aconcagua
Nov 17 at 1:14
You might yet mention that it is not the application's task to keep a console window open, so one shouldn't do
system("pause");
or alternatively call getchar
, fgetc
or similar. Doing so makes the application unusable in script files.– Aconcagua
Nov 17 at 1:14
Also, mention (and/or demonstrate) that
std::cerr
is preferable to std::cout
for error messages.– Toby Speight
15 hours ago
Also, mention (and/or demonstrate) that
std::cerr
is preferable to std::cout
for error messages.– Toby Speight
15 hours ago
add a comment |
Mitko Donchev is a new contributor. Be nice, and check out our Code of Conduct.
Mitko Donchev is a new contributor. Be nice, and check out our Code of Conduct.
Mitko Donchev is a new contributor. Be nice, and check out our Code of Conduct.
Mitko Donchev is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207811%2fbinary-search-tree-in-c-and-display-search-and-delete-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown