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

Я думаю, стандартное двоичное дерево должно подойти... вот пример (двоичного ) узел дерева выражений:

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;

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

Я не думаю, что Node или Tree — это первые классы, которые нужно написать.

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

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

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

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

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

И дерево тоже:

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

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