Morrisのトラバーサルのアルゴリズムは次のようになります:
- 現在のノードをcurrentとして初期化する。
- currentがnullでない限り以下の手順を繰り返す:
a. currentの左の子ノードをleftとして初期化する。
b. leftがnullでない場合、currentと同じ部分木の最右のノードを見つける。
- 最右のノードは、leftを根とする部分木で最も右側にあるノードです。
- このノードの右の子ノードが現在のcurrentであるため、このノードの右の子ノードをnullに設定します。 c. leftがnullの場合、currentを訪れて適切な処理を行います。 d. currentをcurrentの右の子ノードに更新します。
このアルゴリズムを使用すると、二分木をインオーダー（中間順）に走査することができます。走査の順序は、左の部分木、現在のノード、右の部分木の順になります。
以下に、MorrisのトラバーサルのPythonコード例を示します:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def morris_traversal(root):
current = root
while current:
if current.left is None:
# 左の子ノードがない場合、現在のノードを訪れて適切な処理を行う
print(current.val) # 例えば、ノードの値を表示するなどの処理を行う
current = current.right
else:
# 左の子ノードがある場合、最右のノードを見つける
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
# 最右のノードがnullの場合、現在のノードの右の子ノードを最右のノードに設定し、左の子ノードに移動する
predecessor.right = current
current = current.left
else:
# 最右のノードがnullでない場合、最右のノードをnullに設定して、現在のノードを訪れて適切な処理を行う
predecessor.right = None
print(current.val) # 例えば、ノードの値を表示するなどの処理を行う
current = current.right
# 二分木の作成
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# Morrisのトラバーサルを実行
morris_traversal(root)このコード例では、Morrisのトラバーサルを使用して二分木を走査し、ノードの値を表示する処理を行っています。あなたの具体的な要件に応じて、このコードを変更して利用することができます。
以上が、Morrisのトラバーサルに関する解説とコード例です。これにより、効率的な二分木の走査が可能になります。