关于树和前缀（波兰）表示法？

Question

我的MIPS汇编课程要求我将一个大小未知的表达式读入解析树中。我从未接触过树，所以这是我存储值的方式：

假设用户输入了表达式1+3-4（每个运算数只能是数字1-9）

我的最左边的子节点将成为起始点并包含两个数据：

1. The operand
2. Pointer to the next node (operator)

这是我构建树的方法。我会从操作数指向运算符，再指向下一个操作数，再指向下一个运算符，直到没有更多值需要读取。

我的下一个任务是递归遍历树，并以中缀/前缀/后缀表示法输出值。

考虑到我如何构建树，中缀遍历不成问题。

我卡在了前缀上。首先，我并不完全理解它。

当我以前缀形式输出我们的表达式（1 + 3 - 4）时，它应该是 - + 1 3 4 吗？我很难跟随在线示例。

你认为我的树构建得正确吗？我的意思是，我无法从当前节点返回到上一个节点，这意味着我始终必须从最左边的子节点开始遍历，即使我的TA说那是正确的方法，但本能上感觉不对。

谢谢您的帮助。

- vpotok

Answer 1

您的解析树应该类似于这样：

        '-'
         |
     +---+---+
     |       |
    '+'     '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 汇编语言编程模拟块世界的情景。

- gclj5

Answer 2

一般来说，你应该构建一棵树，使得所有叶节点（没有子节点的节点）都是操作数，而内部节点（其他所有节点）都是运算符。这样做是为了让运算符节点的子节点成为它的操作数或者自身是具有操作数的运算符。如果你能以这种方式构建一棵树，那么形成各种表示法（前缀、后缀、中缀）就非常简单——只需要按照树的前序、后序和中序遍历进行即可，对于这些遍历方式，已经有着众所周知的算法。

据我所知，你并没有构建一棵树，而是一个链接列表，这样做不会给你带来好处。你有两个不同的实体——操作数和运算符——你必须对它们进行不同的处理。

- sykora

---

这正是我即将要给出的答案。谢谢，sykora！ - Niyaz

Answer 3

我同意sykora的观点。我想补充一下，在这种情况下，您也可以使用一个栈。如果您的任务要求您特定地使用树，则sykora的建议最好。然而，对于简单表达式计算，使用堆栈可能更容易编程。

- batbrat

Answer 4

这是编译的一般问题实例，是一个已经解决的问题。如果你在谷歌上搜索编译技术，你会发现各种与你问题相关的信息。

你的图书馆应该有阿霍（Aho）、塞斯（Sethi）和乌尔曼（Ullman）的《编译器：原理、技术和工具》（Compilers: Principles, Techniques, and Tools）的副本。如果没有，可以请求购买（它是该领域的标准作品）。它的第一部分应该对你有所帮助。

第三版链接

- Paul Nathan