MIPS中二叉树的最长路径

Question

以这种方式给出二叉树：

.data
tree: .word a
a: .word 5, b, c
b: .word 2, d, e 
c: .word 1, 0, 0
d: .word 5, f, g
e: .word 9, 0, h
f: .word 0, 0, 0
g: .word 6, i, 0
h: .word 55, 0, j
i: .word 4, 0, 0
j: .word 8, 0, 0

这棵树是这样的：

因此，最长的路径是7通过槽.

那么我的问题是如何实现这一点呢？我需要在堆栈中占用多少空间？

我需要用0-4来表示左边的4-8值，8-12的值是右边的吗？

我的意思是，我如何从根源上发展到下一个孩子？

Answer 1

如何在这些数据中移动？

给定指向$a0中某个节点的指针，从节点开始时左右指针位于4字节偏移处。(节点结构的第一个成员似乎是一个整数，但您不需要对它做任何事情。)因此，lw $t1, 4($a0)加载第二个结构成员(即node->left)，lw $t2, 8($a0)加载node->right。

您可以通过与零寄存器进行比较来检查NULL，即0，如下所示：

beq $t1, $0, left_was_zero

我认为您的搜索算法应该执行一次树遍历，而maxdepth(left) + maxdepth(right).查找具有最大的节点。一个正常的有序遍历将考虑每个节点一次.

递归算法是显而易见的方法，但您可能希望在寄存器中保留一些持久状态，即在递归调用中使用它们作为全局变量。因此，您可以将许多状态“活动”保存在寄存器中，而不是像简单的C编译器那样实际传递/返回它。我要用全局寄存器变量来表示。

register unsigned longest_len asm("$t8") = 0;
register node* longest_root asm("$t9") = NULL;

// private helper function
// returns max depth, updates global registers along the way
static unsigned traverse(node *root) {
    unsigned left_depth=0, right_depth=0;
    if (root->left)
       left_depth = traverse(root->left);
    if (root->right)
       right_depth = traverse(root->right);

    unsigned sum = left_depth + right_depth;
    if (sum >= longest_len) {
        // update global registers
        longest_len = path + 1;  // path includes *this* node
        longest_root = root;
    }

    // you can probably save an instruction somewhere by optimizing the +1 stuff between the retval and the longest_len check
    int retval = left_depth + 1;   // $v0
    if (left_depth < right_depth)
        retval = right_depth + 1;   // +1 to include this node

    return retval;
}

node *find_longest_path(node *tree) {
    longest_len = 0;
    // longest_root = NULL;  // will always be overwritten
    traverse(tree);
    return longest_root;
}

您可以使用实际的递归来实现这一点；这可能比跟踪节点的左或右子树和在调用堆栈上使用堆栈数据结构更容易。具有返回地址的jal / jr是跟踪要返回的块的一种方便的方式。

无论如何，这应该非常直接地转换为MIPS asm；它甚至可能(与gcc一起)使用全局寄存器变量进行编译，因为我认为我对register ... asm("$t9"); https://gcc.gnu.org/onlinedocs/gcc/Global-Register-Variables.html使用了正确的语法。