Чтобы ответить на ваш первый вопрос: не используйте оператор [] , потому что он вставляет созданный по умолчанию элемент, если он не существует на карте. Вместо этого вы можете использовать в .
Тогда о вашей архитектуре: она выглядит не очень хорошо, потому что, имея ребенка, не очевидно, как получить родителя, иметь родителя, это не так. Очевидно, как получить его, ваш ключ std::map должен быть уникальным, и вы также используете его как значение для вашего Elements. Я предлагаю применить по крайней мере следующее:
class Element
{
public:
Element() = delete;
explicit Element(int value, Element* parent = nullptr):
value_(value), parent_(parent), left_child_(nullptr), right_child_(nullptr) {}
int getValue() const { return value_; }
Element* getParent() { return parent_; }
Element* getLeftChild() { return left_child_.get(); }
Element* getRightChild() { return right_child_.get(); }
Element* insertLeftChild(int value)
{
if (left_child_)
{
std::cout << "already exists" << std::endl;
return left_child_.get(); // already exists
}
std::cout << "new left elem: " << value << std::endl;
left_child_ = std::make_unique<Element>(value, this);
return left_child_.get();
}
bool isRoot() { return parent_ == nullptr; }
private:
int value_;
Element* parent_;
std::unique_ptr<Element> left_child_;
std::unique_ptr<Element> right_child_;
};
int main()
{
auto root = std::make_shared<Element>(1);
Element* last_child = root->insertLeftChild(2)->insertLeftChild(3)->insertLeftChild(4);
std::cout << last_child->getValue() << std::endl;
std::cout << last_child->getParent()->getValue() << std::endl;
std::cout << last_child->getParent()->getParent()->getValue() << std::endl;
std::cout << last_child->getParent()->getParent()->getParent()->getValue() << std::endl;
std::cout << last_child->getParent()->getParent()->getParent()->isRoot() << std::endl;
return 0;
}
Теперь у вас есть доступ к родителям и дочерним элементам из каждого элемента, и вы можете начать строить свое дерево. Затем возникают дополнительные проблемы, такие как Element оператор сравнения (при необходимости), только 2 дочерних элемента на узел или, возможно, больше, аннулирование указателей при каждой модификации дерева и т. Д. c. Это большой топи c в целом.
======= РЕДАКТИРОВАТЬ =========
Чтобы ответить на озабоченность ОП по поводу нескольких детей и приведите пример удаления узла с сохранением листьев (потомков):
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_;
};
int main()
{
auto root = std::make_shared<Element>(1);
Element* last_child = root->insertChild(2)->insertChild(3)->insertChild(4);
last_child->getParent()->insertChild(5);
std::cout << "numChildren: " << last_child->getParent()->numChildren() << std::endl;
last_child->getParent()->moveChildren2Parent();
std::cout << "numChildren: " << last_child->getParent()->numChildren() << std::endl;
last_child->getParent()->removeChild(0); // element with value 3 removed, it's children already transferred
std::cout << last_child->getValue() << std::endl;
std::cout << last_child->getParent()->getValue() << std::endl;
std::cout << last_child->getParent()->getParent()->getValue() << std::endl;
std::cout << last_child->getParent()->getParent()->isRoot() << std::endl;
return 0;
}
Это лишь одна из многих возможностей, выбор конкретной реализации всегда зависит от системных требований.