Page 403 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

10-1 트리

09장에서 살펴본 리스트는 순서대로 데이터를 나열하는 자료구조였습니다. 이번 장에서는
데이터 사이의 계층 관계를 나타내는 자료구조인 트리를 살펴보겠습니다.
계층 관계란 족보에서 볼 수 있는 부모, 자식, 형제 등의 관계를 의미합니다.

트리란?

트리(tree)란 무엇인지 살펴보기 전에 트리와 관련된 용어를 먼저 알아보겠습니다.

트리 관련 용어
트리를 구성하는 요소는 노드(node)와 가지(edge)입니다. 각각의 노드는 가지를 통해 다른
노드와 연결되어 있습니다. 는 노드, 는 가지를 나타냅니다.

노드
루트는 트리의 가장 윗부분에 위치합니다.
가지
루트 레벨０

Ｘ 리프 레벨１

Ｙ 리프 리프 리프 레벨２

리프 리프 리프 리프 레벨３
초록색으로 표시한 부분은 서브 트리라고 부릅니다.
이때 서브 트리의 X는 다시 서브 트리의 루트 역할을 합니다.

[그림 10-1] 트리

루트
트리의 가장 윗부분에 위치하는 노드를 루트(root)라고 합니다. 하나의 트리에는 하나의 루트
가 있습니다. 식물의 나무에도 루트가 1개인 것과 같습니다. 그림을 거꾸로 보면 나무 모양과
비슷하다는 것을 알 수 있습니다.

10•트리 403