在表达式树中插入节点 [英] Insert nodes in expression trees
问题描述
我正在尝试使用二叉树评估表达式.该树具有以下特征:
I'm trying to evaluate an expression using a binary tree. The tree has this characteristics:
- 每个节点有零个，一个或两个孩子.
- 只有个包含运算符的节点可以有子级.
- 所有叶子节点必须为数字.
- 为简单起见，允许的唯一运算符是
*和+
- Each node has zero, one or two children.
- Only nodes containing operators can have children.
- All leaf nodes must be numbers.
- For the sake of simplicity, the only operators allowed are
*and+
类似的东西:
Something like those ones:
这是我的树类:
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;
}
}
}
}
}
}
问题出在此功能中.我从一个函数开始编写它，即在 Binary Search树中插入节点，但是它不起作用.当我运行一个简单的主程序(使用 insert()一次添加第二棵树的节点)时，它崩溃了，没有返回任何错误，只有要求输入的Windows 7对话框检查在线解决方案.
The problem is in this function. I wrote it starting from a function to insert nodes in a Binary Search tree, but it doesn't work. When I run a simple main (that, using insert(), adds the nodes of the second tree one at time) it crashes without returning any error, only a windows 7 dialog who asks to check for an online solution.
我认为主要的问题是它不检查树的所有元素，而仅检查分支，因此，它以非法方式附加新节点.不幸的是，我不知道如何解决这个问题.
I think that the main problem is that it does not inspect all the elements of a tree, but only a branch, and for this reason it appends new nodes in an illegal way. Unfortunately, I can't figure out how to solve this.
我希望这个问题不太具体.
I hope that this question is not too much specific.
注意: is_operator()接受一个字符串，如果是 + 或 * ，则返回 true ，并且否则为假.
Note: is_operator() takes a string, and return true if it's + or *, and false otherwise.
推荐答案
可以解决该问题，在类中添加跟踪每个节点的 parent 节点的可能性.这是新班级:
The problem can be solved adding to the class the possibility to keep trace of the parent node for each node. Here the new class:
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 * 数据成员.这将存储指向父节点的指针，从而使向后遍历树的可能性成为可能.
The only difference from the previous one, is the addition of another Node* data member. This will store the pointer to the parent node, giving in this way the possibility to traverse the tree backward.
insert()函数也需要进行一些修改.在这里:
Also the insert() function needs some modifications. Here it is:
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;
}
}
}
}
与先前版本的区别在于:在 while 内的主 if 中添加了 else 语句，这打破了循环所有叶节点都是数字(这意味着它们不能有子代)的情况 [1] 并用赋值替换先前的else(由//+ 指定)多数民众赞成轻触光标贝克到当前节点的父节点.
The differences with the previous version are: the addition of an else statement in the main if inside the while that breaks the loop in case that all leaf nodes are numbers (that means they cannot have children)[1] and the substitution (as specified by // +) of the previous else with an assignment thats teps the cursor beckward to the parent node of the current one.
此外，构造函数 Node()也会进行修改:每次创建新节点时，它都会与它的父节点链接，并传递父节点的指针和第二个参数.
Moreover, also the constructor Node() go through a modification: each time that a new node is created, it is linked with its parent passing the parent's pointer ad second argument.
最后一件事.插入元素的顺序为自上而下，从左至右.例如，在问题的第一棵树之后，必须按以下顺序插入元素: *，+，*，7、121、12，+，9、3 .
Dr_Sam建议的 [1] .
Just a last thing. The order to insert elements is top-down left-right. For example, following the first tree in the question, the elements must be inserted in this order: *, +, *, 7, 121, 12, +, 9, 3.
[1] suggested by Dr_Sam.
这篇关于在表达式树中插入节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
