4
\$\begingroup\$

I am trying to implement a class for the Node of a Tree in C++ in order to represent an HTML structure. It is not complete by a shot, but i'd still like an opinion.

TreeNode.h :

#ifndef TreeNode_H
#define TreeNode_H

#include <string>
#include <vector>

class TreeNode
{
    private:
        std::string textContent;
        std::string tagName;

        TreeNode *parent;

        std::vector<TreeNode *> children;

        int countNodesRec(TreeNode *root, int& count);

    public:
        TreeNode();
        TreeNode(std::string iTextContent, std::string iTagName);

        void appendChild(TreeNode *child);
        void setParent(TreeNode *parent);

        void popBackChild();
        void removeChild(int pos);

        bool hasChildren();
        bool hasParent();

        TreeNode* getParent();
        TreeNode* getChild(int pos);

        int childrenNumber();
        int grandChildrenNum();

        std::string getTextContent();
        std::string getTagName();
};

#endif

TreeNode.cpp :

#include "TreeNode.h"
#include <string>
#include <vector>
#include <iostream>


TreeNode::TreeNode() {};

TreeNode::TreeNode(std::string iTextContent, std::string iTagName) :
    textContent(iTextContent),
    tagName(iTagName),
    parent(NULL)
{}

int TreeNode::countNodesRec(TreeNode *root, int& count)
{   
    TreeNode *parent = root;
    TreeNode *child = NULL;

    for(int it = 0; it < parent->childrenNumber(); it++)
    {   
        child = parent->getChild(it);
        count++;
        //std::cout<<child->getTextContent()<<" Number : "<<count<<std::endl;
        if(child->childrenNumber() > 0)
        {   
            countNodesRec(child, count);
        } 
    }

    return count;
}

void TreeNode::appendChild(TreeNode *child)
{       
    child->setParent(this);
    children.push_back(child);
}

void TreeNode::setParent(TreeNode *theParent)
{
    parent = theParent;
}

void TreeNode::popBackChild()
{
    children.pop_back();
}

void TreeNode::removeChild(int pos)
{   
    if(children.size() > 0) {
        children.erase(children.begin()+ pos);
    }
    else {
        children.pop_back();
    }
}

bool TreeNode::hasChildren()
{
    if(children.size() > 0)
        return true;
    else
        return false;
}

bool TreeNode::hasParent()
{
    if(parent != NULL)
        return true;
    else 
        return false;
}

TreeNode * TreeNode::getParent()
{
    return parent;
}

TreeNode* TreeNode::getChild(int pos)
{   
    if(children.size() < pos)
        return NULL;
    else
        return children[pos];
}

int TreeNode::childrenNumber()
{
    return children.size();
}

int TreeNode::grandChildrenNum()
{   
    int t = 0;

    if(children.size() < 1)
    {
        return 0;
    }

    countNodesRec(this, t);

    return t;
}

std::string TreeNode::getTextContent()
{
    return textContent;
}

std::string TreeNode::getTagName()
{
    return tagName;
}

Sample code :

#include <iostream>
#include <vector>
#include "TreeNode.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {

    TreeNode *itr = NULL;

    TreeNode *node = new TreeNode("k", "p");
    node->appendChild(new TreeNode("test1", "testag"));
    node->appendChild(new TreeNode("test2", "testag"));
    node->appendChild(new TreeNode("test3", "testag"));

    itr = node->getChild(0);

    itr->appendChild(new TreeNode("test1a", "testtag"));
    itr->appendChild(new TreeNode("test1b", "testtag"));
    itr->getChild(0)->appendChild(new TreeNode("test1aa", "testtag"));

    itr = node->getChild(1);
    itr->appendChild(new TreeNode("test2a", "testtag"));
    itr->appendChild(new TreeNode("test2b", "testtag"));

    itr->getChild(0)->appendChild(new TreeNode("test2aa", "testtag"));

    std::cout<<node->grandChildrenNum();

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Does this compile without Warnings and errors? \$\endgroup\$ – pacmaninbw Jul 20 '16 at 21:46
  • \$\begingroup\$ Yes it does on DevCpp and Windows 10 \$\endgroup\$ – Viktorija Spasenovska Jul 20 '16 at 21:50
  • 1
    \$\begingroup\$ I recommend adding -Wall -Wextra -pedantic to your compile flags in DevCpp to catch more warnings. \$\endgroup\$ – Emily L. Jul 21 '16 at 6:58
