자료구조 - 트리

컬렉션 프레임워크(Collection Framework)

트리

• 자료의 항목(node)들이 가지(edge)로 연결될 수 있게 자료가 구성되어 있는 구조
• 계층적 구조
• 부모-자식 관계의 노드로 구성

트리의 용어

• 노드(node): 트리를 구성하는 각 자료 항목: A, B, C, D, E, F, ...
• 근 노드(root node)
  • 트리 구조를 시작하는 노드
  • 제일 상위 계층에 존재하는 하나의 노드 A
• 자식 노드
  • 임의의 노드에 연결된 다음 레벨의 노드들의 집합
  • D의 자식 노드는 H, I, J
• 부모 노드
  • 임의의 노드에 연결된 상위 계층의 노드
  • A는 B, C, D의 부모
• 차수(degree)
  • 노드에 연결된 자식 노드의 수
  • A의 차수: 3, B의 차수: 2, C의 차수: 1
• 레벨
  • root node 레벨을 0으로 하고 그 아래 가지로 연결된 노드는 레벨 1, 그 아래는 레벨 2, ...
• 트리의 깊이(depth)
  • 어떤 특정 노드에서 root 노드에 이르는 경로의 길이
  • E의 깊이: 2
• 트리의 높이(height)
  • 트리의 최대 레벨 + 1
  • A의 높이: 3

트리 구조의 저장

• 배열을 이용한 방법
• 연결 리스트를 이용한 방법

배열을 이용한 방법

• 연속적인 기억 공간을 그대로 이용하는 배열의 구조에 트리를 저장
• 각 노드 당 최대 차수 3만큼 기억 장소 확보
• 최대 기억 장소: 총노드의 개수 x 트리의 차수 + 1 = 37

이진트리

• 트리의 모든 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 정의
• 이진트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가짐
• root 노드만 있어도 이진트리로 인정
• 왼쪽과 오른쪽의 방향성 존재

트리의 순회 (tree traverse)

• 트리 구조의 각 노드를 전부 한 번씩 방문하여 검색해내는 방법
• 레벨 순서 순회 방법
  • 상향식 레벨 순서 순회법
  • 하향식 레벨 순서 순회법
• 노드의 위치에 따른 순회법
  • 전위순회
  • 중위순회
  • 후위순회

이진트리의 순회법

• 일반적인 트리의 순회보다 간단

• 나타낼 수 있는 조합의 수는 6가지이나, 왼쪽 서브트리가 오른쪽 서브트리보다 선행한다는 제약을 주면 3가지 순회만 존재

  • 전위 순회: root - left - right

    

  • 중위 순회: left - root - right

  

  • 후위 순회: left - right - root

트리 연습문제

• 이진트리 구성(작은 값은 왼쪽, 큰 값은 오른쪽으로)
  • 5, 2, 8, 1, 4, 6, 9, 3, 7

• 트리 순회 결과 표시
  • 전위: 5 - 2 - 1 - 4 - 8 - 6 - 7 - 9
  • 중위: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
  • 후위: 1 - 3 - 4 - 2 - 7 - 6 - 9 - 8 - 5