-
-
Save harish-r/a7df7ce576dda35c9660 to your computer and use it in GitHub Desktop.
| /* | |
| ** Binary Search Tree implementation in C++ | |
| ** Harish R | |
| */ | |
| #include<iostream> | |
| using namespace std; | |
| class BST { | |
| struct node { | |
| int data; | |
| node* left; | |
| node* right; | |
| }; | |
| node* root; | |
| node* makeEmpty(node* t) { | |
| if(t == NULL) | |
| return NULL; | |
| { | |
| makeEmpty(t->left); | |
| makeEmpty(t->right); | |
| delete t; | |
| } | |
| return NULL; | |
| } | |
| node* insert(int x, node* t) | |
| { | |
| if(t == NULL) | |
| { | |
| t = new node; | |
| t->data = x; | |
| t->left = t->right = NULL; | |
| } | |
| else if(x < t->data) | |
| t->left = insert(x, t->left); | |
| else if(x > t->data) | |
| t->right = insert(x, t->right); | |
| return t; | |
| } | |
| node* findMin(node* t) | |
| { | |
| if(t == NULL) | |
| return NULL; | |
| else if(t->left == NULL) | |
| return t; | |
| else | |
| return findMin(t->left); | |
| } | |
| node* findMax(node* t) { | |
| if(t == NULL) | |
| return NULL; | |
| else if(t->right == NULL) | |
| return t; | |
| else | |
| return findMax(t->right); | |
| } | |
| node* remove(int x, node* t) { | |
| node* temp; | |
| if(t == NULL) | |
| return NULL; | |
| else if(x < t->data) | |
| t->left = remove(x, t->left); | |
| else if(x > t->data) | |
| t->right = remove(x, t->right); | |
| else if(t->left && t->right) | |
| { | |
| temp = findMin(t->right); | |
| t->data = temp->data; | |
| t->right = remove(t->data, t->right); | |
| } | |
| else | |
| { | |
| temp = t; | |
| if(t->left == NULL) | |
| t = t->right; | |
| else if(t->right == NULL) | |
| t = t->left; | |
| delete temp; | |
| } | |
| return t; | |
| } | |
| void inorder(node* t) { | |
| if(t == NULL) | |
| return; | |
| inorder(t->left); | |
| cout << t->data << " "; | |
| inorder(t->right); | |
| } | |
| node* find(node* t, int x) { | |
| if(t == NULL) | |
| return NULL; | |
| else if(x < t->data) | |
| return find(t->left, x); | |
| else if(x > t->data) | |
| return find(t->right, x); | |
| else | |
| return t; | |
| } | |
| public: | |
| BST() { | |
| root = NULL; | |
| } | |
| ~BST() { | |
| root = makeEmpty(root); | |
| } | |
| void insert(int x) { | |
| root = insert(x, root); | |
| } | |
| void remove(int x) { | |
| root = remove(x, root); | |
| } | |
| void display() { | |
| inorder(root); | |
| cout << endl; | |
| } | |
| void search(int x) { | |
| root = find(root, x); | |
| } | |
| }; | |
| int main() { | |
| BST t; | |
| t.insert(20); | |
| t.insert(25); | |
| t.insert(15); | |
| t.insert(10); | |
| t.insert(30); | |
| t.display(); | |
| t.remove(20); | |
| t.display(); | |
| t.remove(25); | |
| t.display(); | |
| t.remove(30); | |
| t.display(); | |
| return 0; | |
| } |
why is he using destructor
I'm using a destructor to remove the dynamically allocated nodes.
nicely done really organized code
thx,and I will learn BST better
my question is can we make a generic BST that fits all data types?!.. looks stupid question i am a newbie in programming
Yes I do use CPP, thank you for your quick response I will try to do a generic BST
Thank you so much. Very useful for the data structures homework hehe. I'm wondering, when I get to line 109, in public: it says "expected a declaration". I typed exactly what the code shows, does somebody knows why does this happens?
If we initialize Root to 'NULL' in beginning, i.e. line 16, will it have impact on the result?
why is it possible to call insert and remove with one parameter, even though there are two?
@yuryion function overloading, both insert() and both delete are different.
@yuryion function overloading, both insert() and both delete are different.
i am saying you have one parameter in lets say insert(30), which is 30; while the actual function has two, node* insert(int x, node* t), why are you able to only have one?
@yuryion function overloading, both insert() and both delete are different.
i am saying you have one parameter in lets say insert(30), which is 30; while the actual function has two, node* insert(int x, node* t), why are you able to only have one?
Ok, when you call insert(30), then it will call " void insert(int x)" i.e. with one parameter. That's what I was saying that "void insert(int x)" and
"node* insert(int x, node* t)" are not the same functions. so if you want to call "node* insert(int x, node* t)" then you need to pass two parameters.
please refer to this link: https://www.geeksforgeeks.org/function-overloading-c/.
@yuryion function overloading, both insert() and both delete are different.
i am saying you have one parameter in lets say insert(30), which is 30; while the actual function has two, node* insert(int x, node* t), why are you able to only have one?
Ok, when you call insert(30), then it will call " void insert(int x)" i.e. with one parameter. That's what I was saying that "void insert(int x)" and
"node* insert(int x, node* t)" are not the same functions. so if you want to call "node* insert(int x, node* t)" then you need to pass two parameters.
please refer to this link: https://www.geeksforgeeks.org/function-overloading-c/.
ohhh, i didn't see that, thank you
The search function is broken. Searching for a node, will either set root to that node, or set root to NULL, either way your losing handles to pointers and will segfault (eventually, if not the moment search is ran. And search isn't demonstrated either, leading me to believe that the author knows it doesn't work, but chose not to fix it.) Honestly, for beginners, I suggest using loops rather than recursion, as recursion is really easy to get wrong and it very obscure (such as using that search function, I see that as about an hour of debugging by hand for someone experienced, or about a half hour for that same experienced individual to debug with gdb, with nothing but an obscure "segmentation fault" to go off of, and that's if your lucky enough to be on Unix as windows will just say it stopped working and close, with no helpful output).
To the new programmer, I highly suggest looking at the articles on geeksforgeeks regarding BST. They are accurate and well explained, and these gists are a coin toss of good or bad, and even if it is on the first page of google, usually no fix if its wrong, such as this one, which is a few years old, still active, still popular (first page of google for bst), yet still contains, what I'll just call bugs, that are waiting to give devs headaches. And we get enough of those as I'm sure you know.
how to do this for while taking user inputs?
Taking user input should be done somewhere else. The BST should only focus on storing items for retrieval later. But either way user input is another beast, but normally, you'd get user input somewhere else, and use that to set/get data in the tree. See here for ways to read command line input.
You would do something like this:
//create BST
BST tree = new BST();
//Enter data using BufferReader
BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
//variable to hold line
String line;
// Keep reading input until "done" is entered
while(!line.equals("done")) {
// Reading data using readLine
String name = reader.readLine();
//Adding data to BST
tree.insert(name);
}
//Print off list
System.out.println("insert-order: "+tree.asArrayRootUp());
System.out.println("in-order: "+tree.asArrayInOrder());
//etc...
Any good BST class will have methods to get the BST as a collection, and this is a basic example, but I hope it gets you going for now!
how would you implement this using C++ templates?
honestly, you should learn them separately, then tie them together when you understand enough
Best and simple. Perfect 10/10.
Best and simple. Perfect 10/10.
How is it ""best and simple" when it doesn't even work properly? More like "perfect 10/10" to get you fired or to fail a class.
bro i have this bst code which runs perfectly
Ok? How so? I haven't seen this changed and this code still throws segfaults everywhere. Not to mention, using the search function in this code will actually modify the list. How can you say something runs perfectly when a read operations causes an unexpected write?
You say "my functions". have you changed the code after you copied it? Or are you trying to boost the OPs gist without having tried it? Because its about as plain as day the amount of bugs in this code. For example. I mentioned the broken search function.
Function in question:
void search(int x) {
root = find(root, x);
}
//...
node* find(node* t, int x) {
if(t == NULL)
return NULL;
else if(x < t->data)
return find(t->left, x);
else if(x > t->data)
return find(t->right, x);
else
return t;
}
Where, in any BST (find one other than this), would the search function not only not return a result, but would also fragment the entire list?
Because I'm not sure how well versed you are in general programming, but if you look at that search (and its supporting find) method, you can very clearly see that anytime search is called, the root of the list will be set to the searched value if found else null. You can say it works and its perfect all you want, but the proof is in the pudding.
Now, because I have a good feeling your still going to try and defend this bad piece of code saying its somehow perfect, let me enlighten you, and hopefully teach you something to keep you from failing again in the future.
Let's say the BST contains 2,3,6,8,10.
Lets say I search for 8.
find will recurse until it finds 8, then return the node holding 8 to search, which will set the root of the list to that node.
Assuming the tree is structured like:
6
3 8
2 10
Then you've just lost your pointers to 6,3,2 because this broken search will change the list to:
8
10
without even deconstructing the nodes. So yes, this WILL/DOES segfault. And thats ignoring the fact that a 'normal' bst search would return a boolean, not be void. If you want, I can tear apart the rest of this bogus code and show you exactly how bad it is (its bad)
Honestly, severely misleading information such as this should not be allowed on Github period. Atleast not publicly with random no ones claiming it works "perfectly"
Hi,
I am a student at the University of Akron studying Computer Engineering. One of my class projects is to implement an AVL tree. I need to compare my tree implementation with some other trees for search, insert, and delete operations. There's no open source license on your BST implementation - may I have your permission to run test cases on your code for this project?
Thanks,
Elena Falcione
[email protected]
Hi,
I am a student at DAIICT, India. Studying ICT with machine learning specialization. This is an article, I have written while practicing the algorithms. I gathers a lot of information and wrote this articles of a binary tree in java: this is the link-> Click here
Hello @harish-r! In your implementation of BST search, you are changing the root of the tree every time you search. This is undesired behavior in a BST.
Perhaps there's a mistake in search() since it's just a public interface "returning" what find() returns. Thus root MUST NOT BE MODIFIED
Once it's fixed, everything is good.
When x == t->data, then it will be skipped and no action will be taken.