6
\$\begingroup\$

Some quick comments:

Const correctness

You really should make your code const correct.

For example at least these functions could be const declared:

    bool hasChildren();
    bool hasParent();

    TreeNode* getParent();
    TreeNode* getChild(int pos);

    int childrenNumber();
    int grandChildrenNum();

    std::string getTextContent();
    std::string getTagName();

Use references to avoid copies

This:

TreeNode(std::string iTextContent, std::string iTagName);

should be:

TreeNode(const std::string& iTextContent, const std::string& iTagName);

otherwise you are creating temporary copies of the strings when you pass them in.

These functions should return by const reference:

    std::string getTextContent();
    std::string getTagName();

Like so:

    const std::string& getTextContent() const;
    const std::string& getTagName() const;

Otherwise you will be creating unnecessary memory copies each time the function is called even if you just want to look at the value.

Memory leak galore?

Your API requires that you pass in raw pointers and store them in the node. There is no documentation of the ownership of the pointers. Who is responsible for freeing them? Right now all I see is a memory leak waiting to happen.

In your main code you allocate the nodes with new but C++ is NOT a garbage collected language. You will need to pair each new with a delete to free the memory otherwise you will run out of memory faster than you can say "Holy memory management batman!".

Now, this keeping track of new/delete gets error prone very quickly so since C++11 you are recommended to use smart pointers. A.k.a. std::unique_ptr and std::shared_ptr for just about everything. See also std::make_unique and std::make_shared. There are places where you could/should use pointers, but as I gather that you are new to C++ I will not go into those detail because you can get away with just using smart pointers everywhere for now.

Also you might be interested in reading up on Resource Acquisition Is Initialisation (RAII). We ❤❤❤ RAII in C++.

\$\endgroup\$
5
\$\begingroup\$

Some general points:

  • Explicit new should never be part of an interface. Use std::unique_ptr to represent a uniquely-owning pointer. In fact, your code leaks because you never delete anything that you allocate. unique_ptr would mean you don't have to remember to manually free, and should also help your code to be more exception-safe.

  • You're not using polymorphism, so you don't need (owning) pointers at all really. The parent field should still be a pointer, but the children can just be a std::vector<TreeNode>.

  • Your TreeNode doesn't have an explicit destructor. Classes should either have a public virtual destructor, a protected non-virtual destructor, or no destructor but the class should be marked final.

  • Pass anything bigger than a register by const reference instead of by value.

  • In terms of layout, it's nicer for the class-user to have the public items before the private ones.

This seems like code that has been quickly ported from Java rather than idiomatic C++.

\$\endgroup\$
  • \$\begingroup\$ Thank you! Yes i forgot to add a destructor and delete the pointer to the node(still not finished).And yeah I mostly do OOP in PHP and Java so it's kind of hard to shift to the cpp mindset(But I am really trying to learn). \$\endgroup\$ – Viktorija Spasenovska Jul 20 '16 at 22:08
3
\$\begingroup\$

You did well with the #ifndef #endif guard banding, and the indentation is nice.

Initialize Variables
The empty constructor is not initializing parent, my compiler gives me an error on this code.

TreeNode::TreeNode() {};

It should be

TreeNode::TreeNode():parent{nullptr} {};

Note: in C++11 initialization uses {} rather than ().

Comparison of Different Types
The reason for my comment above is that the following code compares an int to a size_t

TreeNode* TreeNode::getChild(int pos)
{   
    if(children.size() < pos)
        return NULL;
    else
        return children[pos];
}

The vector.size() function is of type size_t which in some implementations is unsigned int. The G++ compiler on CentOS 7 has a warning message for the comparison of children.size() and pos.

It would be better if pos was declared as type size_t. If pos isn't declared size_t than the code should contain a static_cast in the comparison.

Lack of Error Checking
In the above getChild() function above, there is not enough error checking. Since pos is an integer the error checking should include a check for the value of pos being less than zero. If pos is less than zero this code will throw a runtime exception.

Use the Functions
The code contains the function hasChildren()

bool TreeNode::hasChildren()
{
    if(children.size() > 0)
        return true;
    else
        return false;
}

This function should be called by the other functions that modify the children vector rather than repeating if (children.size() > 0). That way if you need to change the comparison you only need to change it in one place.

The function hasChildren() can be simplified to

bool TreeNode::hasChildren() const { return children() > 0; }

and you can put the entire function into the header file.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.