この性質は、二分木の中で要素を探索するときに特に役立ちます。もし値 x を探しているとすると、常にどちらの方向に進めばよいかが分かるからです。上の例で値 3 を探すときは、まずルートノードの値が5であることを確認します。5は3より大きいため左側に進みます。次に値が2のノードを確認し、2は3より小さいため右側に進みます。続いて値が4のノードを確認し、4は3より大きいため左側に進みます。最後に値が3のノードを見つけ、探していた値3に等しいことから、そのノードを見つけたことがわかります。
# ノードが存在しない場合はNoneとし、値0は使用しない
def search(node: Node | None, x: int):
""" x が木の中にあれば True を、なければ False を返す """
if node is None: # 木の末端まで到達
return False # x を見つけられなかった
if x == node.value: # x と node.value が等しい場合
return True # => 木の中で x を見つけたことになる
if x < node.value: # x がノードの値より小さい => 左側へ進む
return search(node.left) # 左部分木で x を探す
return search(node.right) # それ以外の場合は右部分木を探す
.png?table=block&id=18a2c681-664d-81aa-9367-fde8c8526c6e&cache=v2)
