方法1: スタックを使用する方法 スタックを使用して、ノードをトラバースする順序で保持します。以下は、スタックを使用したプレオーダートラバーサルのコード例です。
def preorder_traversal(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.value) # ノードの値を表示する代わりに、何らかの処理を行うことも可能です
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)方法2: Morrisトラバーサルを使用する方法 Morrisトラバーサルは、追加のメモリを使用せずにトラバーサルを行う方法です。以下は、Morrisトラバーサルを使用したプレオーダートラバーサルのコード例です。
def preorder_traversal(root):
node = root
while node:
if not node.left:
print(node.value) # ノードの値を表示する代わりに、何らかの処理を行うことも可能です
node = node.right
else:
predecessor = node.left
while predecessor.right and predecessor.right != node:
predecessor = predecessor.right
if not predecessor.right:
print(node.value) # ノードの値を表示する代わりに、何らかの処理を行うことも可能です
predecessor.right = node
node = node.left
else:
predecessor.right = None
node = node.rightこれらは再帰を使用せずにプレオーダートラバーサルを行う方法の一部です。他にもさまざまなアルゴリズムやデータ構造を使用して実装する方法がありますが、上記の2つの方法は一般的なものです。実際の使用に応じて、最適な方法を選択してください。