Regarding treeNode
implementation.
- Use self documenting naming for template arguments.
template <typename T>
; what is T
? Let's use something such as ValueType
. Maybe in this case is not really required but nevertheless is a good practice.
- Name your classes and structures with a capital letter.
class treeNode
=> class TreeNode
More like my personal preference, but is good to have your classes starting with capital letter. Standard library is an exception. If you have such a coding guideline then this is no issue at all.
Also many libraries are using the same guideline so it should be more expected to find it in various projects.
- Do not use pointers in C++
If we're using C++ we are not using pointer types unless really required and backed up by a reasonable explanation. Instead, what we do is use smart pointers or objects. So for your treeNode
we would have:
std::shared_ptr<treeNode> left;
std::shared_ptr<treeNode> right;
which leads me to the next point...
- Avoid public data members especially when those are pointers
Have your treeNode
class provide access to those data members through specific methods. You can then include debug only asserts, return objects by ref and do various improvements to your code, something like:
const TreeNode& LeftChild() const
{
assert(_left != NULL);
return *_left;
}
Regarding BST
implementation
(what I said above still applies here - I will not repeat'em).
- Use a self documenting name instead of BST
.
BinarySearchTree
is quite fine. But this is the smallest issues here.
- This class is buggy, semantically wrong, doesn't make sense and is very confusing
Here is a rough list of issues:
- All your method expect a
treeNode
as parameter. Why? As a user of your class I expect to be able to call clear()
without having the need to send the root object.
- I have no idea what
void traversePostorder();
does. Receives nothings, returns nothing. I don't want to read the implementation to figure it out.
- Why are
minHelper
, min
, maxHelper
and max
methods public? I have no idea what they do and why are they public. Again, I don't want to look in your implementation to figure it out.
- Calling clear method will not reset the
size
to 0. So I have a tree, I call clear on it, but when I ask for its size it is not 0. This is a major bug.
isBST
again, the naming is very confusing? Does this check that the current instance is a BST? Why wouldn't it be, since it is named BST. Please rework the naming.
Here is an API example you should be using:
<template ValueType>
class BinarySearchTree
{
public:
///Construct an empty binary search tree.
BinarySearchTree();
void Insert(const ValueType& elementToInsert);
/// Removes the provided element, if found.
/// return true if the element was found or false otherwise
bool Remove(const ValueType& elementToRemove);
/// Search for the provided element.
bool Contains(const ValueType& elementToFind) const;
/// Empty the tree
void Clear();
/// True when size() == 0
bool IsEmpty() const;
/// Number of elements the tree currently holds
size_t Count() const;
typedef const TreeNode<const ValueType&>& NodeConstRef;
//[personal note]:
// I would provide iterators based on TreeNode implementation.
NodeConstRef Root() const;
//Add more... as required.
}
Take note that this is just a simple example I wrote directly here. You should adapt it to fit your needs. If I were to make a binary tree implementation for generic purposes I would aim at providing an interface as close as possible to standard library (mainly providing proper iterators for your tree). This means also changing the TreeNode
implementation and maybe using methods such as size()
, insert
etc. But mainly iterators, those are the most important part.
Then you can use stuff like std::find
or std::transform
and so on for working with your tree, so you no longer need to implement all that.
And finally few more words regarding your implementations...
Method implementations
- Your methods should never make use of std::cout
. Never.
I will not go into details here, just look at other code reviews on C++ codes as this is a very common mistake. There are people who explained it better than I can do it.
- BST<T>::remove
is simply not readable.
Too much code, too chaotic, inconsistent...
For instance, why are your throwing std::runtime_error
if the tree is empty but just logging to console if curr == nullptr
?
Really, I don't even know what to say here, you need to tackle simpler problems before dealing with this. Basically every single line from this method has something wrong in it. Dealing with the API, the treeNode
implementation and cleaning the whole design would render this method useless.
Even more, if you take my advice and use iterators, you can just call std::remove
and completely delete this monstrosity.
... and more
Heavy usage of pointers, dereferencing pointers without checking, many if-else branches, breaking while loops when going through the tree, mixing recursion with iterative algorithms in the same method.
Final suggestions
Please tackle smaller problems. Something that fits in 20 lines of code or so. You could even aim to learn a bit of C before and slowly move to C++. You'll get much better code reviews if you solve problems that match your skill level.
Also, it is mandatory for you to learn standard template library. Learn to work with smart pointers, collections, iterators and algorithms provided by std
.
There are so many improvements here that I could write 20 times as much as I did here and I still wouldn't cover it all. So start with smaller problems or ask review on smaller parts of your code until you get better.