C++ tree base node

I've been programming in C++ again (after switching to web languages) for about 2 weeks now. I wrote this simple Node class from which all other objects within the Tree will be derived from. Any critique is very welcome here, however please use clear explanations, don't just point out flaws.

```
#include
#include

using namespace std;

// DEFINITION

class Node
{
public:

Node(string name_);
virtual ~Node() = 0;

string GetName() const;

void SetParent(Node * parent);
Node * GetParent() const;

Node AddChild(Node child);
vector FindChildren(string name) const;
Node * FindFirstChild(string name) const;
Node * FindLastChild(string name) const;
Node * FindNthChild(int nth, string name) const;
vector ChildrenNames() const;

int Depth() const;
bool IsLeaf() const;
bool IsRoot() const;

protected:

string name;

Node * parent;
vector children;

private:
};

// IMPLEMENTATION

Node::Node(string name_)
{
name = name_;
parent = NULL;
}

Node::~Node()
{
for(vector::iterator it = children.begin(); it SetParent(this);
children.push_back(child);

return child;
}

vector Node::FindChildren(string name) const
{
vector children;
for(vector::const_iterator it = children.begin(); it name) == 0)
children.push_back(*it);

}
return children;
}

Node * Node::FindFirstChild(string name) const
{
for(vector::const_iterator it = children.begin(); it name) == 0)
return (*it);

}
return NULL;
}

Node * Node::FindNthChild(int nth, string name) const
{
int n = 0;
for(vector::const_iterator it = children.begin(); it name) == 0)
{
if (++n == nth)
return (*it);
}

}
return NULL;
}

vector Node::ChildrenNames() const
{
vector names;
for(vector::const_iterator it = children.begin(); it name);
}
return names;
}

int Node::Depth() const
{
int d;
Node * ancestor =

OK. I complain about this every time. Please don't do this.

using namespace std;

It may be in every C++ book but in real programs (more than 100) lines it causes more problems than it is worth. You can easily get tangled up in all sorts of problems with name look-up. The whole point of std being so short (not standard) is so that it is simple to prefix items in the standard library easily. You can also selectively use using to bring specific objects into the current namespace.

using std::cout; // now you can use cout
                 // But try and scope it as much as possible
                 // preventing pollution is a good thing.

But personally I have got used to typing std:: in-front of everything.

When returning objects

string GetName() const;

prefer to return by reference. If you want to keep the object immutable return by const reference. Depending on usage it may be worth having two version a const and a non const version.

string&       GetName();
    string const& GetName() const;

Why do you need a SetParent()?

void SetParent(Node * parent);

This seems like you are exposing the implementation via the interface. This is binding your interface and tightly binding your implementation to this interface. I would remove this method. Remember that Node is a friend of itself so methods in Node can access and manipulate other objects of type Node (you trust yourself don't you).

There is absoilutely no reason to expose this.

Node * GetParent() const;

You pass pointers around too much.

Node * AddChild(Node * child);

OK. In a tree the ownership may seem obvious. But I would prefer to ownership explicitly defined by the code (this will prevent mistakes later). Thus you need to use smart pointers so that you explicitly define how ownership of pointers as they are passed around.

// No need to return anything.
    // Explicitly pass ownership of the pointer.
    void AddChild(std::auto_ptr child);

These are OK returning pointers. As here you are saying that there may be no result and you need to validate any result (checking for NULL) before it can be used. But you can pass string by const reference.

vector FindChildren(string name) const;
    Node * FindFirstChild(string name) const;
    Node * FindLastChild(string name) const;
    Node * FindNthChild(int nth, string name) const;
    vector ChildrenNames() const;

OK. Parent can be a pointer (as it potentially may be NULL).

Node * parent;

Children on the other hand are owned.

• One choice is a vector of smart pointers.

-
An alternative is boost::ptr_vector.

vector children;

Normally I would go with boost::ptr_vector (as it exposes its members as object references rather than pointers) but in this particular case I would go with a vector of smart pointers (because I want to manage the pointers in this case).

No need to test for NULL before deleting
if (*it)
{
delete * it;
}
Just use::
delete (*it);

No point in calling clear. The destructor is about to destroy this object any way. By putting this here you are making the mainter think that there is something none obvious going on here.

children.clear();

//  Just delete this function it is not required.
//  See below on how to replace it. 
/* void Node::SetParent(Node * parent_) 
{
    parent = parent_;
}*/

// No need for this. It is exposing internals without needing too.
/*Node * Node::GetParent() const
{
    return parent;
}*/

// Replace call to set parent
void Node::AddChild(std::auto_ptr child)
{
    // Check if the child is valid
    if (child.get() == NULL)
    {    return;
    }

    // child->SetParent(this);
    // Check that the child is not already in a tree.
    if (child->parent != NULL)
    {    throw std::runtime_error("Something bad happened this node is already in a tree");
    }

    // Add it to the tree.
    child->parent = this;
    children.push_back(child);

    // No need to return this
    // You have to think why does this return the child
    // I see no reason for this.
    // return child;
}

So you only check this node and its children!!!!!

If so this function seems to be named incorrectly. Searching a tree is normally recursive. The function should check the current node then RECUSIVELY check each child.

vector Node::FindChildren(string name) const

Iterators are not compared with < you need to test against !=. While we are here prefer to use prefix ++ (here it does not make much difference but in other places it can so it is a nice habbit to get into (especially with iterators)).

for(vector::const_iterator it = children.begin(); it < children.end(); it++)

Is there a particular reason you use compare() rather than the more natural ==?

if (name.compare((*it)->name) == 0)

Try this:

```
std::vector Node::FindChildren(std::string const& name) const
{

StackExchange Code Review Q#11841, answer score: 12