Python에서 트리의 중위 순회
트리는 에지로 연결된 노드로 구성된 계층적 데이터 구조입니다. 트리를 순회한다는 것은 트리의 모든 노드를 정확히 한 번 방문하는 것을 의미합니다.
노드 표시, 가장 큰 노드와 가장 작은 노드 찾기, 검색, 정렬 등과 같은 다양한 목적으로 트리를 탐색합니다. 이 기사에서는 Python에서 트리의 inorder 탐색을 배우고 구현합니다.
트리의 중위 순회
Inorder 순회는 일종의 깊이 우선 순회입니다. 다음 트리가 있다고 가정합니다.
inorder 순회를 적용하면 각 노드에 대해 아래 단계를 따릅니다.
- 먼저 왼쪽 하위 트리의 모든 노드를 방문해야 합니다.
- 그런 다음 부모 노드를 방문합니다.
- 그런 다음 오른쪽 하위 트리의 모든 노드를 방문합니다.
4, 2, 5, 1, 6, 3, 7 순서로 노드를 가져옵니다.
Python의 중위 트리 순회 구현
파이썬에서 inorder 순회를 구현하는 두 가지 방법이 있습니다. 재귀적이고 반복적인 접근.
재귀적 접근
재귀적 접근 방식은 구현하고 이해하기 쉽습니다. 다음 코드에서는 트리를 저장하기 위한 데이터 구조로 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
반복적 접근
반복적 접근에서 우리는 나중에 방문할 노드를 저장하기 위해 stack을 유지해야 합니다. 이전과 마찬가지로 다음 코드에서 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