需要帮助生成C ++中深度有限的随机表达式树

Question

我发现了这个例子：Insert nodes in expression trees并做了一些小的修改：

class Node {
public:
    std::string data;
    Node* left, * right;
    Node* parent; // operator
    Node(std::string d, Node* p) : data(d), left(NULL), right(NULL), parent(p) {}
};
class ExpressionTree {
public:
    Node* root;
    int tsize;
    ExpressionTree() : root(NULL), tsize(0) {}
    void insert(string s);
    bool isOperator(string value);
};
bool ExpressionTree::isOperator(string value) {
    if (value == "+" || value == "-" ||
        value == "*" || value == "/" ||
        value == "==")
        return true;
    return false;
}
void ExpressionTree::insert(std::string s) {
    if (root == NULL) {
        root = new Node(s, NULL);
        ++tsize;
    }
    else {
        Node* current = root;
        while (true) {
            if (isOperator(current->data)) {
                if (current->left == NULL) {
                    current->left = new Node(s, current);
                    ++tsize;
                    return;
                }
                else if (current->right == NULL) {
                    current->right = new Node(s, current);
                    //++tsize;
                    return;
                }
                else {
                    if (isOperator(current->left->data)) {
                        current = current->left;
                        continue;
                    }
                    else if (isOperator(current->right->data)) {
                        current = current->right;
                        continue;
                    }
                    else {
                        if (current->parent) {
                            current = current->parent->right;
                            continue;
                        }
                        else {
                            //std::cout << "Error: only nodes who hold operators "
                            //  << "can have children." << std::endl;
                            return;
                        }
                    }
                }
            }
            else {
                //std::cout << "Error: only nodes who hold operators "
                //  << "can have children." << std::endl;
                return;
            }
        }
    }
}
void inorder(Node* node) {
    if (node) {
        if (node->left && node->parent)
            cout << "(";
        inorder(node->left);
        cout << node->data;
        inorder(node->right);
        if (node->right && node->parent)
            cout << ")";
    }
}

我需要根据输入向量创建深度有限的随机表达式树

int maxDepth = 2;
vector<string> operands = { "A", "B", "C" };
vector<string> operators = { "+", "*", "-" };

如果可以执行这样的事情，那就太好了：

ExpressionTree expression = generateRandomTree(operands, operators, maxDepth);

在这种情况下可能的有序解为A，B，C（树深度= 1）或A + B，A - A，C - A等，如果树深度> 1。

与上一个链接一样，要创建有效的表达式，必须遵循以下规则：

• 每个节点有零个，一个或两个孩子。
• 仅包含运算符的节点可以有子级。
• 所有叶节点必须是操作数。

[方法insert做得很好，但是我根本不知道如何基于此代码生成随机表达式树。。感谢您为解决此问题所提供的帮助。

Edit：大声想一下，我可能应该只用随机操作数或随机运算符（50-50％的机会）重复执行insert，直到所有叶节点都变成操作数或达到最大深度为止。另外，我只需要为maxDepth树级别强制使用随机操作数（如果达到）。尽管如此，实现仍然是我的问题。

Answer 1

仅推入树中的随机物品将不起作用。以2开头的幂maxDepth运算符很有可能，因此没有更多的操作数空间。

您想要做的是从一个节点开始，然后如果它在maxDepth处，请始终选择一个操作数，否则请随机选择一个运算符或操作数。如果您选择了一个运算符，则对左，右子级递归重复此操作。

如果树的深度必须精确为maxDepth，那么您将需要多修改一点此算法。