Я реализовал древовидную структуру на C++, обращаясь к чужим кодам. Код ниже, который я сделал, наверняка был скомпилирован и, похоже, хорошо работает. Но подозреваю, что есть способы получше. Например, безопасен ли этот код в точке утечки памяти? Есть ли способ более простой и более эффективный в вычислительном отношении?
В частности, я сомневаюсь в необходимости «std :: list lst_nodes». Функция expand_node в классе Tree присоединяет новый узел к родительскому узлу, значение которого наиболее близко к значению нового узла. Этот процесс требует итерации по всем существующим узлам для доступа к их значениям. Для этой итерации я определил переменную-член с именем "std :: list lst_nodes" в классе Tree. И я подозреваю, что существует отличный способ сделать то же самое без определения lst_nodes.
#include<random>
#include<iostream>
#include<list>
using namespace std;
class Node{
public:/*functions*/
Node(const double& val_, Node* parent_=nullptr)
:val(val_), parent(parent_)
{
if (parent){
parent->children.push_back(this);
}
}
public:/*variables*/
Node* parent;
std::list<Node*> children;
double val;
};
class Tree{
public:/*function*/
Tree(double x_init);
void extend_node();
public:/*variables*/
list<Node*> lst_nodes;
double x_init;
};
Tree::Tree(double x_init_)
:x_init(x_init_)
{
Node* n=new Node(x_init);
lst_nodes.push_back(n);
}
void Tree::extend_node(){
double val_new = rand();
auto it=lst_nodes.begin();
double minval = abs((**it).val-val_new);
Node* node_parent;
for(;it!=lst_nodes.end(); it++){
if (minval>abs((**it).val-val_new)){
minval = abs((**it).val-val_new);
node_parent = *it;
}
}
Node* n_new = new Node(val_new, node_parent);
node_parent->children.push_back(n_new);
lst_nodes.push_back(n_new);
}
int main(){
Tree t(0);
for(int i=0; i<100; i++){
t.extend_node();
}
}
Большое спасибо.
@Richard: ваша ссылка отображается не так, как вы планировали, потому что вы пропустили "https: //"
delete не обращается ни разу, поэтому код полон утечек памяти.
@Beta исправлено спасибо
Вы правы, lst_nodes там быть не должно. Вы создаете и список узлов, и дерево. Вместо этого сделайте его деревом поиска, чтобы вы могли таким образом находить узлы.





В современном C++ вы можете использовать unique_pointer<T> вместо необработанных указателей T*, когда объект, на который указывает указатель, принадлежит объекту, имеющему указатель. Таким образом, вам не нужно явно указывать объект delete, это будет сделано в деструкторе unique_ptr.
В дереве (то есть связном графе без циклов) право собственности четко определено: каждый узел владеет своими дочерними элементами, поэтому вы можете использовать list<unique_ptr<Node>> для Node::children.
Вы также можете размещать сообщения на Обмен стеком для проверки кода