이진 트리(Binary Tree)

이진 트리는 알고리즘에서 가장 많이 다뤄지는 부분입니다.

 

Chat GPT를 통해 이진 트리를 알아보면 아래와 같은 답변이 나옵니다.

이진 트리(binary tree)는 노드(node)들이 부모-자식 관계로 이루어진 트리 구조입니다. 이진 트리에서 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다. 루트 노드(root node)는 트리의 최상위 노드이며, 부모 노드(parent node)는 자식 노드(child node)를 가리킵니다. 이진 트리는 노드 간에 다음과 같은 관계를 가집니다: 부모 노드는 자식 노드를 가리키며, 자식 노드는 부모 노드를 알지 못합니다. 왼쪽 자식 노드(left child node)는 부모 노드보다 작거나 같은 값을 갖습니다. 오른쪽 자식 노드(right child node)는 부모 노드보다 큰 값을 갖습니다. 이진 트리는 많은 알고리즘에서 활용되며, 특히 검색(search) 연산에서 유용합니다. 이진 탐색 트리(binary search tree)는 이진 트리의 일종으로, 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 특징이 있어 검색 연산이 빠릅니다.

 

이진 트리를 구성하는 노드를 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. 오른쪽 자식 노드를 전위 순회합니다.

이를 재귀적으로 구현하면 다음과 같습니다:

1. 현재 노드를 출력합니다.
2. 왼쪽 자식 노드가 있으면, 왼쪽 자식 노드에 대해 재귀적으로 전위 순회를 수행합니다.
3. 오른쪽 자식 노드가 있으면, 오른쪽 자식 노드에 대해 재귀적으로 전위 순회를 수행합니다.

예를 들어 다음과 같은 이진 트리가 있는 경우 

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 →  9 순으로 읽는 방법입니다.

LeetCode에서 관련된 문제를 풀어 볼 수 있으며, 풀이법은 다음 글을 참고하시면 됩니다.

2023.03.04 - [코딩테스트/Binary Tree] - [LeetCode] 144. Binary Tree Preorder Traversal 문제 풀이

 

 

이진 트리의 중위 순회(inorder traversal)는 다음과 같이 정의됩니다:

1. 왼쪽 자식 노드를 중위 순회합니다.
2. 현재 노드를 방문(출력)합니다.
3. 오른쪽 자식 노드를 중위 순회합니다.

이를 재귀적으로 구현하면 다음과 같습니다:

1. 왼쪽 자식 노드가 있으면, 왼쪽 자식 노드에 대해 재귀적으로 중위 순회를 수행합니다.
2. 현재 노드를 출력합니다.
3. 오른쪽 자식 노드가 있으면, 오른쪽 자식 노드에 대해 재귀적으로 중위 순회를 수행합니다.

앞선 예의 이진 트리의 경우

4 → 3 → 2 → 5 → 1 → 7 → 8 → 6 → 9 순으로 읽는 방법입니다.

마찬가지로 LeetCode에서 관련된 문제를 풀어 볼 수 있으며, 풀이법은 다음 글을 참고하시면 됩니다.

2023.03.04 - [코딩테스트/Binary Tree] - [LeetCode] 94. Binary Tree Inorder Traversal 문제 풀이

 

이진 트리의 후위 순회(postorder traversal)는 다음과 같이 정의됩니다:

1. 왼쪽 자식 노드를 후위 순회합니다.
2. 오른쪽 자식 노드를 후위 순회합니다.
3. 현재 노드를 방문(출력)합니다.

이를 재귀적으로 구현하면 다음과 같습니다:

1. 왼쪽 자식 노드가 있으면, 왼쪽 자식 노드에 대해 재귀적으로 후위 순회를 수행합니다.
2. 오른쪽 자식 노드가 있으면, 오른쪽 자식 노드에 대해 재귀적으로 후위 순회를 수행합니다.
3. 현재 노드를 출력합니다.

앞선 예의 이진 트리의 경우

4 → 3 → 5 → 2 → 8 → 7 → 9 → 6 → 1 순으로 읽는 방법입니다.

마찬가지로 LeetCode에서 관련된 문제를 풀어 볼 수 있으며, 풀이법은 다음 글을 참고하시면 됩니다.

2023.03.04 - [코딩테스트/Binary Tree] - [LeetCode] 145. Binary Tree Postorder Traversal 문제 풀이