-
-
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; | |
| } |
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
emf66@uakron.edu
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.
how to do this for while taking user inputs?