Как структурировать это дерево узлов?

Question

Я пишу программу на C++, которая использует генетические методы для оптимизации дерева выражений.

Я пытаюсь написать класс Tree, который имеет в качестве элемента данных Node root. Конструктор узла генерирует случайное дерево узлов с +, -, *, / как узлы и целые числа в виде листьев.

Я работаю над этим некоторое время, и я пока не понял, какая структура лучше. Поскольку мне нужно получить доступ к любому узлу в дереве, чтобы мутировать или скрещивать дерево, мне нужно сохранить dicionary узлов. Массив будет делать, но кажется, что вектор является рекомендуемым контейнером.

vector<Node> dict; 

Так класс Дерево будет содержать вектор dict со всеми узлами дерева (или указателей на тот же), корневой узел дерева, а также переменную для фитнес-мера для дерева.

class Tree 
    { 
    public: 
     typedef vector<Node>dict; 
     dict v; 
     Node *root; 
     float fitness; 

     Tree(void); 
     ~Tree(); 
    }; 

class Node 
    { 
    public: 
     char *cargo; 
     Node *parent; 
     Node *left; 
     Node *right; 
     bool entry; 
     dict v; 
     Node(bool entry, int a_depth, dict v, Node *pparent = 0); 
       }; 

Tree::Tree() 
    { 
    Node root(true, tree_depth, v); 
    }; 

Там, кажется, нет хорошего места, чтобы положить typedef vector<Node>dict;, потому что, если он идет в определении дерева, он не знает о Node, и выдаст ошибку, говоря так. Я не смог найти место до typedef.

Но я даже не уверен, является ли вектор лучшим контейнером. Узлы просто нужно индексировать последовательно. Контейнер должен расти, поскольку может быть от 200 до 500 узлов.

Answer 1

Я думаю, что стандартное двоичное дерево должно ...здесь является example of a (binary) expression tree node:

const int NUMBER = 0, // Values representing two kinds of nodes. 
      OPERATOR = 1; 

struct ExpNode { // A node in an expression tree. 

    int kind;  // Which type of node is this? 
        // (Value is NUMBER or OPERATOR.) 
    double number; // The value in a node of type NUMBER. 
    char op;   // The operator in a node of type OPERATOR. 
    ExpNode *left; // Pointers to subtrees, 
    ExpNode *right; //  in a node of type OPERATOR. 

    ExpNode(double val) { 
      // Constructor for making a node of type NUMBER. 
     kind = NUMBER; 
     number = val; 
    } 

    ExpNode(char op, ExpNode *left, ExpNode *right) { 
      // Constructor for making a node of type OPERATOR. 
     kind = OPERATOR; 
     this->op = op; 
     this->left = left; 
     this->right = right; 
    } 

}; // end ExpNode 

Так что, когда вы делаете кроссовер или мутации, и вы хотите, чтобы выбрать случайный узел, просто сделайте следующее:

1. Подсчитать количество узлов в дереве (нужно только сделать это в конструкторе).
2. Выберите случайный индекс от 0 до размера дерева.
3. Посетите каждый узел и вычтите 1 из случайного индекса, пока не достигнете нуля.
4. Возвращает узел, когда индекс 0.

В этом случае вам не нужно ничего знать о родителю узла. Так спаривание/мутация должна выглядеть следующим образом:

select nodeX 
select nodeY 
    if(Rand(0,1) == 1) 
     nodeY->left = nodeX; 
    else 
     nodeY->right = nodeX; 

И это должно быть это ...

Answer 2

Вы можете реализовать список по узлам. Затем каждый узел будет иметь два дополнительных указателей внутри:

class Node{ 
... 
Node* sequentialPrevious; 
Node* sequentialNext; 
... 
} 

И так будет дерево:

class Tree{ 
... 
Node* sequentialFirst; 
Node* sequentialLast; 
... 
} 

Чем вы будете Albe двигаться двунаправленным над узлами только прыгнув в sequentialFirst или sequentialLast, а затем итеративно до sequentialNext или sequentialPrevious. Конечно, конструктор и деструктор Node должны быть правильно реализованы, чтобы обновлять эти указатели.

Answer 3

Я не думаю, что Node или Tree - первые классы для написания.

Я бы начал с Expression. В вашем случае вам нужно как минимум BinaryExpression, а также выражение без подносов (константы или переменные). Каждое двоичное выражение должно содержать auto_ptr<Expression> lhs и auto_ptr<Expression> rhs.

Затем вы можете легко написать функцию для перечисления через элементы дерева выражений. Если производительность оказывается релевантной, вы можете кэшировать список выражений в дереве и аннулировать ее вручную при изменении выражения. Все более продвинутое, вероятно, будет более медленным и более подверженным ошибкам.

Я не понимаю, почему выражение должно знать, что это родительское выражение. Это только усложняет жизнь, когда вы начинаете редактировать выражения.