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

Question

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

我有两个 class，EmployeeNode 和 EmpoyeeTree。 EmployeeNode 包含工作所需的数据元素：一个字符串 name、一个 EmployeeNode parent 和一个链接的 List<EmployeeNode> children我之前实现的列表，据说可以使用任何模板 object.

这是我目前的代码：

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

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

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

Answer 1

EmployeeNode 中存在一些结构问题。

List<EmployeeNode> *child; 不应该是 List<EmployeeNode *> child; 表示每个 EmployeeNode 都有一个叫 child 的成员来记住指向其子项的指针列表吗？
在构造函数中

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

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

Problem with general tree implementation in C++

c++

tree

member-function-pointers

data-structures