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)

アセンブリでこれらのいずれかの実装を開始する場所がわかりません。再帰がよりエレガントですが、しばしば効率が悪い（末尾再帰の最適化なし）高級言語に似ていますか？

スタックを使用する必要がありますか、それともレジスタのみを変更するループでこれを行うことができますか? ノードが追加されたときにカウンターを保持するだけでなく、実際にノードをカウントする必要があります。

ノードは、2 つのポインタとデータ値を使用してメモリに格納されます。ポインタは、子を格納するメモリ アドレスを参照します。

アプローチに違いがある場合は、QtSpimエミュレーターを使用しています。

また、完成したコード (コードがあれば..) を求めているわけではありません。ツリー トラバーサルがどのように機能するかは知っていますが、アセンブリでどのように行われるかを理解するのに苦労しています。

4

1 に答える 1

1

どちらのアプローチを使用することを妨げるものは何もありません。それらの間に違いは見られません。ただし、O(1) メモリで実行されるツリー トラバーサル アルゴリズムがあるため、再帰とスタックは使用されません。詳細については、https ://sites.google.com/site/debforit/effective-binary-tree-traversal-with-two-pointers をご覧ください。

于 2012-03-03T12:19:24.303 に答える