OK, let's start at the first question you should ask yourself when writing code:
Am I helping the reader figure out what's going on?
Let's start by looking at Main.cpp. Here, there are a few small clues that might help me figure out what's going on, but they're misleading. First, you are including a file called ClassTree.h. This name suggests to me that it provides a class called ClassTree, or at the very least a module that is concerned with class trees. What's a class tree? Well, I've never heard of it before, but the name suggest that it's a tree of classes. Maybe it's for something in biology, but it seems more like it's for some sort of code analysis. Next we have main, which has no comments, and only references the names P1, Node, and menu, which are very close to the least informative names you could have in a program. Well, let's take a look at what menu does, maybe we can get a hint. Wait, there's no definition for menu, only a declaration. We don't even have a clue as to where it's defined; I guess we'll have to look at a Makefile or grep for menu in the other files in this directory.
So this brings me to my first concrete suggestion: Never declare a function that's defined in an unrelated file. Instead, declare them in a header file with the same basename as the source file that defines them.
Second concrete suggestion: Give things meaningful names. What does this program do? I don't know, the source file is named Main.cpp and the library that defines its core functionality is called ForMain.cpp.
Third concrete suggestion: Document your classes and functions! Documentation starts with a good name, but when some behavior isn't obvious from the name, it should be present in a comment.
Now let's visit ClassTree.h. As alluded to earlier, this isn't a very good name for this file. It's not a tree of classes. The data structure you're defining is a binary tree. The fact that it's implemented using a class is (a) in some sense an implementation detail, and therefore not the thing to emphasize in its name, and (b) essentially assumed in C++. So let's call it BinaryTree.h.
As a relatively minor point, let me say that you should always put your code in namespaces. When you put everything into the global namespace, you are significantly increasing the likelihood of name collisions, which can sometimes not be detected by the compiler or linker and which may lead to subtly wrong behavior at run time.
Now let's visit your class design. Others have mentioned some of the problems here, but most of them come from one error at the root: You have inappropriately overspecialized the design of this class to this specific use case. You've written a little test program here to exercise your binary tree, but you've basically made the tree unusable in other programs. Let's look at some of the problems that arise from that:
- The
count mechanism makes the assumption that you will only ever have one tree in your program. If you have multiple trees, they will trample each other's counts.
- You have committed yourself to
int data in the nodes. But binary trees like this work with lots of data types, as long as they can be ordered and compared for equality. This should be a template class!
Node's methods have confusing names and signatures, and no documentation. This probably wasn't obvious to you since you only wrote a short program using Node around the same time as you wrote Node.
There are a few other problems as well, which I'll call out as I lay out a possible implementation of BinaryTree.h (I've written this in C++11, which is now widely available; I've avoided some improvements that could be made using C++14):
#pragma once
#include <cassert>
#include <functional>
#include <iostream>
Quick note -- include the C++ headers, not the C-ish headers like iostream.h — they're ancient.
#include <memory>
#include <utility>
namespace dimanist_binary_tree {
Normally I give the public API before private implementation details, but the Node class illustrates many of the points I want to make, so here it is.
namespace detail {
template <typename T,
typename Less = std::less<T>,
typename Eq = std::equal_to<T>>
Note: In C++14, these should be std::less<> and std::equal_to<>, which are more flexible than std::less<T> and std::equal_to<T>.
class Node : std::enabled_shared_from_this<Node> {
public:
using LessType = Less;
using EqType = Eq;
Node(T&& t) : data(std::move(t)) {}
// In-place construction of data
template <typename... Args>
Node(Args&&... args) : data(std::forward<Args>(args)...) {}
// Inserts a new node into this tree with t as its data.
void insert(T&& t, Less less) {
return insert(std::make_shared<Node>(std::move(t)), less);
}
// Inserts node into this tree.
void insert(std::shared_ptr<Node> node, Less less);
A couple notes on insert:
- There's no need to pass the root node as its first argument; this is already the root node of a subtree. This is C++, not C!
- Passing raw pointers around makes it difficult to make sure you're neither leaking memory nor keeping references to memory that has already been freed. std::shared_ptr<T> makes our life easier in this instance.
// If t is present in this tree, one node containing it is removed.
// The return value contains the new root of this tree and a bool
// that is true if any node was removed.
std::pair<std::shared_ptr<Node>, bool> erase(const T& t, Less less, Eq eq);
// If t is present in this tree, all nodes containing it are removed.
// The return value contains the new root of this tree and an int
// giving the number of nodes removed.
std::pair<std::shared_ptr<Node>, int> erase_all(const T& t, Less less, Eq eq);
I know your current implementation prevents multiple copies of t from being
inserted (though only because I read carefully through the code!), but I think
for that to be a reasonable thing to do, you need to modify the API, which makes
it more complicated.
// Returns a node containing t, or nullptr if this tree does not contain t.
std::shared_ptr<const Node> find(const T& t, Less less, Eq eq) const;
std::shared_ptr<Node> find(const T& t, Less less, Eq eq);
I've provided two versions of this method in order to provide deep const semantics to the class. You're allowed to search for a value given a const Node&, but you can't use the returned value to modify the tree. I used find rather than search since that is the name the standard library uses for this functionality. Note also that I return the node rather than printing to std::cout; if the caller wants to print, they can do that themselves. This provides them also with the flexibility to do other things based on the return value.
// Returns the maximum node in this tree.
std::shared_ptr<const Node> max() const;
std::shared_ptr<Node> max();
// Returns the minimum node in this tree.
std::shared_ptr<const Node> min() const;
std::shared_ptr<Node> min();
std::ostream& print_tree(std::ostream& os, int level);
Note that I pass a std::ostream& so that the user can print to std::cout, std::cerr, a file stream, etc, instead of restricting the choice to std::cout.
private:
// Compute the new root assuming this node is being removed.
std::shared_ptr<Node> reroot();
std::shared_ptr<Node> left;
std::shared_ptr<Node> right;
T data;
};
} // namespace detail
// A binary tree
template <typename T,
typename Node = detail::Node<T>,
typename Less = typename Node::LessType,
typename Eq = typename Node::EqType>
class BinaryTree {
So the purpose of BinaryTree here is to prevent users having to pass Node pointers (or shared_ptrs) directly, checking for nullptr, etc. It makes this whole class easier to use.
public:
using Less = typename Node::LessType;
using Eq = typename Node::EqType;
BinaryTree(Less less = Less(), Eq eq = Eq()) : less(less), eq(eq) {}
bool empty() const { return !root; }
// Insert a new node with t as its data. This node will be inserted
// even if a node with t as its data is already in the tree.
void insert(T t) {
if (!root) {
root = std::make_shared<Node>(std::move(t));
} else {
root->insert(std::move(t), less);
}
}
// Insert a new node with a T constructed from args as its data.
template <typename... Args>
void insert(Args&&... args) {
auto new_node = std::make_shared<Node>(std::forward<Args>(args)...);
if (!root) {
root = std::move(new_node);
} else {
root->insert(std::move(new_node), less);
}
}
// If any node with t as its data is in this tree, removes one such node.
// Returns true if any node was removed.
bool erase(const T& t) {
if (!root) return false;
auto result = root->erase(t, less, eq);
root = std::move(result.first);
return result.second;
}
// Removes all nodes that have data equal to t. Returns the number of
// nodes removed.
int erase_all(const T& t) {
if (!root) return 0;
auto result = root->erase_all(t, less, eq);
root = std::move(result.first);
return result.second;
}
// Returns a subtree rooted by t, or nullptr if t is not in this tree.
BinaryTree<T, const Node, Less, Eq> find(const T& t) const {
if (!root) { return {less, eq}; }
return {root->find(t, less, eq), less, eq};
}
BinaryTree find(const T& t) {
if (!root) { return {less, eq}; }
return {root->find(t, less, eq), less, eq};
}
// Returns a subtree rooted at the maximum node in this tree.
BinaryTree<T, const Node, Less, Eq> max() const {
if (!root) { return {less, eq}; }
return {root->max(), less, eq};
}
BinaryTree max() {
if (!root) { return {less, eq}; }
return {root->max(), less, eq};
}
// Returns a subtree rooted at the minimum node in this tree.
BinaryTree<T, const Node, Less, Eq> min() const {
if (!root) { return {less, eq}; }
return {root->min(), less, eq};
}
BinaryTree min() {
if (!root) { return {less, eq}; }
return {root->min(), less, eq};
}
private:
BinaryTree(std::shared_ptr<Node> root, Less less, Eq eq)
: root(std::move(root)), less(less), eq(eq) {}
template <typename N>
friend std::ostream& operator<<(std::ostream&, const Tree<N>&);
std::shared_ptr<Node> root;
Less less;
Eq eq;
};
template <typename N>
std::ostream& operator<<(std::ostream& os, const Tree<N>& tree) {
if (tree.root) return tree.root->print_tree(os, 0);
return os;
}
Now for the implementations!
namespace detail {
template <typename T, typename Less, typename Eq>
void Node<T, Less, Eq>::insert(std::shared_ptr<Node> node, Less less) {
if (less(node->data, data)) {
if (left) {
left->insert(std::move(node), less);
} else {
left = std::move(node);
}
} else {
if (right) {
right->insert(std::move(node), less);
} else {
right = std::move(node);
}
}
}
template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>> Node<T, Less, Eq>::reroot() {
if (!left) {
return std::move(right);
} else if (!right) {
return std::move(left);
}
// The max in the left subtree has no right subtree; otherwise it
// wouldn't be the max!
auto left_max = left->max();
Two things here: I use max() instead of copy-pasting the logic from max(), and I add a quick explanation of why that works, since it's not totally obvious.
assert(!left_max->right);
left_max->right = std::move(right);
return std::move(left);
}
template <typename T, typename Less, typename Eq>
std::pair<std::shared_ptr<Node<T, Less, Eq>>, bool>
Node<T, Less, Eq>::erase(const T& t, Less less, Eq eq) {
if (eq(t, data)) {
return std::make_pair(reroot(), true);
} else if (less(t, data)) {
auto result = left->erase(t, less, eq);
left = std::move(result.first);
return std::make_pair(shared_from_this(), result.second);
} else {
auto result = right->erase(t, less, eq);
right = std::move(result.first);
return std::make_pair(shared_from_this(), result.second);
}
}
template <typename T, typename Less, typename Eq>
std::pair<std::shared_ptr<Node<T, Less, Eq>>, int>
Node<T, Less, Eq>::erase_all(const T& t, Less less, Eq eq) {
int num_removed = 0;
if (left && !less(data, t)) {
auto result = left->erase_all(t, less, eq);
left = std::move(result.first);
num_removed += result.second;
}
if (right && !less(t, data)) {
auto result = right->erase_all(t, less, eq);
right = std::move(result.first);
num_removed += result.second;
}
if (eq(t, data)) {
return std::make_pair(reroot(), num_removed + 1);
} else {
return std::make_pair(shared_from_this(), num_removed);
}
}
template <typename T, typename Less, typename Eq>
std::shared_ptr<const Node<T, Less, Eq>>
Node<T, Less, Eq>::find(const T& t, Less less, Eq eq) const {
if (eq(t, data)) return shared_from_this();
if (less(t, data)) {
return left ? left->find(t, less, eq) : nullptr;
} else {
return right ? right->find(t, less, eq) : nullptr;
}
}
template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>>
Node<T, Less, Eq>::find(const T& t, Less less, Eq eq) {
if (eq(t, data)) return shared_from_this();
if (less(t, data)) {
return left ? left->find(t, less, eq) : nullptr;
} else {
return right ? right->find(t, less, eq) : nullptr;
}
}
template <typename T, typename Less, typename Eq>
std::shared_ptr<const Node<T, Less, Eq>> Node<T, Less, Eq>::max() const {
auto p = shared_from_this();
while (p->right) p = p->right();
return p;
}
template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>> Node<T, Less, Eq>::max() {
auto p = shared_from_this();
while (p->right) p = p->right();
return p;
}
template <typename T, typename Less, typename Eq>
std::shared_ptr<const Node<T, Less, Eq>> Node<T, Less, Eq>::min() const {
auto p = shared_from_this();
while (p->left) p = p->left();
return p;
}
template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>> Node<T, Less, Eq>::min() {
auto p = shared_from_this();
while (p->left) p = p->left();
return p;
}
template <typename T, typename Less, typename Eq>
std::ostream& Node<T, Less, Eq>::print_tree(std::ostream& os, int level)
if (left) left->print_tree(os, level + 1);
for (int i = 0; i < level; ++i) os << " ";
if (right) right->print_tree(os, level + 1);
return os;
}
} // namespace detail
} // namespace dimanist_binary_tree
OK, this review has gotten pretty long, and we haven't gotten to ForMain.cpp; I'll let other reviewers address that.
