直径を計算するためには、各ノードを根とする部分木における最長パスの長さを求める必要があります。具体的なアルゴリズムは以下の通りです。
-
二分木の各ノードに対して、そのノードを根とする部分木の高さを求める再帰関数を作成します。高さは、そのノードから最も遠い葉ノードまでの距離です。
-
二分木の各ノードに対して、そのノードを通る最長パスの長さを求める再帰関数を作成します。この関数は、左部分木の高さと右部分木の高さを合計した値に1を足したものです。
-
二分木の各ノードに対して、上記の2つの関数を呼び出して直径を計算します。各ノードの直径を求めた後、最大値を取れば二分木の直径が求められます。
以下に、Pythonでの実装例を示します。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def diameter_of_binary_tree(root):
if root is None:
return 0
left_height = height(root.left)
right_height = height(root.right)
left_diameter = diameter_of_binary_tree(root.left)
right_diameter = diameter_of_binary_tree(root.right)
return max(left_height + right_height + 1, max(left_diameter, right_diameter))
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
# 二分木の作成
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# 二分木の直径の計算
diameter = diameter_of_binary_tree(root)
print("二分木の直径:", diameter)このコードでは、Nodeクラスを使用して二分木を表現し、diameter_of_binary_tree関数で直径を計算しています。height関数は、各ノードの高さを求めるために再帰的に呼び出されます。
以上が、二分木の直径を計算するシンプルで簡単な方法とコード例の説明です。この方法を参考にして、自身で二分木の直径を計算することができます。