c++ - C++ 中一般树实现的问题

Question

我必须为我的一个类(class)实现一棵 C++ 通用树，但我遇到了一个我不明白的问题。

我有两个类(class)，EmployeeNode和EmpoyeeTree 。 EmployeeNode包含工作所需的数据元素:字符串 name ，一个EmployeeNode parent 和 List<EmployeeNode> child 是我之前实现的一个链表，据说可以与任何模板对象一起使用。

这是我目前的代码:

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);
}

现在，我只是尝试一些基本命令来测试我的工作。我首先创建根EmployeeNode与 hireEmployee(EmployeeNode *newEmployee) ，然后我尝试使用 hireEmployee(EmployeeNode *boss, std::string newEmployee) 添加一个子项。 ，但我收到一条错误消息，告诉我尝试将 child 添加到不存在的 child 列表中。我检查了，但我不明白我的错误在哪里或是什么。

用断点调试的时候，发现每次创建的时候都会出现List<EmployeeNode>后自动销毁。 我想我玩了太多指针而没有完全理解它们，但现在我坚持了这一点。

Answer 1

EmployeeNode中存在一些结构性问题.

1. List<EmployeeNode> *child;不应该是List<EmployeeNode *> child;也就是代表每 EmployeeNode有一个名为 child 的成员(member)记住指向其子项的指针列表？
2. 在构造函数中

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

child将首先由 employeeChildren 初始化在参数中，然后 employeeChildren将被设置为新列表并且对 child 没有影响 另外，为什么构造函数需要导入别人的 child ？

---

为了完整起见，我还提供了我的实现供您引用。 如果我使用了您尚未学到的任何内容，请不要感到不知所措。

#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();
}