以下に、中間順走査のイテレータ法についてのシンプルで簡単な実装方法といくつかのコード例を示します。
- スタックを使用したイテレータ法: 中間順走査では、現在のノードの左部分木を訪れた後、現在のノードを処理し、その後に右部分木を訪れる必要があります。この順序を保つために、スタックを使用します。
以下は、この方法の疑似コードです:
function inorderTraversal(root):
stack = []
current = root
result = []
while current is not null or stack is not empty:
while current is not null:
stack.push(current)
current = current.left
current = stack.pop()
result.push(current.value)
current = current.right
return result- 再帰を使用した中間順走査: 再帰を使用することでも中間順走査を実装することができます。以下は、再帰を使用した実装例です:
function inorderTraversal(root):
result = []
def traverse(node):
if node is null:
return
traverse(node.left)
result.push(node.value)
traverse(node.right)
traverse(root)
return result上記のコード例は、中間順走査のイテレータ法の基本的な実装方法です。それぞれの方法は、ツリーの要素を順番に処理するための効果的な手法です。
このように、中間順走査のイテレータ法を使用することで、ツリーの要素を簡単かつ効率的に処理することができます。これは、ツリーの探索やソートなど、さまざまなアルゴリズムやデータ処理に応用することができます。