[12주차] 트리의 표현과 트리 순회

4월 6일 자 학습 내용 정리입니다.

 

 

✅ 트리의 표현 방법

이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 다음 코드와 같이 표현할 수 있다.

 

class TreeNode :
  def __init__(self) :
    self.left = None
    self.right = None

 

완전 이진 트리는 배열을 이용해 간단하게 구현할 수 있다.

 

루트 노드부터 깊이를 더해가며 각 정점에 번호를 붙였을 때 어쩐 정점의 번호가 n이라면 왼쪽 자식은 2n, 오른쪽 자식은 2n+1의 인덱스를 가진다.
따라서 이를 배열로 표현하면 아래와 같다.

 

 

 

✅ 트리 순회

트리 순회란 트리의 모든 노드를 방문하는 순서이다.
트리는 비선형 구조로 자료 사이에 정해진 순서가 없기 때문에 각 노드를 방문하고 값을 가져오기 위해 트리 순회가 필요하다.

 

트리 순회는 크게 두 가지 종류가 있다.
바로 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, Breadth First Search)이다.

 

✔️ DFS

DFS는 또 세 가지 종류로 구분된다.

 

 

먼저 전위 순회(preorder)는 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리의 순서로 순회가 이루어진다.

 

 

중위 순회(inorder)는 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리의 순서로 순회가 이루어진다.

 

 

마지막으로 후위 순회(postorder)는 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드의 순서로 순회가 이루어진다.

 

✔️ BFS

BFS의 경우 정점을 방문하는 순서는 다음과 같다.