Если бы я делал это на языке более высокого уровня, я мог бы использовать рекурсию ...
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)
Я не уверен, с чего начать реализацию любого из них в сборке. Это похоже на язык высокого уровня, где рекурсия более элегантна, но часто менее эффективна (без оптимизации хвостовой рекурсии)?
Должен ли я использовать стек или я мог бы сделать это с циклом, который только изменяет регистры? Мне нужно на самом деле считать узлы, а не просто сохранять счетчик, когда они добавляются.
Узлы хранятся в памяти с использованием двух указателей и значения данных, где указатели ссылаются на адреса памяти, хранящие дочерние элементы.
Я использую эмулятор QtSpim, если это имеет какое-то значение для подхода.
Кроме того, я не спрашиваю о готовом коде (если он есть) просто о том, как я должен подходить к проблеме. Я знаю, как работает обход дерева, но я изо всех сил пытаюсь понять, как это делается в сборке.