트리

트리란?

그래프의 일종으로 두 노드 사이의 하나의 간선만 연결되어 있는, 최소 연결과 계층 형태의 비선형 자료 구조

형제노드: 같은 부모를 가진 노드

트리의 특징

• ‘최소 연결 트리’로 불림, 계층 모델, 방향 비순환 그래프 한 종류
• 트리 종류: 이진 트리, 이진 탐색 트리, AVL트리, 힙(Heap)

트리 순회

트리 구조에서 각각의 노드를 정확히 한 번씩 체계적인 방법으로 방문하는 과정

• 필요 용어
  • N(Node): 해당 노드를 방문
  • L(Left): 왼쪽 서브 트리로 이동
  • R(Right): 오른쪽 서브 트리로 이동
• 순회 방식
  • 전위 순회: N - L - R // 해당 노드를 방문하고, 왼쪽을 전부 방문한 다음 오른쪽을 방문한다.
  • 중위 순회: L - N - R
  • 후위 순회: L - R - N
  • 층별 순회: 낮은 Level부터 순차적으로 순회. 즉, 위에서부터 순차적으로 순회

1. 전위 순회 (N - L - R)

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

⇒ 방문 순서

F → B → A → D → C → E → G → I → H

preorder(node)
	print node.value
	if node.left != null then preorder(node.left)
	if node.right != null then preorder(node.right)

2. 중위 순회 (L - N - R)

1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

⇒ 방문 순서

A → B → C → D → E → F → G → H → I

inorder(node)
	if node.left != null then inorder(node.left)
	print node.value
	if node.right != null then inorder(node.right)

3. 층별 순회 (L - N - R) ⇒ bfs

낮은 level 부터 순차적으로 순회

1. root 노드 방문
2. level 증가
3. 왼쪽에서 오른쪽으로 방문

⇒ 방문 순서

F → B → G → A → D → I → C → E → H

levelorder(root)
	q.enqueue(root)
	while not q.empty do
		node := q.dequeue()
		print node.value
		if node.left != null q.enqueue(node.left)
		if node.right != null q.enqueue(node.right)

4. 후위 순회 (L - R - N)

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

⇒ 방문 순서

A → C → E → D → B → H → I → G → F

postorder(node)
	if node.left != null then postorder(node.left)
	if node.right != null then postorder(node.right)
	print node.value