트리 탐색이란, 트리를 돌면서 어떤 원소가 있는지 확인하는 작업을 말합니다. 이 때 어느 원소를 먼저 보는지에 따라 순회의 종류가 달라집니다.
트리의 순회는 재귀 방법으로 쉽게 구현할 수 있습니다.
전위탐색(preorder traversal)
root가 먼저 읽히는 탐색 (root-> left -> right)
전위탐색은 트리 구조에서 루트 노드를 가장 먼저 탐색하는 방법입니다. 루트 노드를 기준으로 왼쪽 자식 노드를 먼저 방문하고, 그 후 오른쪽 자식 노드를 방문합니다. 전위탐색은 노드의 방문 순서가 중요한 알고리즘에서 사용됩니다. 이 방식은 노드 방문 순서가 중요한 경우에 사용됩니다. 예를 들어, 트리를 복제하는 경우, 전위탐색 방식을 활용할 수 있습니다.
def preorder(node):
if node is not None:
print(node.data)
preorder(node.left)
preorder(node.right)
중위탐색(inorder traversal)
root가 중간에서 읽히는 탐색 (left -> root -> right)
중위탐색은 트리 구조에서 루트 노드를 두 번째로 탐색하는 방법입니다. 루트 노드를 기준으로 왼쪽 자식 노드를 방문한 후 루트 노드를 방문하고, 그 후 오른쪽 자식 노드를 방문합니다. 중위탐색은 노드의 값으로 정렬된 순서로 노드를 처리해야 하는 알고리즘에서 사용됩니다. 이 방식은 이진 탐색 트리에서 값을 찾아야 하는 경우에 사용됩니다.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.data)
inorder(node.right)
후위탐색(postorder traversal)
root가 마지막에 읽히는 탐색 (left -> right -> root)
후위탐색은 트리 구조에서 루트 노드를 마지막으로 탐색하는 방법입니다. 루트 노드를 기준으로 왼쪽 자식 노드를 방문한 후 오른쪽 자식 노드를 방문한 후, 마지막으로 루트 노드를 방문합니다. 후위탐색은 부모 노드를 나중에 처리해야 하는 알고리즘에서 사용됩니다. 이 방식은 트리를 삭제해야 하는 경우에 사용됩니다.
def postorder(node):
if node is not None:
postorder(node.left)
postorder(node.right)
print(node.data)
