[자료구조] 트리 개론

트리가 잘 기억이 안나서 정리해본다.

트리의 용어

• root: 최상위 노드, 모든 자식들의 조상
• child(자식) 노드: 현재 노드와 연결된 하위노드
• degree(차수)
  • 노드의 차수: 현재 노드가 가진 서브트리의 개수
  • 트리의 차수: 노드의 차수중 가장 큰 값
• Leaf(잎): 자식이 없는 노드
• Sibling(형제) 노드: 같은 부모를 가진 노드
• Ancestor(조상) 노드: 현재 노드부터 루트노드들까지 존재하는 부모노드 집합
• Descendant(후손) 노드: 현재 노드를 조상으로 가지는 모든 하위노드 집합
• depth(깊이): 현재 노드까지 접근하기 위한 간선의 개수
• level: 같은 depth을 가진 노드의 집합
• height: 트리의 최대 레벨

이를 다음과 같은 트리에서 용어에 매칭되는 노드 혹은 값을 설명하겠다.

• root: 1번 노드
• child
  • 1번노드 => 2,3
• degree:
  • 1번노드 => 2번을 루트노드로 가진 서브트리, 3번을 루트노드로 가진 서브트리 => 2개
  • 3번노드 => 0개
• leaf:
  • 3,4,5번 노드
• Sibling
  • 2번노드의 Sibling 노드: 3번
• Ancestor:
  • 4번 노드의 Ancestor 노드: 2,1번 노드
• Desendant:
  • 1번노드의 Desendant 노드: 2,3,4,5번 노드
• level:
  • level1의 노드: 1
  • level2의 노드: 2,3
  • level3의 노드: 4,5
• height: 3

순회

트리내의 노드를 방문하는 과정을 순회라고 한다. 트리의 순회방식은 4가지로 다음과 같다.

1. 전위순회
2. 중위순회
3. 후위순회
4. 레벨순회

다음과 같은 정보의 트리에서 노드 방문을 순회의 방법에 따라 어떻게 방문하는 것인지를 알아보자.

• root: 1
• depth: 3

1. 전위 순회(Preorder Traverse)

• Node -> Left -> Right 순으로 방문한다.
• 현재 노드를 방문하고 인접한 Left, Right노드 들을 방문한다.
• 루트부터 탐색하면 다음과 같다. 1->2->4->5->3

2. 중위 순회(Inorder Traverse)

• Left -> Node -> Right 순으로 방문한다.
• 현재 노드가 leaf노드거나 후손 노드들을 모두 방문하여야 현재 노드를 방문한다.
• 4->2->5->1->3

3. 후위 순회(Postorder Traverse)

• Left -> Right -> Node 순으로 방문한다.
• 자식들을 모두 읽은 후에 자기 자신을 방문한다.
• 4->5->2->3->1

4. 레벨 순회(Level Order Traverse)

• 레벨이 낮은 곳부터 높은 순으로 방문
• 레벨이 낮을수록 먼저 방문한다.
• 루트노드가 존재하는 레벨부터 시작
• 같은 레벨의 노드들은 왼쪽 -> 오른쪽의 노드순으로 방문한다.
• 1->2->3->4->5