0

我正在尝试使用二叉树评估表达式。树有以下特点：

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

像那些东西：
表达式树

这是我的树类：

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如果是+or则返回*，否则返回 false。

4

2 回答 2

1

可以解决该问题，为类添加跟踪每个节点的父节点的可能性。这里是新类：

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

        Node *leftChild, *rightChild;
        Node* parent; // +

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

与前一个的唯一区别是添加了另一个Node*数据成员。这将存储指向父节点的指针，从而可以向后遍历树。

该insert()功能还需要一些修改。这里是：

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

与之前版本的不同之处在于：在 main 中添加了一条语句else，如果所有叶节点都是数字（这意味着它们不能有子节点）[1]，则该语句会中断循环，并且替换（由 指定）前一个 else 有一个赋值，将光标向后移动到当前节点的父节点。ifwhile// +

此外，构造函数还Node()进行了修改：每次创建新节点时，都会将其与其父节点链接，并传递父节点的指针和第二个参数。

只是最后一件事。插入元素的顺序是自上而下的 left-right。例如，在问题中的第一棵树之后，必须按以下顺序插入元素：*, +, *, 7, 121, 12, +, 9, 3.


[1] Dr_Sam 建议。

于 2013-06-24T17:30:24.980 回答
1

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

（一个）

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

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

根是一个运算符，两个孩子都不为空，因此您进入“else”子句并将左孩子视为当前位置。但是这部分已经被填满了！因此，您将无法在其中插入任何内容。

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

(乙)

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

于 2013-06-20T14:33:49.117 回答