c++ - C++中的树类

Question

我想解决有关保存在树形结构中的数字的问题。


我想创建一个称为Tree的类，再创建一个称为Element的类(在这种情况下将是Integer，但可以是任何东西)，并使它成为基于C++标准的最合适的方法。应该可以将子级添加到树中的特定元素，并回溯每个元素的父级。

#include <iostream>
#include <vector>

class Element
{
public:
    Element() = delete;
    explicit Element(int value, Element* parent = nullptr):
            value_(value), parent_(parent), children_() {}
    int getValue() const { return value_; }
    Element* getParent() { return parent_; }
    // it will throw if idx out of bounds
    Element* getChild(size_t idx) { return children_.at(idx).get(); }


    size_t numChildren() const { return children_.size(); }
    Element* insertChild(int value)
    {
        std::cout << "new elem: " << value << std::endl;
        children_.emplace_back(std::make_unique<Element>(value, this));
        return children_.back().get();
    }
    bool moveChildren2Parent()
    {
        if (isRoot()) return false;
        for (auto& c : children_)
        {
            // children change parent
            c->parent_ = parent_;
            parent_->children_.emplace_back(std::move(c));
        }
        children_.clear();
        return true;
    }
    bool removeChild(size_t idx)
    {
        if (children_.size() <= idx) return false;
        children_.erase(children_.begin()+idx);
        return true;
    }
    bool isRoot() { return parent_ == nullptr; }

private:
    int value_;
    Element* parent_;
    std::vector<std::unique_ptr<Element> > children_;
};

void checkChilds(Element* element) {
    for (int i = 0; i < element->numChildren(); i++)
    {
        if (element->getChild(i)->numChildren() == 1)
        {
            element->getChild(i)->moveChildren2Parent();
            element->removeChild(i);
            i--;
        } else if (element->getChild(i)->numChildren() > 1)
        {
            checkChilds(element->getChild(i));
        }
    }
}

int main()
{
    auto root = std::make_shared<Element>(0);
    Element* _ = root->insertChild(1)->insertChild(3)->insertChild(5);
    Element* last_child = root->insertChild(2)->insertChild(4)->insertChild(7);
    last_child->getParent()->insertChild(6);

    for (int i=0;i<root->numChildren();i++)
    {
        if (root->getChild(i)->numChildren()==1)
        {
            root->getChild(i)->moveChildren2Parent();
            root->removeChild(i);
            i--;
        }
        else if (root->getChild(i)->numChildren()>1)
        {
            checkChilds(root->getChild(i));
        }
    }
    return 0;
}

我的目标是创建一棵树，然后如果每个元素只有一个 child ，则在保留叶子的同时删除该元素。
我的代码可以运行，但是我想知道一些改进，以便根据C++标准使其外观更好。

编辑

多亏了@pptaszni的回答，并将其适应于我手头的特定问题后，才得到了结果。我认为我的实现要遍历所有元素，以检查它们具有的子代数是否等于1，如果这样，则删除效果不好。您知道如何优化它(main和function checkChilds中的最后一个for循环)吗？

Answer 1

是否有任何特定原因需要元素和树两个不同的类？
我建议只使用一个类，该类具有一个将存储节点值的数据成员和两个指向两个不同子对象的指针。

以下是基于我从您的问题中了解的建议。

class Node
{
    int value;
    Node* left_child = nullptr; 
    Node* right_child = nullptr;
    //methods for modifying tree.
};