MIPS中二叉树中的最长路径 [英] Longest path in binary tree in MIPS

问题描述

以这种方式给出二叉树：

Given binary tree in this way:

.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

树看起来像这样：
因此，最长的路径是经过igdbehj的7条槽。

The tree looks like this: So the longest path is 7 passing trough i-g-d-b-e-h-j.

所以我的问题是如何实现呢？
我需要在堆栈中使用多少空间？

So my question is how to implement this? How much space I need to use in the stack?

我需要使用0-4来表示左侧孩子的4-8值，并使用8- 12到正确的孩子？

I need to use 0-4 to the value 4-8 to the left child and 8-12 to the right child?

我的意思是我应该如何从根开始发展到下一个孩子？

I mean how do I progress to the next child from the root?

推荐答案

我如何移动此数据？

how do I move in this data?

给出一个指向 $ a0 中的节点的指针，左指针和右指针与节点的起点之间的偏移量为4个字节。 （节点结构的第一个成员似乎是一个整数，但您无需对其进行任何操作。）因此 lw $ t1，4（$ a0） 加载第二个struct成员（即 node-> left ）和 lw $ t2，8（$ a0） 加载 node->右。

Given a pointer to a node in $a0, the left and right pointers are at 4-byte offsets from the start of the node. (The first member of a node struct appears to be an integer, but you do'nt need to do anything with it.) So lw $t1, 4($a0) loads the 2nd struct member (i.e. node->left), and lw $t2, 8($a0) loads node->right.

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

beq $ t1，$ 0，left_was_zero

You can check for NULL, aka 0, by comparing against the zero-register, like this:
beq $t1, $0, left_was_zero

我认为您的搜索算法应进行树遍历，并且寻找具有最大树数的节点最大深度（左）+最大深度（右） 。正常的有序遍历将每个节点都考虑一次。

I think your search algorithm should do a tree traversal, and look for the node with the largest maxdepth(left) + maxdepth(right). A normal in-order traversal will consider every node once.

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

A recursive algorithm, is the obvious way, but you might want to keep some persistent state in registers, i.e. use them as global variables across the recursive calls. So you can keep lots of state "live" in registers instead of actually passing / returning it the way a naive C compiler would. I'm going to represent that using global register variables.

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 和返回地址是跟踪返回哪个块的便捷方法。

You could implement this with actual recursion; that may be easier than keeping track of whether you're in the left or right subtree of a node and using a stack data structure on the call-stack. jal / jr with a return address is a convenient way of keeping track of which block to return to.

无论如何，这应该可以直接转换为MIPS asm；它甚至可能使用全局寄存器变量进行编译（使用gcc），因为我认为我对 register ... asm（ $ t9）; https://gcc.gnu.org/onlinedocs/gcc/Global-Register-Variables。 html

Anyway, this should translate into MIPS asm pretty straightforwardly; it might even compile (with gcc) using global register variables since I think I used the right syntax for register ... asm("$t9"); https://gcc.gnu.org/onlinedocs/gcc/Global-Register-Variables.html

这篇关于MIPS中二叉树中的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！