tree - 关于树和前缀(波兰语)表示法？

Question

我的 MIPS 汇编类(class)要求我将未知大小的表达式读入解析树。我从来不用处理树，所以这就是我存储值的方式:

假设用户输入了表达式 1 + 3 - 4(每个操作数只能是数字 1-9)

我最左边的子节点将是起点并包含 2 条数据

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

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

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

考虑到我是如何构建树的，中缀遍历没有问题。

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

当我在前缀中输出我们的表达式 (1 + 3 - 4) 时，它应该出现 - + 1 3 4 吗？我无法按照在线示例进行操作。

您还认为我的树构造正确吗？我的意思是，我无法从当前节点转到前一个节点，这意味着我总是必须从最左边的子节点开始遍历，尽管我的 TA 说这是要走的路，但本能地听起来并不正确。

感谢您的任何帮助。

Answer 1

您的解析树应如下所示:

        '-'         |     +---+---+     |       |    '+'     '4'     | +---+---+ |       |'1'     '3'

Each node has two pointers. One to its left child and one to its right child. There is no need for pointers to parent nodes, when using recursive traversal.

Here's some pseudocode:

Traversal for infix notation:

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 .

有时，用更高级的语言(无论你觉得什么都舒服)编写这些东西有助于理解问题，然后将这些代码“翻译”为汇编程序。我记得编程了 blocks world像这样在 MIPS 汇编器中进行仿真。