c++ - 如何构建这个节点树？

Question

我正在用 C++ 编写一个程序，该程序使用遗传技术来优化表达式树。

我正在尝试编写一个类 Tree它有一个数据成员 Node root .节点构造函数生成随机节点树 + , - , * , /作为节点，整数作为叶子。

我已经研究了一段时间，但我还不清楚最佳结构。因为我需要访问树中的任何节点以便对树进行变异或杂交，所以我需要保留节点的字典。一个数组就可以了，但是 vector 似乎是推荐的容器。

vector<Node> dict;

所以 Tree 类将包含一个 vector 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; ，因为如果它进入 Tree 的定义，它不知道 Node，并且会报错。我一直没能找到 typedef 的地方

但我什至不确定 vector 是否是最好的容器。节点只需要按顺序索引。容器需要增长，因为可能有 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;

应该就是这样了......