Самый длинный путь в двоичном дереве в MIPS - PullRequest
Новая
       23

Самый длинный путь в двоичном дереве в MIPS

0 голосов
/ 13 мая 2018

Дано бинарное дерево таким образом: 

.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

Дерево выглядит так: How the tree looks like Таким образом, самый длинный путь - 7 проходов через i-g-d-b-e-h-j.

Итак, мой вопрос, как это реализовать? Сколько места мне нужно использовать в стеке?

Мне нужно использовать 0-4 для значения 4-8 для левого ребенка и 8-12 для правого ребенка?

Я имею в виду, как мне перейти к следующему ребенку от корня?

1 Ответ

0 голосов
/ 13 мая 2018

как мне переместить эти данные?

Учитывая указатель на узел в $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).При обычном обходе по порядку каждый узел рассматривается один раз.

Рекурсивный алгоритм - это очевидный способ, но вы можете захотеть сохранить некоторое постоянное состояние в регистрах, то есть использовать их как глобальные переменные в рекурсивных вызовах.Таким образом, вы можете хранить много «живых» состояний в регистрах, вместо того, чтобы фактически передавать / возвращать их так, как это делает наивный компилятор Си.Я собираюсь представить это, используя глобальные переменные регистра. 

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

...