이진 트리는 알고리즘에서 가장 많이 다뤄지는 부분입니다.
Chat GPT를 통해 이진 트리를 알아보면 아래와 같은 답변이 나옵니다.
| 이진 트리(binary tree)는 노드(node)들이 부모-자식 관계로 이루어진 트리 구조입니다. 이진 트리에서 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다. 루트 노드(root node)는 트리의 최상위 노드이며, 부모 노드(parent node)는 자식 노드(child node)를 가리킵니다. 이진 트리는 노드 간에 다음과 같은 관계를 가집니다:
|
이진 트리를 구성하는 노드를 Code로 표현하자면 아래와 같이 구현됩니다.(Python)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
이진트리의 값을 순회하는 방법에 따라 전위 순회, 중위 순회, 후위 순회 3가지 방법으로 나뉩니다.
이진 트리의 전위 순회(preorder traversal)는 다음과 같이 정의됩니다:
- 현재 노드를 방문(출력)합니다.
- 왼쪽 자식 노드를 전위 순회합니다.
- 오른쪽 자식 노드를 전위 순회합니다.
이를 재귀적으로 구현하면 다음과 같습니다:
- 현재 노드를 출력합니다.
- 왼쪽 자식 노드가 있으면, 왼쪽 자식 노드에 대해 재귀적으로 전위 순회를 수행합니다.
- 오른쪽 자식 노드가 있으면, 오른쪽 자식 노드에 대해 재귀적으로 전위 순회를 수행합니다.
예를 들어 다음과 같은 이진 트리가 있는 경우
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 순으로 읽는 방법입니다.
LeetCode에서 관련된 문제를 풀어 볼 수 있으며, 풀이법은 다음 글을 참고하시면 됩니다.
2023.03.04 - [코딩테스트/Binary Tree] - [LeetCode] 144. Binary Tree Preorder Traversal 문제 풀이
이진 트리의 중위 순회(inorder traversal)는 다음과 같이 정의됩니다:
- 왼쪽 자식 노드를 중위 순회합니다.
- 현재 노드를 방문(출력)합니다.
- 오른쪽 자식 노드를 중위 순회합니다.
이를 재귀적으로 구현하면 다음과 같습니다:
- 왼쪽 자식 노드가 있으면, 왼쪽 자식 노드에 대해 재귀적으로 중위 순회를 수행합니다.
- 현재 노드를 출력합니다.
- 오른쪽 자식 노드가 있으면, 오른쪽 자식 노드에 대해 재귀적으로 중위 순회를 수행합니다.
앞선 예의 이진 트리의 경우
4 → 3 → 2 → 5 → 1 → 7 → 8 → 6 → 9 순으로 읽는 방법입니다.
마찬가지로 LeetCode에서 관련된 문제를 풀어 볼 수 있으며, 풀이법은 다음 글을 참고하시면 됩니다.
2023.03.04 - [코딩테스트/Binary Tree] - [LeetCode] 94. Binary Tree Inorder Traversal 문제 풀이
이진 트리의 후위 순회(postorder traversal)는 다음과 같이 정의됩니다:
- 왼쪽 자식 노드를 후위 순회합니다.
- 오른쪽 자식 노드를 후위 순회합니다.
- 현재 노드를 방문(출력)합니다.
이를 재귀적으로 구현하면 다음과 같습니다:
- 왼쪽 자식 노드가 있으면, 왼쪽 자식 노드에 대해 재귀적으로 후위 순회를 수행합니다.
- 오른쪽 자식 노드가 있으면, 오른쪽 자식 노드에 대해 재귀적으로 후위 순회를 수행합니다.
- 현재 노드를 출력합니다.
앞선 예의 이진 트리의 경우
4 → 3 → 5 → 2 → 8 → 7 → 9 → 6 → 1 순으로 읽는 방법입니다.
마찬가지로 LeetCode에서 관련된 문제를 풀어 볼 수 있으며, 풀이법은 다음 글을 참고하시면 됩니다.
2023.03.04 - [코딩테스트/Binary Tree] - [LeetCode] 145. Binary Tree Postorder Traversal 문제 풀이