二分木の比較には、一般的に以下の2つのアプローチがあります。
- 再帰的な比較: このアプローチでは、二分木を再帰的にたどりながら、ノードごとに値を比較します。比較するノードの値が一致しているかどうかを確認し、一致していない場合は二分木が異なると判断します。また、各ノードの子ノードも再帰的に比較します。以下は、再帰的な比較を行うための簡単なコード例です。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def compare_trees(node1, node2):
if node1 is None and node2 is None:
return True
elif node1 is None or node2 is None:
return False
else:
return (node1.value == node2.value) and compare_trees(node1.left, node2.left) and compare_trees(node1.right, node2.right)
# 二分木の例
root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root2 = Node(1)
root2.left = Node(2)
root2.right = Node(3)
if compare_trees(root1, root2):
print("二分木は同じです")
else:
print("二分木は異なります")- イテレーティブな比較: このアプローチでは、二分木をイテレーションしながら、各ノードの値を比較します。スタックやキューを使用してノードを管理し、比較を行います。再帰を使用せずに比較を行うため、スタックオーバーフローのリスクが低いという利点があります。以下は、イテレーティブな比較を行うための簡単なコード例です。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def compare_trees(node1, node2):
stack1 = [node1]
stack2 = [node2]
while stack1 and stack2:
current1 = stack1.pop()
current2 = stack2.pop()
if current1 is None and current2 is None:
continue
elif current1 is None or current2 is None:
return False
else:
if current1.value != current2.value:
return False
stack1.append(current1.left)
stack1.append(current1.right)
stack2.append(current2.left)
stack2.append(current2.right)
return len(stack1) == len(stack2)
# 二分木の例
root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root2 = Node(1)
root2.left = Node(2)
root2.right = Node(3)
if compare_trees(root1, root2):
print("二分木は同じです")
else:
print("二分木は異なります")以上が、二分木の比較方法についての簡単な説明とコード例です。これらの方法を使用して、二分木の比較を行うことができます。