关于树和前缀（Polish）符号？
https://stackoverflow.com/questions/523957
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
需要我我的MIPS Assembly类在未知大小的成解析树的表达式来阅读。我从来没有对付树木，所以我这是怎么绕到存储值：
让我们说，用户输入的表达式1 + 3 - 4（每个操作数只能是数字1-9）
我的最左边的子节点是起点，并且包含2个数据
1. The operand
2. Pointer to the next node (operator)
这是我如何构建的树。直到没有更多的值留在要被读取我会从操作数操作者下一个操作数到下一个操作者指向。
我的下一个任务是递归遍历树和输出在中缀/前缀/后缀符号的值。
中缀遍历是没有问题的考虑我如何构造我的树。
我卡上的前缀。首先，我不完全了解它。
当我输出我们的表达式（1 + 3 - 4）中的前缀需要它出来 - + 1 3 4？我在下面的网上的例子的麻烦。
另外你觉得我的树是正确构造？我的意思是，我没有办法去前一个节点的，这意味着我总是不得不从本能地不健全的权利，即使我的TA说，这是要走的路。最左边的子节点开始遍历当前节点
感谢您的帮助。
解决方案
您解析树看起来应该是这样的：
'-'
|
+---+---+
| |
'+' '4'
|
+---+---+
| |
'1' '3'
每个节点具有两个指针。与其左边的孩子，一个在它的右边子。没有必要对指针父节点，使用递归遍历时。
下面是一些伪代码：
遍历的缀表示法：
void traverse(Node *node) {
if (node->leftChild != 0) {
traverse(node->leftChild);
}
print(node->value);
if (node->rightChild != 0) {
traverse(node->rightChild);
}
}
遍历的前缀符号：
void traverse(Node *node) {
print(node->value);
if (node->leftChild != 0) {
traverse(node->leftChild);
}
if (node->rightChild != 0) {
traverse(node->rightChild);
}
}
遍历的后缀符号：
void traverse(Node *node) {
if (node->leftChild != 0) {
traverse(node->leftChild);
}
if (node->rightChild != 0) {
traverse(node->rightChild);
}
print(node->value);
}
您会调用traverse方法与你的树的根节点。
您Node数据结构将需要三个成员：
struct Node {
char value;
Node *leftChild;
Node *rightChild;
}
的树的叶子将包含用于leftChild和rightChild空指针。
有时，它帮助写在高级语言这个东西（不管你觉得舒服），了解问题，然后“翻译”这个代码汇编。记得编程块世界在MIPS汇编仿真这样。
其他提示
在一般您应该建立一个树以这样的方式，所有的叶节点（那些没有孩子）是操作数，而内部节点（一切）是运营商。这应该是使运营商节点的孩子是它的操作数，或本身具有操作数的运营商。如果你能以这种方式构建一个树，形成了不同的符号（前缀，后缀，中缀）是相当简单 - 你只需按照序，后序和中序树遍历的，对于其中有著名的算法
据我所知，你不是构建一棵树，而一个链表，这是不会为你服务好。你有2个不同的实体 - 操作数和运算 - 你必须区别对待
。我同意SYKORA说什么。我想补充一点，你也可以在这种情况下使用堆栈。如果你的作业要求您专门使用一棵树，然后SYKORA的建议将是最好的。然而，堆栈可能更容易进行简单的表达式求值进行编程。
这是编译的一般问题，这是一个解决的问题的一个实例。如果你在编译技术做谷歌，你会发现各种涉及您的问题的信息。
您图书馆应有相应的副本的编译原理，技术和工具的阿霍，塞西和乌尔曼。如果没有它，要求其购买（这是在该领域的标准工作）。 它的第一部分应该帮助你。
