Python でのツリーのインオーダートラバーサル
ツリーは、エッジで接続されたノードで構成される階層データ構造です。ツリーをトラバースするということは、ツリーのすべてのノードに 1 回だけアクセスすることを意味します。
ノードの表示、最大ノードと最小ノードの検索、検索、並べ替えなど、さまざまな目的でツリーをトラバースします。この記事では、Python でツリーの順序どおりのトラバースを学習して実装します。
ツリーのインオーダートラバーサル
Inorder トラバーサルは、深さ優先トラバーサルの一種です。次のツリーがあるとします。
inorder トラバーサルを適用する場合は、ノードごとに以下の手順に従います。
- まず、左側のサブツリーのすべてのノードにアクセスする必要があります。
- 次に、親ノードにアクセスします。
- 次に、右側のサブツリーのすべてのノードにアクセスします。
4, 2, 5, 1, 6, 3, 7 の順序でノードを取得します。
Python での順序ツリートラバーサルの実装
Python で inorder トラバーサルを実装する方法は 2つあります。再帰的かつ反復的なアプローチ。
再帰的アプローチ
再帰的アプローチは、実装と理解が簡単です。次のコードでは、ツリーを格納するためのデータ構造としてクラス Node を作成しました。
各ノードは、値、その左と右の子で構成されます。inorder トラバーサルは、左右のサブツリーに対して再帰的に機能します。
すべてのノードについて、inorder トラバーサルは、その左側のノード、親、および右側のノードにアクセスすることによって実行されます。
サンプルコード：
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.val = value
def inorder(root):
if root:
inorder(root.left)
print(str(root.val))
inorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)
出力：
Inorder traversal of the Tree
4
2
5
1
6
3
7
反復アプローチ
反復アプローチでは、後でアクセスするノードを格納するためにスタックを維持する必要があります。前と同じように、次のコードでクラス Node を作成しました。
空のスタックを作成し、ルートノードを現在のノードにすることで開始しました。現在のノードが存在する場合は、それをスタックにプッシュして、左側のノードに移動します。
それ以外の場合、ノードが存在しない場合は、スタックから要素をポップして出力します。左側のノードが存在しない場合は、現在のノードにして右側のノードに移動します。
スタックと現在の要素の両方が空になるまで、同じ手順を繰り返します。
サンプルコード：
from collections import deque
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.val = value
def inorder(root):
stack = deque()
curr = root
while stack or curr:
if curr:
stack.append(curr)
curr = curr.left
else:
curr = stack.pop()
print(curr.val)
curr = curr.right
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)
出力：
Inorder traversal of the Tree
4
2
5
1
6
3
7
I am Fariba Laiq from Pakistan. An android app developer, technical content writer, and coding instructor. Writing has always been one of my passions. I love to learn, implement and convey my knowledge to others.
LinkedIn