c++ - 在表达式树中插入节点

Question

我正在尝试使用二叉树计算表达式。该树具有以下特征:

• 每个节点都有零个、一个或两个子节点。
• 只有包含运算符的节点可以有 child 。
• 所有叶节点必须是数字。
• 为简单起见，唯一允许的运算符是 * 和 +

像那些:

这是我的树类:

class ExpressionTree {
    struct Node {
        std::string data;

        Node *leftChild, *rightChild;

        Node(std::string d): data(d), leftChild(NULL), rightChild(NULL) {}
    } *root;
    uint tsize;
public:
    ExpressionTree(): root(NULL), tsize(0) {}
    Node* treeRoot() { return root; }
    void insert(std::string s);
};

这是我的插入函数:

void insert(std::string s) {
    if (root == NULL) {
        root = new Node(s);
        ++tsize;
    } else {
        Node* current = root;
        while (true) {
            if (is_operator(current->data)) {
                if (current->leftChild == NULL) {
                    current->leftChild = new Node(s);
                    ++tsize;
                    return;
                } else if (current->rightChild == NULL) {
                    current->rightChild = new Node(s);
                    ++tsize;
                    return;
                } else {
                    if (is_operator(current->leftChild->data)) {
                        current = current->leftChild;
                        continue;
                    } else if (is_operator(current->rightChild->data)) {
                        current = current->rightChild;
                        continue;
                    } else {
                        std::cout << "Error: only nodes who hold operators"
                                  << " can have children." << std::endl;
                        return;
                    }
                }
            }
        }
    }
}

问题出在这个函数中。我从一个在二叉搜索树 中插入节点的函数开始编写它，但它不起作用。当我运行一个简单的 main(使用 insert()，一次添加第二棵树的节点)时，它崩溃了，没有返回任何错误，只有一个 Windows 7 对话框要求 检查在线解决方案。

我认为主要问题是它不检查树的所有元素，而只检查一个分支，因此它以非法方式附加新节点。不幸的是，我不知道如何解决这个问题。

我希望这个问题不要太具体。

注意:is_operator()接受一个字符串，如果是+或*则返回true，并且否则为假。

Answer 1

我认为我发现了两个问题。

(一)

假设您尝试进入图片右侧的树。您已经在顶部输入了 *，在下方输入了 * 和 +。您还输入了 7 和 121。

现在您想输入 12，这就是您的代码失败的地方。

根是一个运算符并且两个 child 都不为空，因此您进入“else”子句并将左 child 视为当前位置。但是这部分已经填满了!所以你将无法在那里插入任何东西。

但不确定这是唯一的错误，因为您应该会看到显示的错误消息。

(乙)

我认为，如果您从树的数字开始(而不是运算符)，则在尝试插入叶子时会进入无限循环，并且看不到显示的消息(如果总是失败，则第一个)