後行順巡回は、二分探索木のノードを以下の順序で訪れる方法です: 左の部分木、右の部分木、ノード自体。この順序でノードを訪れることで、二分探索木の要素をソートされた順序で表示することができます。
以下に、Pythonで後行順巡回を計算するためのコード例を示します:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def postorder_traversal(node):
if node is None:
return
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.value)
# 二分探索木の作成
root = Node(4)
root.left = Node(2)
root.right = Node(6)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(5)
root.right.right = Node(7)
# 後行順巡回の実行
postorder_traversal(root)このコードでは、Nodeクラスを定義し、各ノードには値と左右の子ノードがあります。postorder_traversal関数は再帰的に呼び出され、左の部分木、右の部分木、ノード自体の順序でノードを訪れます。各ノードの値はprint文で表示されます。
以上が二分探索木の後行順巡回を計算するためのコード例です。他のプログラミング言語でも同様のアルゴリズムを実装することができます。