граф узлов в бинарном дереве с использованием MIPS ASM

Question

Если бы я делал это на языке более высокого уровня, я мог бы использовать либо рекурсии ...

size(node): 
    1 + size(node.left) + size(node.right) 

или итерации ...

size = 0 
stack = new Stack() 
stack.push(root) 
while(!stack.isEmpty()): 
    size++ 
    node = stack.pop() 
    stack.push(node.left) 
    stack.push(node.right) 

I Не знаю, с чего начать внедрять любой из них в сборке. Это похоже на язык высокого уровня, где рекурсия более изящна, но часто менее эффективна (без оптимизации хвостовой рекурсии)?

Должен ли я использовать стек, или я могу сделать это с помощью цикла, который только изменяет регистры? Мне нужно фактически подсчитывать узлы - не просто держать счетчик, как они добавлены.

Узлы хранятся в памяти с использованием двух указателей и значения данных, где указатели ссылаются на адреса памяти, хранящие дочерние элементы.

Я использую эмулятор QtSpim, если это имеет какое-то значение для подхода.

Кроме того, я не прошу заполненный код (если какой-либо код ...), как мне подойти к проблеме. Я знаю, как работает обход дерева, но я изо всех сил пытаюсь понять, как это делается в сборке.

Answer 1

Ничто не мешает вам использовать любой подход. Я не вижу никакой разницы между ними. Тем не менее, существует алгоритм обхода дерева, который работает в O (1) памяти, поэтому он не использует рекурсию и стек. Вы можете узнать больше об этом здесь: https://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers