Problem with general tree implementation in C++

Question

I have to implement a general tree en C++ for one of my class, and I come across a problem I don't understand.

I have two classes, EmployeeNode and EmpoyeeTree. EmployeeNode contains the data elements needed for the work : a string name, an EmployeeNode parent and a List<EmployeeNode> children which is a linked list I implemented before, supposedly working with any template object.

Here is my code for the moment:

class EmployeeTree;

class EmployeeNode {
public:
    EmployeeNode(std::string name, EmployeeNode* parent, List<EmployeeNode>* child);
    ~EmployeeNode();
    
    void setChild(EmployeeNode newEmployee) {child->insert(newEmployee);}
    List<EmployeeNode>* getChild() {return(child);}
    bool hasChild() {return (child != 0);}
    
    std::string getName() {return name;}
    
private:
    std::string name;
    EmployeeNode *parent;
    List<EmployeeNode> *child;
};

EmployeeNode::EmployeeNode(std::string employeeName, EmployeeNode* employeeParent, List<EmployeeNode>* employeeChildren)
:name(employeeName), parent(employeeParent), child(employeeChildren)
{
    employeeChildren = new List<EmployeeNode>;
}

EmployeeNode::~EmployeeNode() {}

class EmployeeTree {
public:
    EmployeeTree();
    ~EmployeeTree();
    
    void hireEmployee(EmployeeNode *newEmployee);
    void hireEmployee(EmployeeNode* boss, std::string newEmployee);
    
    EmployeeNode find(std::string employee);
    
    void print(EmployeeTree Tree);
    
private:
    int level, age;
    EmployeeNode *root;
};

EmployeeTree::EmployeeTree()
:root(0)
{}

EmployeeTree::~EmployeeTree()
{}

void EmployeeTree::hireEmployee(EmployeeNode *newEmployee)
{
    root = newEmployee;
}

void EmployeeTree::hireEmployee(EmployeeNode* boss, std::string newEmployee)
{
    EmployeeNode* newChild;
    
    if (!boss->hasChild()){
        newChild = new EmployeeNode(newEmployee, boss, 0);
        boss->setChild(*newChild);
    }
    
    else {
        newChild = new EmployeeNode(newEmployee, boss, boss->getChild());
        boss->setChild(*newChild);
    }
}

EmployeeNode EmployeeTree::find(std::string employee) {
    if(root->getName() == employee)
        return *root;
    
    else if (root->getChild()) {
        
        List<EmployeeNode> *children = root->getChild();
        children->gotoBeginning();
        
        for(children->getCursor(); children->getCursor().getName() == employee ;children->gotoNext())
            *root = children->getCursor();
        
        return(*root);
        }
    else {std::cout << "Boss not found in employee tree." << std::endl;}
    
    return(*root);
}

For now, I'm just trying some basic commands to test my work. I first create the root EmployeeNode with hireEmployee(EmployeeNode *newEmployee), and then I try to add a child to that with hireEmployee(EmployeeNode *boss, std::string newEmployee), but I get an error telling me I try to add the child in a non-existing children list. I checked, but I don't understand where or what my error is.

When debugging with breakpoints, I found that every time it is created, the List<EmployeeNode> is automatically destructed after. I think I played too much with pointers without fully understanding them, but now I stuck with this.

boss->setChild(*newChild) probably does not do what you want it to do. — jxh
– jxh, Commented Jun 8, 2021 at 8:43
What is the intended purpose of employeeChildren = new List<EmployeeNode>;? At present it just overwrite the function argument, not a member variable, so the only meaninful thing it does is leak memory. — Korosia
– Korosia, Commented Jun 8, 2021 at 12:47

hare1039 · Accepted Answer · 2021-06-08 13:49:14Z

There are some structural problems in EmployeeNode.

List<EmployeeNode> *child; shouldn't it be List<EmployeeNode *> child; which is to represent that every EmployeeNode have a member called child to remember a list of pointer to its child?
In the constructor

:name(employeeName), parent(employeeParent), child(employeeChildren)
{
    employeeChildren = new List<EmployeeNode>;
}

child will be first initialized by employeeChildren in the argument, and then employeeChildren will be set to a new list and have no effect on child Also, why does the constructor need to import other people's child?

Just to be complete, I also provide my implementation for your reference. Don't be overwhelmed if I use anything you haven't learned yet.

#include <iostream>
#include <list>
#include <memory>

template<typename T>
using List = std::list<T>;
class EmployeeNode;
using EmployeeNodePtr = std::unique_ptr<EmployeeNode>;

class EmployeeNode
{
public:
    EmployeeNode(std::string name, EmployeeNode* parent): name{name}, parent{parent} {}
    void setChild(EmployeeNodePtr &child) { children.push_back(std::move(child)); }

    auto findChildByName(std::string queryname) -> EmployeeNode*
    {
        for (EmployeeNodePtr& child : children)
            if (child->name == queryname)
                return child.get();

        for (EmployeeNodePtr& child : children)
        {
            EmployeeNode* n = child->findChildByName(queryname);
            if (n != nullptr)
                return n;
        }

        return nullptr;
    }
    auto getName() -> std::string { return name; }
    void print()
    {
        std::cout << name << "\n";
        for (EmployeeNodePtr& child : children)
            child->print();
    }

private:
    std::string name;
    EmployeeNode *parent; // reference to parent, no ownership
    List<EmployeeNodePtr> children;
};

class EmployeeTree
{
public:
    void changeCEO(EmployeeNodePtr newCEO) { root.swap(newCEO); }
    void hireEmployee(EmployeeNode* boss, std::string newEmployee)
    {
        EmployeeNodePtr newChild = std::make_unique<EmployeeNode>(newEmployee, boss);
        boss->setChild(newChild);
    }

    auto find(std::string employee) -> EmployeeNode*
    {
        if (root->getName() == employee)
            return root.get();
        return root->findChildByName(employee);
    }

    void print() { root->print(); }
private:
    EmployeeNodePtr root;
};

int main()
{
    EmployeeNodePtr ceo = std::make_unique<EmployeeNode>("GreatCEO", nullptr);
    EmployeeTree company;
    company.changeCEO(std::move(ceo));

    EmployeeNode* boss = company.find("GreatCEO");
    company.hireEmployee(boss, "RightHand");
    company.hireEmployee(boss, "LeftHand");
    company.hireEmployee(boss, "RightFoot");
    company.hireEmployee(boss, "LeftFoot");

    EmployeeNode* hand = company.find("RightHand");
    company.hireEmployee(hand, "Finger1");

    EmployeeNode* feet = company.find("LeftFoot");
    company.hireEmployee(feet, "Toe");

    company.print();
}

Oh I see... Thanks for helping ! The List should be a List of pointers to employeeNode objects, and not a pointer to a linked list of employees. Also, the employeeChildren is overwritten when initialised so I'm going to fix that, but what do you mean about importing other's people children ? Thank you so much for your help, it means a lot !
I mean that in your original code EmployeeNode(std::string name, EmployeeNode* parent, List<EmployeeNode>* child);, I don't know the child argument is for. Does it means that "when construct a new EmployeeNode, the caller need to specify what children it have?".

Collectives™ on Stack Overflow

Problem with general tree implementation in C++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related