0

如果我用更高级别的语言来做这件事，我可以使用递归......

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 模拟器。

另外，我不是要求完整的代码（如果有代码的话..）我应该如何解决这个问题。我知道树遍历是如何工作的，但我很难看到它是如何在汇编中完成的。

4

1 回答 1

1

没有什么能阻止您使用任何一种方法。我看不出它们之间有什么区别。但是，有一种树遍历算法在 O(1) 内存中运行，因此它不使用递归和堆栈。您可以在此处阅读更多相关信息：https ://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

于 2012-03-03T12:19:24.303 回答