我正在尝试使用二叉树计算表达式。该树具有以下特征:
- 每个节点都有零个、一个或两个子节点。
- 只有包含运算符的节点可以有 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
,并且否则为假。
最佳答案
我认为我发现了两个问题。
(一)
假设您尝试进入图片右侧的树。您已经在顶部输入了 *
,在下方输入了 *
和 +
。您还输入了 7
和 121
。
现在您想输入 12
,这就是您的代码失败的地方。
根是一个运算符并且两个 child 都不为空,因此您进入“else”子句并将左 child 视为当前位置。但是这部分已经填满了!所以你将无法在那里插入任何东西。
但不确定这是唯一的错误,因为您应该会看到显示的错误消息。
(乙)
我认为,如果您从树的数字开始(而不是运算符),则在尝试插入叶子时会进入无限循环,并且看不到显示的消息(如果总是失败,则第一个)
关于c++ - 在表达式树中插入节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17215944/